The Big Takeaway of this Unit

Exam Weighting

• 2.5-7.5% of the test

• Roughly 1 to 2 multiple-choice questions

• A possible topic of FRQ #3, which may test your ability to make ArrayLists and ArrayList algorithms.

Enduring Understanding

We will now move on to the next data structure in this course, the ArrayList. Unlike the array, ArrayLists don't have a fixed size, and we can add and remove items from them. ArrayLists are part of the Java Collections Framework, which contains different data structures for different purposes. If you decide to learn more about Java in a second course, you will learn all about these data structures!

Building Computational Thinking

ArrayLists are more versatile than arrays in many situations, but there are different methods that must be used to achieve this. Thus, it is important to know the difference between arrays and ArrayLists. Using ArrayLists, we will also learn how to sort and search elements, which are two of the most important applications.

Main Ideas for this Unit 💡

• Creating ArrayLists

• ArrayList Methods

• Traversing ArrayLists

• ArrayList Algorithms

• Searching

  • Sequential/Linear Search

• Sorting

  • Selection Sort

  • Insertion Sort

7.1 Introduction to ArrayList

An ArrayList is a data structure that allows you to store a collection of items in an ordered list. It is similar to an array, but it is dynamic in size, which means you can add or remove items from the list without having to specify the size of the list beforehand.

One of the key features of an ArrayList is its mutability. This means that the elements in the list can be changed after the list is created. For example, you can add or remove elements from the list, or you can change the value of an element at a specific index in the list.

To create an ArrayList, you can use the ArrayList constructor, which takes no arguments:

ArrayList<E> list = new ArrayList<>();

You can also create an ArrayList with a specific initial capacity:

ArrayList<E> list = new ArrayList<>(int initialCapacity);

The generic type E specifies the type of elements that will be stored in the ArrayList. For example, if you want to create an ArrayList that holds integers, you would use the type Integer like this:

ArrayList<Integer> list = new ArrayList<>();

It is important to note that ArrayLists can only store objects, not primitive types (int, boolean, double). This is where the wrapper classes you learned about in Unit 2 come in! In order to add a primitive type to an ArrayList, you must first wrap the primitive type in its wrapper class to turn it into an object.

7.2 ArrayList Methods

The ArrayList class is not part of the standard Java package, so it must be imported into your class so you can use it. This is the import statement you need to write:

import java.util.ArrayList;

Unlike arrays, the ArrayList uses methods to add, remove, and manipulate the list. This is a list of all the methods you need to know to be proficient with ArrayLists for the AP exam:

• int size() -- Returns an integer with the number of elements currently in the list

• boolean add(E obj) -- Appends (adds to the end) obj to the end of the list; returns true if added and false if not

• void add(int index, E obj): This method is used to add an element to the ArrayList at a specified index. The first parameter, index, is the position in the list where the element will be added, and the second parameter, obj, is the element that you want to add to the list. If the index is equal to the size of the list, the element is added at the end of the list. If the index is less than the size of the list, the element is inserted at the specified index, and any elements that were previously at that index or later are shifted one position to the right.

• E get(int index): Used to retrieve an element from the ArrayList at a specified index. The parameter, index, is the position in the list of the element that you want to retrieve. The method returns the element at the specified index, or null if the index is out of bounds.

• E set(int index, E obj): This method updates an element in the ArrayList at a specified index. The first parameter, index, is the position in the list of the element that you want to update, and the second parameter, obj, is the new value of the element. The method returns the element that was previously at the specified index. It throws an exception if the index is out of bounds.

• E remove(int index): This method is used to remove an element from the ArrayList at a specified index. The parameter, index, is the position in the list of the element that you want to remove. The method returns the element that was removed, or null if the index is out of bounds.

7.3 Traversing ArrayLists

The indices of an ArrayList start at 0 and end at size() - 1, so make sure your code only runs within these indices or you will get an IndexOutOfBoundsException.

Like arrays, you can use a for or while loop and an enhanced for loop (for-each loop) to traverse an ArrayList. This is how to traverse an ArrayList using a for loop:

ArrayList<Integer> list = new ArrayList<>();

list.add(1);

list.add(2);

list.add(3);

for (int i = 0; i < list.size(); i++) {

System.out.println(list.get(i));

}

This for loop creates the variable i to store the index of the elements, then uses those indices to access the elements, much like traversing an array. Notice, however, that the get method of the ArrayList is used to retrieve the elements, and that instead of array.length, we are using list.size() to determine the length of the list.

Using an enhanced for loop to traverse through the ArrayList is also possible:

for (Integer number : list) {

System.out.println(number);

}

