A Brief Intro:

  • Learning Objective: ArrayList objects are a good way to represent collections of related object reference data.
  • An ArrayList is Mutable and contains Object References
    • Mutable: Changeable in size and content
    • Object References: Stores Wrapper Class Objects, not primitives

Vocabulary:

  • Static: size can't be changed
    • Arrays are static in size
  • Dynamic: size can be changed at any time
    • ArrayLists are dynamic

Differences between Array and ArrayList:

Array ArrayList
fixed length resizable length
fundamental java feature park of a framework
an Object with no methods a Class with many methods
not as flexible flexible
can store primitive data not designed to store primitives
  • Additionally, it's slightly slower than an Array and can only be used with an import statement
  • ArrayList class is implemented using Arrays!

Declaring an ArrayList: 

// make sure to import!
import java.util.ArrayList;

// declare a variable to reference an ArrayList Object
ArrayList<DataType> variableName;

// instantiate an ArrayList Object
// stores only elements of the same, NONPRIMITIVE DataType
New ArrayList<DataType>(); // empty
New ArrayList<DataType>(n); // has n spaces
  • Use primitive values disguised as Wrapper Class Objects for ArrayLists, since they can only store references to objects, not primitive values!

Hack 1!

Create an ArrayList:

// a) that stores Boolean values
;

// b) that stores Turtle Objects
;

// c) that initializes with 10 Strings
;

Methods with ArrayLists:

  • int .size(): returns the number of elements in the ArrayList
  • boolean .add(datatype obj): appends obj to the end of the list; returns true
  • datatype .add(int index, datatype obj): inserts obj at position index and moves the rest of the elements to the right higher
  • datatype .remove(int index): removes element from position index and moves the elements to right of it lower
  • datatype .set(int index, datatype obj): replaces the element at position index with obj; returns the element formerly as position index
  • datatype .get(int index): returns the element at position index in the list

Hack 2!

Choose 3 different methods from above to change around this sample ArrayList:

import java.util.ArrayList;

public class Hack2 {
    public static void main(Integer[] args) {
        ArrayList<Integer> randomNumbers = new ArrayList<Integer>();
        randomNumbers.add(1);
        randomNumbers.add(4);
        randomNumbers.add(7);
        randomNumbers.add(12);
        randomNumbers.add(23);
        System.out.println("ArrayList: " + randomNumbers);

        ;
        ;
        ;
    }
}
Hack2.main(null);

int int1 = 1 % 5;
System.out.println(int1);

1

Passing an ArrayList as a Method Parameter:

  • ArrayList are reference objects and when passed as a parameter in a method they are passed as references to their addresses, not copies of their values
  • Methods access and update the elements in ArrayLists directly, so be careful

Traversing an ArrayList with Loops

  • For loops traverse an ArrayList given that a value condition is met (i) and updated each time
    • i++ or i--, i = 0 or i = arr.size()-1
  • While loops continue while i meets a certain condition
    • i <arr.size()
  • Enhanced for loops do not explicitly use a variable for index tracking
    • for variable : collection
//basic
for (int i = 0, i < arr.size()-1, i++) {
    
}

//enhanced
for (DataType variable: collection) {
    
}

while (int i < arr.size()-1) {
    //code
    i++
}

Developing Algorithms Using ArrayLists

  • Common AP exam operations include finding a max or minimum value and summing the integers in an ArrayList
// sample for max value search

private double findMax (ArrayList<Double> values) {
    double max = values.get(0); // setting first value as variable for comparison

    for (int index = 1; index < values.size(); index++) { // checking values from 2nd to last 
        if (values.get(index) > max) {
            max = values.get(index); // updating max value with each check
        }
    }
    return max;
}

Hack 3!

Here is some sample code for the total sum of integers. Finish the loop!

public class Hack3 {
    public static void main(ArrayList<Integer> values) {
        ArrayList<Integer> values = new ArrayList<Integer>();
        values.add(1);
        values.add(4);
        values.add(7);
        values.add(12);
        values.add(23);
        System.out.println("ArrayList: " + values);
        
        int total = 0;

            for (int i=0; i < values.size(); i++) {
                ;
            }
    }
}
Hack3.main(null);

On the Exam

  • Min/max value
  • Find sum, avg, or mode
  • Check elements for particular property
  • Check duplicates (individuals or pairs)
  • Count elements meeting specific criteria
  • Shift or reverse elements

Searching Within ArrayLists

  • Linear search uses loops to check each element for a condition
    • It's best to go backwards through an array, that way if you remove an element from the array the index of the next few elements won't change
  • Remember different checks for conditions:
    • == for int
    • rounding for doubles (or subtraction)
    • .equals() for objects
  • Usual return method is index or -1 (false) if not found
    • In this way, enhanced for loops are useful if checking for existence (no indexes)
  • Sample Search Code:
public int where(double magicNumber, ArrayList<Double> realNumbers, double delta) {
    for (int index = 0; index < realNumbers.size(); index++) {
        if (Math.abs(magicNumber-realNumbers.get(index)) < delta) {
            return index;
        }
    }
    return -1;
}
  • You may have to sort the ArrayList first to avoid skipping values
  • Another way is to go backwards through an array, that way if you remove an element from the array the index of the next few elements won't change
  • A way to not worry about index at all is to use an enhanced for loop
  • If removing elements, use index-- to avoid skipping elements
if (myList.get(index).equals(searchedValue)) {
    myList.remove(index);
    index--;
}

Sorting

  • Selection sort uses a min/max variable that updates with a linear iteration pattern
  • Needs a helper method to swap values using a third variable
  • End goal is to be able to implement a selection sort within an ArrayList

Hack 4!

Complete the Selection sort sample code by writing code for a swap of elements.

for (int i = 0; i < arr.length; i++) {
 
    // nested loop 1 index ahead
    for (int j = i + 1; j < arr.length; j++) {

        // comparing elements
        int temp = 0;
        if (arr[j] < arr[i]) {

            // write the swap code!
            ;
        }
    }

    // Printing sorted array 
    System.out.print(arr[i] + " ");
}
  • Insertion sort builds sorted structure by placing elements at assigned indexes, and uses a while loop
  • Sample code:
for (int outer = 1; outer < randomList.size(); outer+) {
    DebugDuck tested = randomList.get(outer);
    int inner = outer - 1;

    while (inner >= 0 && tested.compareTo(randomList.get(inner)) < 0) {
        randomList.set(inner + 1, randomList.get(inner));
        inner--;
    }
    randomList.set(inner + 1, tested);
}