AP CSA Unit 4 ArrayLists: Dynamic Lists, Traversal, and List-Based Algorithms

Wrapper Classes: Integer and Double

In Java, primitive types like int and double store raw numeric values directly. They’re fast and simple—but they are not objects. An object (like a String) can be stored in many Java library data structures, can have methods, and fits into Java’s “reference type” world.

An ArrayList is designed to store objects, not primitives. This matters because ArrayLists use generics—type parameters like ArrayList<E>—and generic types in Java must be reference types (classes), not primitives.

That’s where wrapper classes come in:

• Integer “wraps” an int value inside an object.
• Double “wraps” a double value inside an object.

So if you want an ArrayList of whole numbers, you write ArrayList<Integer>, not ArrayList<int>.

Why wrapper classes matter in ArrayLists

ArrayLists are resizable collections of elements. The Java library needs every element to behave consistently like an object (for things like null, method calls, and generics). Wrapper classes make numeric values compatible with that object-based system.

This comes up constantly in AP CSA because many problems want a “list of scores,” “list of temperatures,” “list of counts,” etc.—and those are naturally numeric.

Autoboxing and unboxing (how primitives and wrappers interact)

Java helps you by automatically converting between primitives and their wrapper objects when it can.

• Autoboxing: converting a primitive to its wrapper automatically.
  • Example: int to Integer
• Unboxing: converting a wrapper to its primitive automatically.
  • Example: Integer to int

This allows code like this to work smoothly even though nums stores Integer objects:

import java.util.ArrayList;

public class Demo {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();

        nums.add(7);        // autoboxing: 7 (int) becomes Integer.valueOf(7)
        int x = nums.get(0); // unboxing: Integer becomes int

        nums.set(0, x + 5); // x + 5 is int, autoboxed into Integer
        System.out.println(nums); // [12]
    }
}

You don’t need to write Integer.valueOf(...) or intValue() for AP-style code most of the time, but understanding what’s happening prevents confusion.

What can go wrong with wrappers

Wrapper classes introduce a few pitfalls:

1. null values: An ArrayList can store null because it stores references. If you unbox null, Java throws a NullPointerException.

   ArrayList<Integer> a = new ArrayList<Integer>();
   a.add(null);
   int n = a.get(0); // NullPointerException due to unboxing null

2. Comparing wrapper objects: == compares references for objects, not value equality.
   • For value comparison, use .equals(...).

   Integer a = 1000;
   Integer b = 1000;
   System.out.println(a == b);      // could be false
   System.out.println(a.equals(b)); // true

3. Precision with Double: Double wraps a double, so it inherits floating-point precision limitations. Two values that “should” be equal might not be exactly equal due to rounding.

Exam Focus

• Typical question patterns:
  • Identify the correct type for an ArrayList of numbers (e.g., ArrayList<Integer> vs ArrayList<int>).
  • Predict output that involves adding/getting numeric values from an ArrayList (autoboxing/unboxing).
  • Reason about null elements or comparisons using .equals.
• Common mistakes:
  • Writing ArrayList<int> or ArrayList<double> (generics require reference types).
  • Using == to compare Integer/Double values instead of .equals.
  • Unboxing a null element (causing NullPointerException).

ArrayList Methods

An ArrayList is a resizable list structure from java.util. You can think of it like an array that can grow and shrink automatically, while still providing indexed access (positions 0, 1, 2, …). Unlike arrays, an ArrayList’s size can change during program execution.

To use it, you typically import and declare it like this:

import java.util.ArrayList;

ArrayList<String> words = new ArrayList<String>();

The type parameter (String here) tells Java what kind of elements the list holds. This gives you type safety: you can’t accidentally add an Integer into an ArrayList<String>.

Indexing rules (why off-by-one errors happen)

ArrayLists are zero-indexed:

• The first element is at index 0.
• The last element is at index size() - 1.

Trying to access an invalid index throws an IndexOutOfBoundsException.

Core methods you must know

The AP CSA ArrayList questions typically focus on a small set of core methods. These are the ones you should be fluent with:

(Other methods exist in the Java API, like contains, indexOf, and clear, but the core ones above are the most consistently tested.)

How insertion and removal really work (the shifting effect)

ArrayLists maintain elements in order. When you insert or remove in the middle, everything after the index must “slide” to fill the gap or make room.

• add(index, obj) shifts existing elements at index and beyond right.
• remove(index) shifts elements after index left.

This shifting is why index-based loops can behave unexpectedly if you modify the list while traversing.

Examples: add, get, set, remove, size

import java.util.ArrayList;

public class ListOps {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<String>();

        names.add("Ada");      // [Ada]
        names.add("Grace");    // [Ada, Grace]
        names.add(1, "Linus"); // insert at index 1 -> [Ada, Linus, Grace]

        System.out.println(names.get(2)); // Grace