A ConcurrentModificationException can be thrown if you change the size of the ArrayList while you are using a for-each loop to traverse it. Remember that for-each loops cannot modify the original data structure, so if you try to add or remove elements of an ArrayList with a for-each loop, this exception will be thrown.

7.4 Developing Algorithms Using ArrayLists

ArrayLists have their own versions of the standard algorithms you learned in the last unit with arrays. You need to know how to:

• Insert an element in the ArrayList

• Delete an element

• Turn arrays into ArrayLists and vice versa

• Perform all the standard array algorithms mentioned in the Unit 6 Overview

The code below explains how to turn an ArrayList into an array:

ArrayList<Integer> list = new ArrayList<>();

list.add(1);

list.add(2);

list.add(3);

Integer[] array = new Integer[list.size()];

for (int i = 0; i < list.size(); i++) {

array[i] = list.get(i);

}

In this example, a new Integer array is created with the same size as the ArrayList. A for loop is used to iterate through the elements of the ArrayList, and the elements are added to the array one by one using the array's index, which is stored in the variable i.

7.5 Searching

Linear search, also known as sequential search, is a method for searching an ArrayList for a specific value. The algorithm iterates through the array or list, one element at a time, from the start to the end, until it finds the target element or determines that the element is not present.

You can implement linear search for an ArrayList using a for loop. You would start by iterating through the elements of the ArrayList, one at a time, using the for loop. At each iteration, you would check if the current element is equal to the target element. If it is, you would return the index of that element. If the for loop completes without finding the target element, you would return -1 to indicate that the element was not found.

Linear search is very similar to traversing an ArrayList:

public int linearSearch(ArrayList<Integer> list, int target) {

for (int i = 0; i < list.size(); i++) {

if (list.get(i) == target) {

return i;

}

}

return -1;

}

This function takes an ArrayList of integers and a target integer as input, and returns the index of the target element in the list, or -1 if the element is not found.

7.6 Sorting

Selection sort and insertion sort are two commonly-used sorting algorithms in computer science. Both algorithms can be used to sort an array or an ArrayList.

Selection sort works by repeatedly finding the minimum element from the unsorted portion of the array or list, and then moving it to the sorted portion of the array or list. The algorithm repeatedly selects the smallest element from the unsorted portion of the array and then swaps it with the first element of the unsorted portion. This process is repeated for the remaining unsorted portion of the array or list, which results in the entire array or list being sorted.

Take some time to trace through this code for a selection sort using an ArrayList to build your understanding.

public void selectionSort(ArrayList<Integer> list) {

for (int i = 0; i < list.size(); i++) {

int minIndex = i;

for (int j = i + 1; j < list.size(); j++) {

if (list.get(j) < list.get(minIndex)) {

minIndex = j;

}

}

int temp = list.get(i);

list.set(i, list.get(minIndex));

list.set(minIndex, temp);

}

}

A visual explanation of how selection sort works. GIF courtesy of Make a GIF.

On the other hand, Insertion Sort starts by assuming that the first element of the ArrayList is already sorted, and then it picks the next element and insert it into the correct position in the already sorted portion of the array. The algorithm repeatedly compares an unsorted element with the sorted elements to the left of it, and then shifts the sorted elements to the right to make room for the unsorted element to be inserted into its correct position.

This is the Insertion Sort implemented on a generic ArrayList:

public void insertionSort(ArrayList<Integer> list) {

for (int i = 1; i < list.size(); i++) {

int current = list.get(i);

int j = i - 1;

while (j >= 0 && list.get(j) > current) {

list.set(j + 1, list.get(j));

j--;

}

list.set(j + 1, current);

}

}

A visual explanation of insertion sort. GIF courtesy of Wikimedia.

7.7 Ethical Issues Around Data Collection

The ethical issues around data collection arise from the collection, storage, and use of personal data by companies, organizations, and governments. The sheer volume of data that is being collected, combined with advances in technology that make it easier to store and analyze data, has led to concerns about the potential for misuse of personal data, such as privacy violations and erosions of civil liberties.

As a programmer, there are several steps you can take to safeguard your users' personal privacy:

• Use encryption when handling personal data: Encryption is the process of converting plain text into a code to protect the data from unauthorized access. 🔐

• Be careful about what data you collect: only collect the data that is truly necessary for your application, and consider the potential risks associated with each type of data.

• Implement security measures like firewalls, intrusion detection and prevention systems, and authentication and access controls, to protect personal data from unauthorized access or theft.

• Be transparent with users about data collection and usage: Be upfront with users about what data you are collecting, why you are collecting it, and how you plan to use it. This helps to build trust with users and also help them to make more informed decisions about the data they share. 🤝