Unit 7 Overview: ArrayList

Unit 7 Overview: ArrayList

The Big Takeaway of this Unit

ArrayLists are one of the most versatile data structures in Java, allowing dynamic storage and manipulation of data. Unlike arrays, ArrayLists can grow and shrink as needed, making them ideal for situations where the size of the collection is not predetermined. In this unit, you’ll learn how to create, traverse, and implement algorithms with ArrayLists, as well as explore their applications in searching and sorting.

Exam Weighting

• Weighting: 2.5-7.5% of the test

• Multiple-choice questions: 1 to 2

• FRQ Potential: Likely topic for FRQ #3, focusing on creating ArrayLists and developing ArrayList algorithms.

Enduring Understanding

ArrayLists are a step up from arrays, offering dynamic sizing and a host of methods to manipulate their contents. They are part of the Java Collections Framework, a library of data structures designed for different use cases. Mastering ArrayLists is key to building computational thinking and preparing for more advanced programming concepts.

Main Ideas for this Unit

• Creating ArrayLists

• ArrayList Methods

• Traversing ArrayLists

• ArrayList Algorithms

• Searching: Sequential/Linear Search

• Sorting: Selection Sort and Insertion Sort

7.1 Introduction to ArrayList

An ArrayList is a dynamic data structure that stores items in an ordered list. Unlike arrays, ArrayLists do not have a fixed size, allowing elements to be added or removed as needed. This flexibility makes them highly useful in scenarios where the data size is unknown or subject to change.

Key Features of ArrayLists

1. Dynamic Sizing: Unlike arrays, ArrayLists can grow or shrink dynamically.

2. Mutability: Elements in an ArrayList can be changed after creation.

3. Generic Types: ArrayLists use generics to specify the type of elements they store. For example:

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

   This ensures type safety, reducing runtime errors.

Creating an ArrayList

• Without Initial Capacity:

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

• With Initial Capacity:

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

• Storing Primitive Types: Since ArrayLists only store objects, primitive types like int or double must be wrapped using their corresponding wrapper classes (Integer, Double, etc.).

7.2 ArrayList Methods

The ArrayList class provides various methods to manipulate the list. Below are the most important methods for the AP CSA exam:

Commonly Used Methods

1. size(): Returns the number of elements in the ArrayList.

   int count = list.size();

2. add(E obj): Adds an element to the end of the ArrayList.

   list.add(42);

3. add(int index, E obj): Inserts an element at a specified index, shifting subsequent elements to the right.

   list.add(2, 99);

4. get(int index): Retrieves the element at the specified index.

   int value = list.get(0);

5. set(int index, E obj): Updates the element at the specified index.

   list.set(1, 55);

6. remove(int index): Removes the element at the specified index, shifting subsequent elements to the left.

   list.remove(3);

Import Statement

To use ArrayLists, import the class:

import java.util.ArrayList;

7.3 Traversing ArrayLists

Traversing an ArrayList involves accessing each element in the list. You can traverse using a for loop, a while loop, or an enhanced for loop (for-each loop).

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));
}

Using an Enhanced For Loop

for (Integer number : list) {
    System.out.println(number);
}

Note: Modifying the ArrayList while using a for-each loop can cause a ConcurrentModificationException.

7.4 Developing Algorithms Using ArrayLists

ArrayLists are versatile and support various algorithms, including:

Insert an Element

list.add(2, 50); // Inserts 50 at index 2

Delete an Element

list.remove(3); // Removes the element at index 3

Converting Between Arrays and ArrayLists

ArrayList to 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);
}

Array to ArrayList:

Integer[] array = {1, 2, 3};
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(array));

7.5 Searching

Linear Search Linear search is used to find an element in an ArrayList by iterating through the list sequentially.

public int linearSearch(ArrayList<Integer> list, int target) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == target) {
            return i; // Return index of the target
        }
    }
    return -1; // Return -1 if target is not found
}

7.6 Sorting

Selection Sort

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);
    }
}

Insertion Sort

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);
    }
}

7.7 Ethical Issues Around Data Collection

With the increased use of data, ethical considerations around its collection, storage, and usage have grown significantly. Here are steps programmers can take to ensure ethical data handling:

1. Use Encryption: Protect user data with robust encryption methods.

2. Minimize Data Collection: Only collect data that is absolutely necessary.

3. Implement Strong Security Measures: Use firewalls, authentication systems, and regular audits to prevent data breaches.

4. Be Transparent: Clearly communicate to users what data is being collected and why.

Conclusion

ArrayLists are a dynamic and powerful data structure that offer flexibility and functionality far beyond static arrays. By mastering ArrayList creation, traversal, and algorithm development, you can handle complex data manipulation tasks with ease. Additionally, understanding the ethical considerations around data collection ensures you build trust with your users while protecting their privacy.