        String old = names.set(0, "Alan");
        System.out.println(old);   // Ada
        System.out.println(names); // [Alan, Linus, Grace]

        String removed = names.remove(1);
        System.out.println(removed); // Linus
        System.out.println(names);   // [Alan, Grace]

        System.out.println(names.size()); // 2
    }
}

A note on remove with numbers (index vs value)

This is a classic ArrayList confusion when using ArrayList<Integer>.

• remove(int index) removes by position.
• There is also an overload remove(Object obj) that removes by value.

But with ArrayList<Integer>, an int argument looks like an index, so Java chooses remove(int).

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(10);
nums.add(20);
nums.add(30);

nums.remove(1); // removes index 1 (value 20), list becomes [10, 30]

If you wanted to remove the value 20, you would need to pass an Integer object:

nums.remove(Integer.valueOf(20)); // removes the first occurrence of 20

This overload behavior is a frequent AP CSA “gotcha.”

Exam Focus

• Typical question patterns:
  • Trace code that uses add, add(index, ...), set, and remove, predicting the final list.
  • Determine the value returned by set or remove.
  • Identify what happens (and why) when an index is out of bounds.
• Common mistakes:
  • Forgetting that add(index, ...) and remove(index) shift elements (leading to wrong tracing).
  • Confusing size() with the last index (size() is not a valid index).
  • With ArrayList<Integer>, calling remove(2) thinking it removes the value 2 (it removes index 2).

Traversing ArrayLists

Traversing an ArrayList means visiting its elements—usually to compute something (like a sum), search for a value, count matches, or modify elements. Traversal is where ArrayLists become powerful: you combine a simple loop with method calls like get, set, and remove to implement real algorithms.

There are two main traversal styles you’re expected to use in AP CSA:

1. Index-based traversal with a regular for loop
2. Enhanced for loop traversal (also called “for-each”)

Which one you choose depends on whether you need the index and whether you plan to modify the list structure (add/remove).

Index-based for loop traversal

An index-based loop gives you direct control over positions.

for (int i = 0; i < list.size(); i++) {
    // use i and list.get(i)
}

This matters when:

• You need the index (e.g., “replace every 3rd element”).
• You need to use set(i, ...).
• You want to remove elements safely by iterating backwards.

Example: doubling all values in an ArrayList<Integer>

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(3);
nums.add(5);
nums.add(8);

for (int i = 0; i < nums.size(); i++) {
    nums.set(i, nums.get(i) * 2);
}
System.out.println(nums); // [6, 10, 16]

Notice the pattern: get reads the current value, then set writes back a replacement.

Enhanced for loop traversal

The enhanced for loop is simpler to read:

for (String s : words) {
    // s is each element
}

This is great when you only need to read elements (like counting or summing). It’s also less error-prone because you don’t manage indices.

Example: counting strings longer than 4 characters

int count = 0;
for (String s : words) {
    if (s.length() > 4) {
        count++;
    }
}

A key limitation: you generally should not add/remove elements from the list while using an enhanced for loop. In standard Java, that often triggers a ConcurrentModificationException. On the AP exam, the safe rule is: use enhanced for for reading; use index-based loops for modifications.

Traversal while removing elements (the shifting trap)

Removing elements changes indices. If you loop forward and remove at index i, the element that used to be at i+1 shifts into index i. If your loop then increments i, you skip checking that shifted element.

Example of a buggy pattern:

for (int i = 0; i < nums.size(); i++) {
    if (nums.get(i) == 0) {
        nums.remove(i);
    }
}

If there are consecutive zeros, you’ll likely skip some.

Two common safe patterns

Pattern A: Traverse backwards when removing

for (int i = nums.size() - 1; i >= 0; i--) {
    if (nums.get(i) == 0) {
        nums.remove(i);
    }
}

Going backwards means that removing an element doesn’t affect the indices you haven’t visited yet.

Pattern B: Only increment when you don’t remove

int i = 0;
while (i < nums.size()) {
    if (nums.get(i) == 0) {
        nums.remove(i); // stay at same i to check the shifted element
    } else {
        i++;
    }
}

This pattern is especially useful when the removal condition is complex.

Choosing the right traversal approach

A practical way to decide:

• If you are only reading values: enhanced for loop is usually best.
• If you need indices or must set elements: index-based for loop.
• If you must remove (or insert) elements during traversal: index-based, typically backwards or with a while.

Exam Focus

• Typical question patterns:
  • Determine the output of a loop that traverses a list and uses get, set, or remove.
  • Choose which traversal style is appropriate for a given task.
  • Identify why a loop that removes items skips elements and how to fix it.
• Common mistakes:
  • Using i <= list.size() instead of i < list.size() (out-of-bounds).
  • Removing while traversing forward without accounting for shifting (skips elements).
  • Attempting structural modifications (add/remove) inside an enhanced for loop.

Developing Algorithms Using ArrayLists

An algorithm is a step-by-step process for solving a problem. With ArrayLists, most AP CSA algorithms fall into a few themes:

• Searching: find whether something exists, or where it occurs
• Counting/accumulating: totals, averages, number of matches
• Filtering: remove or keep elements based on a condition
• Transforming: update each element (curve grades, clamp values, normalize strings)

What makes ArrayList algorithms different from array algorithms is that the list can change size while you work—powerful, but it adds complexity when removing/inserting.

Accumulation algorithms: sum and average

A common pattern is building a running total.

Example: average of an ArrayList<Integer>

public static double average(ArrayList<Integer> nums) {
    if (nums.size() == 0) {
        return 0.0; // choice: avoid division by zero
    }

    int sum = 0;
    for (int n : nums) {
        sum += n; // unboxing happens here
    }
    return (double) sum / nums.size();
}

Two subtle points:

• If you do sum / nums.size() with both as int, Java does integer division. Casting to double ensures a decimal result.
• The enhanced for loop is ideal here because you’re only reading values.

Searching algorithms: find the first match

Searching means scanning until you find what you want.

Example: return the index of the first negative number, or -1 if none.

public static int firstNegativeIndex(ArrayList<Integer> nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums.get(i) < 0) {
            return i;
        }
    }
    return -1;
}

Why return -1? Because it’s not a valid index, so it’s a standard “not found” signal.

Filtering algorithms: remove elements that match a condition

Filtering is where you must be careful about shifting. A classic AP task is: “remove all values less than 10” or “remove all strings containing ‘a’.”

Example: remove all even numbers

public static void removeEvens(ArrayList<Integer> nums) {
    for (int i = nums.size() - 1; i >= 0; i--) {
        if (nums.get(i) % 2 == 0) {
            nums.remove(i);
        }
    }
}

This uses backward traversal to avoid skipping elements.

Real-world analogy: Imagine a line of people (the list). If you remove someone from the middle, everyone behind them steps forward. If you’re walking forward counting positions, your “position numbers” stop matching the same people—unless you account for the shift.

Transformation algorithms: update elements in place

Sometimes you want to modify each element but keep the same size.

Example: add a 5-point curve to each score, but cap at 100

public static void curveScores(ArrayList<Integer> scores) {
    for (int i = 0; i < scores.size(); i++) {
        int newScore = scores.get(i) + 5;
        if (newScore > 100) {
            newScore = 100;
        }
        scores.set(i, newScore);
    }
}

This is a “map” style algorithm: each input element becomes a new value.

Working with Strings in ArrayLists (common on AP)

AP CSA often mixes ArrayLists with String processing. Typical tasks include counting based on length(), checking substrings, or standardizing formatting.

Example: count how many strings start with a prefix

public static int countStartingWith(ArrayList<String> words, String prefix) {
    int count = 0;
    for (String w : words) {
        if (w.startsWith(prefix)) {
            count++;
        }
    }
    return count;
}

Removing duplicates (algorithmic thinking with nested loops)

A more advanced pattern uses nested loops to compare elements.

Example: remove later duplicates so each value appears once (preserving first occurrence)

public static void removeDuplicates(ArrayList<String> words) {
    for (int i = 0; i < words.size(); i++) {
        for (int j = words.size() - 1; j > i; j--) {
            if (words.get(j).equals(words.get(i))) {
                words.remove(j);
            }
        }
    }
}

Why does the inner loop go backwards? Because it’s removing items, and backward removal avoids index issues. Also notice .equals(...) for String comparison—another frequent AP expectation.

Insertion algorithms: building a list in order

Sometimes you insert into a particular position rather than just appending.

Example: insert a value into a sorted (ascending) ArrayList<Integer>

public static void insertSorted(ArrayList<Integer> sorted, int value) {
    int i = 0;
    while (i < sorted.size() && sorted.get(i) < value) {
        i++;
    }
    sorted.add(i, value);
}

This algorithm demonstrates a key ArrayList advantage: inserting at an index is built-in. The tradeoff is that insertion can be slower than appending because of shifting.

Common AP free-response style reasoning with ArrayLists

On free-response questions, you’re often asked to implement a method that:

• Takes an ArrayList parameter
• Traverses it with a loop
• Uses get, set, remove, size
• Returns a computed value or modifies the list

When writing these methods, focus on:

• Correct loop bounds (0 to size() - 1)
• Correct use of .equals for object comparison
• A safe removal strategy if the list size changes

Exam Focus

• Typical question patterns:
  • Write or complete a method that counts, sums, searches, or filters elements in an ArrayList.
  • Trace an algorithm that modifies a list (especially remove or set) and determine final contents.
  • Implement a common pattern like “remove all matching elements” or “insert in the right position.”
• Common mistakes:
  • Integer division when computing averages (forgetting to cast to double).
  • Using == instead of .equals for Strings (and sometimes wrapper objects).
  • Removing elements while looping forward and unintentionally skipping items (fix with backward traversal or a while).