Unit 6 gave you the knowledge to work with collections of related data. While arrays are useful and convenient, they do have their limitations.

Size: The size of the array must be established at the time of creation and cannot be changed. You would need to rebuild a brand-new array if you wanted a bigger one! Do you always know how big your data will be?

Adding/removing: It is not possible to actually remove elements in an array other than re-assigning it some invalid value! You also cannot add to an array so that it includes one or two more elements from its original size. This goes back to the fact that the size must be known during creation. Collections of data that may change can be things like a shopping list or a to-do list. They are a collection of data where you could expect someone to want to add or remove elements from it.

ArrayList is the answer to this limitation! The underlying structure is actually an array that grows and shrinks, but that is automatically done for the user of the data structure. You do not need to define a starting size for an array and you can add and remove freely. You may see other CSA material refer to ArrayList as a List. This is actually because ArrayList is the actual implementation of a List but they do represent the same thing. A List is an interface describing a set of behavior for what it means to be a list while an ArrayList is the actual implementation of the behaviors! Interfaces are no longer on the AP Exam.

The line below is how you declare and create an ArrayList. Similar to an array, you do not have the actual data structure until you call the constructor for the list.

ArrayList nameOfList = new ArrayList();

For Type, ArrayLists are limited to Object types only! The good news is that there are Object versions of the primitive types you have worked with known as wrapper classes. They are Integer, Double, Boolean.

//invalid list because int is not an Object type
ArrayList error = new ArrayList()

//corrected array from above
ArrayList error = new ArrayList();

Practice declaring and creating lists in the practice problems!

 The following are all of the methods you should be familiar with to be prepared for the AP Exam.

int size()
    returns the number of elements in the list boolean

add(E obj)
     appends obj to the end of the list and returns true

E remove(int index)
     removes the item at the index and shifts remaining items to the left (to a lower index)

void add(int index, E obj)
     moves any current objects at index or beyond to the right (to a higher index) and inserts obj at the index

E get(int index)
     returns the item in the list at the index

E set(int index, E obj)
     replaces the item at index with obj size vs length

Arrays use .length while lists uses size(). You can think of lists using a getter to obtain the size while arrays use a property/field.

There are two main ways to add to an ArrayList. The first one will automatically add to the end of the list while in the second version you can specify a valid index to insert into.

add(object): The first version of add is if you are trying to add to the end of the list. If you do not specify where to add it will automatically add to the end.

Printing the list below will result in [5 7]

ArrayList test = new ArrayList();
test.add(5);
test.add(7);
add(index, obj)

If you want to insert an element into a list you can use the second version of add. You need to ensure you are using a valid index. You are allowed to specify locations 0 to size. If you add at the size of the array you effectively adding to the end of the list. You will get an IndexOutOfBoundsException.

Printing the list below results in [9, 5, 4, 1].

ArrayList test = new ArrayList();
test.add(5);
test.add(4);
test.add(2, 1);
test.add(0, 9);

Add methods allow you to insert elements into the list. If you want to override an element at a position you can use set. This will replace the element! get is used to access an element from the list similar to the bracket [ ] notation for arrays.

ArrayList phrase = new ArrayList();
phrase.add("San");
phrase.add("Diego");
phrase.add("is");
phrase.add("awesome");
System.out.println(phrase);
System.out.println(phrase.get(0));
System.out.println(phrase.get(1));
phrase.set(3, "the best");
System.out.println(phrase);

The output of the program above is below. Be sure you know why!

[San, Diego, is, awesome]
San
Diego
[San, Diego, is, the best] 

One of the advantages of a list is the ability to remove elements from it! The remove method has an index parameter to specify which element to remove. All the elements to the right of that element will shift and the size of the list will decrease by 1. The method returns the element you removed from the list.

ArrayList list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
int x = list.remove(1);
System.out.println(list);

The code above produces the following output:

[1, 2, 3, 4]
[1, 3, 4]

Traversing lists look similar to traversing arrays as shown below. The loop is still mainly responsible for generating the addresses (indexes) to the elements. It is up to the programmer what to do once they have access to the element.

