AP Computer Science A: Arrays and ArrayLists

Mastering arrays and ArrayLists is non-negotiable for the AP Computer Science A exam. These fundamental data structures are your primary tools for storing and managing collections of data, forming the backbone for countless algorithms and problem-solving scenarios you will encounter both on the test and in real-world programming. Understanding their declaration, traversal, and manipulation is key to writing efficient, effective Java code.

Understanding the Foundation: Arrays

An array is a fixed-size, ordered collection of elements of the same data type. Think of it like a series of identical, numbered lockers in a row; once the row is built, you cannot add or remove lockers, but you can place or retrieve an item from any specific locker if you know its number.

Declaring and initializing an array involves two key steps. First, you declare the array variable, which creates a reference that can point to an array object. Second, you initialize it, which actually creates the array object in memory and, optionally, fills it with values.

// Declaration - `scores` can reference an array of integers
int[] scores;

// Initialization with size - creates an array of 5 integers, all set to 0
scores = new int[5];

// Combined declaration and initialization with size
String[] names = new String[10];

// Initialization with pre-defined values
int[] primes = {2, 3, 5, 7, 11};

A critical concept is array indexing, which is zero-based. This means the first element is at index 0, the second at index 1, and so on. The last index is always one less than the array's .length property. Accessing or modifying an element uses bracket notation: scores[0] = 95;.

Introducing Flexibility: The ArrayList

While arrays are fixed in size, an ArrayList is a resizable, object-oriented collection found in the java.util package. Imagine it as a dynamic list on a notepad; you can easily add lines, remove lines, or insert a line anywhere, and the notepad manages the space for you.

Declaring and initializing an ArrayList requires specifying the type of object it will hold using angle brackets <>, known as generics. A key difference from arrays is that ArrayList can only hold object types (like String, Integer), not primitive types (like int, double). You must use the corresponding wrapper class (e.g., Integer for int).

import java.util.ArrayList;

// Declaration and initialization
ArrayList<String> words = new ArrayList<String>();

// Adding elements
words.add("Hello");
words.add("World");

// For primitive types, use the wrapper class
ArrayList<Integer> numberList = new ArrayList<Integer>();
numberList.add(7); // Auto-boxing converts int 7 to Integer 7

The ArrayList class provides powerful methods like .add(element), .add(index, element), .remove(index), .set(index, element), and .get(index) to manipulate the list. Its size is dynamic and can be found using the .size() method.

Traversing Collections: Loops in Action

To process every element in an array or ArrayList, you must traverse it. You have two main loop structures at your disposal.

The standard for loop gives you explicit control over the index, which is essential when you need to know the position of an element, such as when modifying values or comparing adjacent items.

// Traversing an array with a for loop
int[] values = {10, 20, 30, 40};
for (int i = 0; i < values.length; i++) {
    values[i] = values[i] * 2; // Double each value
}

// Traversing an ArrayList with a for loop
ArrayList<Double> temps = new ArrayList<Double>();
// ... list is populated
for (int i = 0; i < temps.size(); i++) {
    Double current = temps.get(i);
    // Process current
}

The enhanced for loop (or "for-each" loop) provides a simpler syntax for when you only need to access each element's value in order, without needing to modify the underlying collection's structure.

// Traversing an array with an enhanced for loop
for (int val : values) {
    System.out.println(val); // Prints each value
}

// Traversing an ArrayList with an enhanced for loop
for (String name : namesList) {
    System.out.println(name.toUpperCase());
}

A crucial exam tip: you cannot use an enhanced for loop to modify the elements of an array of primitive types. The loop variable is a copy. However, you can modify the state of objects within an array or ArrayList of objects.

Implementing Common Array Algorithms

The AP exam consistently tests your ability to implement standard algorithms on arrays and ArrayLists. These patterns are building blocks for more complex programs.

Finding a Maximum or Minimum Value: This algorithm initializes a tracker variable to the first element and then traverses the collection, updating the tracker whenever a larger (for max) or smaller (for min) value is found.

// Find the maximum value in an array `data`
int max = data[0];
for (int i = 1; i < data.length; i++) {
    if (data[i] > max) {
        max = data[i];
    }
}

Computing an Average (Mean): This requires calculating the sum of all elements and then dividing by the number of elements. Be mindful of integer division; if the sum and count are integers, you may need to cast one to a double to get a precise result.

double sum = 0.0;
for (int num : dataArray) {
    sum += num;
}
double average = sum / dataArray.length;

Counting Occurrences: Traverse the collection and increment a counter each time a target value is found.

int count = 0;
for (String item : itemList) {
    if (item.equals(target)) { // Use .equals() for String comparison!
        count++;
    }
}

Searching for a Value: A linear search checks each element sequentially until the target is found or the end is reached. It's versatile and works on unsorted data. You'll often see it used to determine if a value exists or to find its first index.

// Returns the index of target, or -1 if not found
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Inserting and Removing Elements: For an ArrayList, this is straightforward using the .add(index, element) and .remove(index) methods. For a standard array, these operations are more involved because you must manually shift elements to open a space for an insert or to close a gap left by a removal. This shifting is a classic exam task.

// Remove the element at index `pos` from an array `arr`
for (int i = pos; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1]; // Shift each element one to the left
}
// The last element becomes duplicated. Often, we track logical size separately.

Common Pitfalls

1. Off-by-One Errors and ArrayIndexOutOfBoundsException: The most common error is accessing index arr.length. Remember, valid indices run from 0 to arr.length - 1. Always check your loop conditions. In an enhanced for loop, you avoid this error entirely, which is a key benefit.

• Correction: Use i < array.length as your loop condition, not i <= array.length.

1. Forgetting That ArrayList Stores Objects, Not Primitives: You cannot declare ArrayList<int>. This will cause a compilation error.

• Correction: Use the wrapper classes: ArrayList<Integer>, ArrayList<Double>, etc.

1. Using == to Compare Strings (or Objects) in a Collection: The == operator compares object references (memory addresses), not content. Two different String objects with the same text are not ==.

• Correction: Always use the .equals() method to compare the content of objects: if (myString.equals(targetString)).

1. Confusing ArrayList Size with Array Length: An array uses the public field .length. An ArrayList uses the method .size().

• Correction: Use the correct syntax: for (int i = 0; i < myList.size(); i++).

Summary

• Arrays are fixed-size collections of a single type, accessed by a zero-based index using bracket notation (arr[i]). Their length is fixed and found using the .length field.
• ArrayLists are dynamic, object-oriented collections from java.util. They only hold object types (requiring wrapper classes for primitives) and are manipulated using methods like .add(), .remove(), and .get(). Their size is found using the .size() method.
• Traversal is done with a standard for loop (when you need the index) or an enhanced for loop (for simple, sequential access to values).
• Standard Algorithms like finding max/min, computing average, counting occurrences, and linear search are fundamental patterns tested on the AP exam. Practice implementing them on both arrays and ArrayLists.
• Shifting Elements is a manual process required for insertion and removal in standard arrays, a common source of algorithmic questions.