int[] vals = {1 , 5, 2, 5};
int sum = 0;
for(int i =0; i < vals.length; i++){
    sum += vals[i];
}
ArrayList vals2 = new ArrayList();
vals2.add(1);
vals2.add(5);
vals2.add(2);
vals2.add(5);
sum = 0;
for(int i =0; i < vals2.size(); i++){
    sum += vals2.get(i);
}

There are many practice problems provided to help you practice traversals! Once you can do certain algorithms with arrays, it is not too much work to translate that knowledge to using lists!

You should familiarize yourself with these common algorithms for lists. You will be in a good place if you can perform these on lists and arrays.

• Insert elements
• Delete elements
• Determine the minimum or maximum value
• Compute a sum, average, or mode of elements
• Search for a particular element in the array
• Determine if at least one element has a particular property
• Determine if all elements have a particular property
• Access all consecutive pairs of elements
• Determine the presence or absence of duplicate elements
• Determine the number of elements meeting specific criteria Shift or rotate elements left or right
• Reverse the order of the elements
• Be able to perform the above operations for Primitives or Objects! ([ints, doubles, booleans] vs [String and whatever Class is given in the problem])
  
  

Use the practice problems to get started!

In AP CSA, if you have unsorted data, a linear/sequential search is the only method that can be used to find a value. It will start at the beginning and walk through the entire array until it finds the element or doesn't find the element. It will return the index of the element if found otherwise it will return -1. Below are two versions of linear search using an array and a list.

public static int sequentialSearch(String[] elements, String target){
    for (int j = 0; j < elements.length; j++){
        if (elements[j].equals(target)){
            return j;
        }
    }
    return -1;
}
public static int sequentialSearch(int[] elements, int target){
    for (int j = 0; j < elements.length; j++){
        if (elements[j] == target){
            return j;
        }
    }
    return -1;
}

When you have sorted data, you can use Binary Search. Binary search will divide the sorted search space into halves. It compares a target value to the value in the middle of a range of indices. If the value isn't found it looks again in either the left or right half of the current range. Each time through the loop it eliminates half the values in the search area until either the value is found or there is no more data to look at. Below is an animation showing searching for a negative number that does not exist in the data. Included is also the code used for binary search without recursion. How would you change it to work with a list instead of an array?

public static int binarySearch(int[] elements, int target) {
    int left = 0;
    int right = elements.length - 1;
    while (left <= right){
        int middle = (left + right) / 2;
        if (target < elements[middle]){
            right = middle - 1;
        }
        else if (target > elements[middle]){
            left = middle + 1;
        }else {
            return middle;
        }
    }
    return -1;
}

You will learn about 3 sorting algorithms that will be on the AP Exam in some fashion. Typically they show up in multiple-choice questions.

Selection Sort - Select the smallest item from the current location onto the end of the array and swap it with the value at the current position. Do this from index 0 to the array length - 2. You don't have to process the last element in the array, it will already be sorted when you compare the prior element to the last element.

Insertion Sort - Insert the next unsorted element in the already sorted part of the array by moving larger values to the right. Start at index 1 and loop through the entire array.

The selection sort that you need to know for the exam starts at index 0 and looks through the entire array keeping track of the index of the smallest value in the array and then swaps the value at the smallest index with the value at index 0. Then it does the same thing for index 1, then 2, and so on until it reaches the length of the array minus one. At this point, the array is sorted in ascending order.

public static void selectionSort(int[] elements){
        for (int j = 0; j < elements.length - 1; j++){
            int minIndex = j;
            for (int k = j + 1; k < elements.length; k++) {
                if (elements[k] < elements[minIndex]){
                    minIndex = k;
                }
            }
            int temp = elements[j];
            elements[j] = elements[minIndex];
            elements[minIndex] = temp;
        }
}

The insertion sort that you need to know for the exam starts at index 1 and inserts the value at index 1 into its correct place in the already sorted part (the part to the left of the current index). It moves any value larger than the value stored in temp to the right until it either finds the appropriate place to put temp or gets to the front of the array.

public static void insertionSort(int[] elements){
    for (int j = 1; j < elements.length; j++) {
        int temp = elements[j];
        int possibleIndex = j;
        while (possibleIndex > 0 && temp < elements[possibleIndex - 1]){
            elements[possibleIndex] = elements[possibleIndex - 1];
            possibleIndex--;
        }
        elements[possibleIndex] = temp;
    }
}