ArrayList Traversals - AP Computer Science A

SECTION 1

Historical Context & Motivation

Long before Java's ArrayList class existed, programmers relied on fixed-size arrays to store collections of data. While arrays offered fast index-based access, their rigid capacity created a persistent headache: any insertion or deletion required manual shifting of elements and tedious bookkeeping of the current logical size. The desire for a resizable, indexed collection with built-in traversal support drove the evolution of list data structures across multiple programming languages.

1972 • C Arrays & Manual Loops

The C language formalized index-based array traversal with the classic for-loop idiom, establishing patterns still visible in Java today.

1998 • Java Collections Framework

Java 2 (JDK 1.2) introduced the Collections Framework, including java.util.ArrayList, giving developers a resizable list backed by a growable internal array.

2004 • Generics & Enhanced For

Java 5 added generics (ArrayList<E>) and the enhanced for-each loop, dramatically simplifying type-safe traversal code.

2014 • Streams & Lambdas

Java 8 introduced the Stream API and lambda expressions, enabling functional-style traversals—though these remain outside the AP subset.

The central question this lesson addresses is straightforward yet nuanced: how do you visit every element in an ArrayList correctly, efficiently, and without introducing subtle bugs—especially when elements may be added or removed mid-traversal? Mastering these patterns is essential because the AP Computer Science A exam tests traversal fluency in both multiple-choice and free-response questions.

SECTION 2

Core Principles & Definitions

An ArrayList traversal is the systematic process of visiting each element in the list exactly once (or, in some patterns, conditionally skipping elements). Understanding traversals requires a firm grasp of several foundational ideas that govern how Java's ArrayList behaves under iteration.

Zero-Based Indexing

ArrayList elements are indexed from 0 through size() − 1. An off-by-one error on the upper bound is the single most common traversal bug.

Dynamic Size

Unlike arrays, an ArrayList's size() can change during traversal when elements are added or removed, requiring special care in loop bounds.

Two Loop Idioms

The AP subset emphasizes two traversal patterns: the indexed for loop (full control over index) and the enhanced for-each loop (concise, read-only access).

ConcurrentModificationException

Modifying the ArrayList's structure (add/remove) during a for-each loop causes a runtime exception. Indexed loops with careful index adjustment are the safe alternative.

SECTION 3

Visual Explanation

The diagram shows each iteration of an indexed for-loop over a five-element ArrayList. The variable i advances from 0 to 4, and the loop terminates when i reaches size() (5).

The diagram above illustrates the most fundamental ArrayList traversal: an indexed for loop. Notice that the guard condition uses the strict less-than operator (<) rather than <=. Using <= would attempt get(5) on a five-element list, triggering an IndexOutOfBoundsException. This off-by-one pitfall is one of the most commonly tested concepts on the AP exam, appearing in both standalone MCQ questions and as part of larger FRQ solutions.

SECTION 4

How ArrayList Traversals Work

Pattern 1 — Indexed for Loop

The indexed for loop gives you explicit control over the loop variable. The canonical form is:

INDEXED FOR LOOP

for (int i = 0; i < list.size(); i++) { Type elem = list.get(i); // process elem }

i — current index; list.size() — evaluated each iteration (important when removing); get(i) — O(1) random access

Because list.size() is re-evaluated on every iteration, this pattern naturally adapts when you remove elements during traversal. However, after calling list.remove(i), the element that was at index i + 1 shifts down to index i. If you then increment i as usual, you skip that shifted element. The fix: decrement i after a removal, or traverse backward from size() − 1 down to 0.

Pattern 2 — Enhanced for-each Loop

FOR-EACH LOOP

for (Type elem : list) { // process elem (read-only) }

elem — a copy of the reference at each position; modifying the list's structure (add/remove) during this loop throws ConcurrentModificationException

The enhanced for-each loop is syntactic sugar over an Iterator. It is the preferred idiom when you need only read access to every element and do not need the index. It produces cleaner code and eliminates the risk of off-by-one index errors. The trade-off is that you cannot modify the list's structure (no add or remove calls) without triggering a runtime exception.

Pattern 3 — While Loop Traversal

WHILE LOOP

int i = 0; while (i < list.size()) { if (shouldRemove(list.get(i))) { list.remove(i); } else { i++; } }

Index increments only when no removal occurs, preventing the skip-after-remove bug.

ℹ

AP Exam Tip

SECTION 5

Common Traversal Patterns & Pitfalls

Beyond simple element access, ArrayList traversals appear in several recurring algorithmic patterns on the AP exam. Understanding these patterns will help you recognize which loop idiom to use and how to avoid the classic pitfalls that examiners love to exploit.

Left: a forward traversal with unconditional i++ skips the second "X" after removal. Right: a backward traversal naturally avoids this because the shifting only affects indices already visited.

Pattern	Best Loop Idiom	Key Detail
Sum / Average	for-each	Accumulator variable initialized before loop; divide by size() after
Search (find first match)	Indexed for or while	Return index or element immediately on match; return −1 / null after loop
Count occurrences	for-each	No modification needed; counter++ when condition met
Remove all matches	Backward for or while	Never use for-each; must handle index shift
Simultaneous comparison (adjacent pairs)	Indexed for (i < size()−1)	Compare get(i) with get(i+1); upper bound is size()−1 to avoid IOOBE

Common AP exam traversal patterns and the recommended loop idiom for each.

SECTION 6

Worked Example

Consider the following problem, which mirrors a typical AP FRQ task: given an ArrayList<Integer> called scores containing [85, 42, 97, 38, 74, 55], remove all values below 50 and return the average of the remaining scores.

Worked example

1
Step 1 — Choose the Right Loop Pattern

Because we must remove elements during traversal, the for-each loop is off-limits. We select a backward indexed for loop to avoid the shift-and-skip bug.
2
Step 2 — Write the Removal Loop

for (int i = scores.size() - 1; i >= 0; i--) — inside the loop body: if (scores.get(i) < 50) { scores.remove(i); }

After loop: scores = [85, 97, 74, 55]
3
Step 3 — Trace the Removal

i=5: 55 ≥ 50 → keep. i=4: 74 ≥ 50 → keep. i=3: 38 < 50 → remove → [85, 42, 97, 74, 55]. i=2: 97 ≥ 50 → keep. i=1: 42 < 50 → remove → [85, 97, 74, 55]. i=0: 85 ≥ 50 → keep.

Remaining list: [85, 97, 74, 55]
4
Step 4 — Compute the Average with a for-each Loop

Now that no structural modification is needed, a for-each loop is safe: int sum = 0; for (int s : scores) { sum += s; }. Then double avg = (double) sum / scores.size();

sum = 311; avg = 311.0 / 4 = 77.75

ℹ

Why Not a Forward While Loop?

SECTION 7

Comparing Traversal Approaches

Feature	Indexed for Loop	Enhanced for-each
Access to index	Yes — i is available	No — index hidden
Can add/remove elements	Yes (with care)	No — throws ConcurrentModificationException
Risk of off-by-one error	Higher — manual bounds	None — automatic bounds
Code conciseness	Moderate	Very concise
Can traverse backward	Yes	No
AP exam frequency	Very high (FRQs especially)	High (MCQ and simple FRQs)

Indexed for loop vs. enhanced for-each loop comparison

★

Key takeaway

DECISION RULE

SECTION 8

Connection to Advanced Concepts

ArrayList traversal mastery lays the groundwork for several topics you will encounter in data structures courses and professional development. The table below maps each AP-level concept to its more advanced counterpart, giving you a roadmap for future study.

AP Concept	Advanced Extension
Indexed for loop over ArrayList	Iterator and ListIterator patterns; fail-fast vs. fail-safe iterators in concurrent collections
Remove-during-traversal	Iterator.remove() — the only safe structural modification during iteration in the general Collections API
For-each loop	Java Streams (map, filter, reduce) — functional-style traversal with lazy evaluation
Linear search during traversal	Binary search on sorted lists; hash-based O(1) lookups with HashMap

The Iterator design pattern (from the Gang of Four) is precisely what the enhanced for-each loop uses under the hood. When you write for (String s : list), the compiler translates it into an Iterator-based while loop. Understanding this connection will help you reason about why structural modifications cause a ConcurrentModificationException and why Iterator.remove() is the sanctioned escape hatch in post-AP Java programming.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Which of the following is a valid reason to prefer an indexed for loop over an enhanced for-each loop when traversing an ArrayList?

A. The indexed for loop runs faster because get(i) is O(log n).
B. The indexed for loop allows you to remove elements during traversal without throwing an exception.
C. The enhanced for-each loop cannot access elements of type Integer due to autoboxing limitations.
D. The enhanced for-each loop does not iterate in index order.

Show answer (B)

B is correct. An indexed for loop allows structural modifications (add/remove) with proper index management, whereas the enhanced for-each loop throws a ConcurrentModificationException on such modifications. A is wrong because ArrayList.get(i) is O(1), not O(log n). C is wrong because autoboxing works seamlessly with for-each and Integer. D is wrong because the for-each loop iterates in index order (0, 1, 2, …).

Question 2: BASIC CALCULATION

Consider the following code:

ArrayList<Integer> nums = new ArrayList<>();
nums.add(10); nums.add(20); nums.add(30);
int total = 0;
for (int n : nums) { total += n; }
System.out.println(total);

What is printed?

A. 0
B. 30
C. 60
D. An IndexOutOfBoundsException is thrown

Show answer (C)

C is correct. The for-each loop visits 10, 20, and 30 in order, accumulating total = 10 + 20 + 30 = 60. A is wrong because total is updated inside the loop. B is wrong—that would be only the last element. D is wrong because the for-each loop handles bounds automatically.

Question 3: INTERMEDIATE

What does the following code print?

ArrayList<String> words = new ArrayList<>();
words.add("A"); words.add("A"); words.add("B"); words.add("C");
for (int i = 0; i < words.size(); i++) {
    if (words.get(i).equals("A")) {
        words.remove(i);
    }
}
System.out.println(words);

A. [B, C]
B. [A, B, C]
C. [A, A, C]
D. A ConcurrentModificationException is thrown

Show answer (B)

B is correct. This problem demonstrates the classic "skip-after-remove" bug when removing elements during a forward ArrayList traversal. Start: [A, A, B, C]. i=0: get(0) is "A" → remove(0) → list becomes [A, B, C], i increments to 1. The second "A" shifted down to index 0, but i has already moved past it, so it is skipped. i=1: get(1) is "B" → not "A", no removal, i increments to 2. i=2: get(2) is "C" → not "A", no removal, i increments to 3. i=3: 3 ≥ size() (3) → loop exits. Final list: [A, B, C]. Because the two A's are adjacent, removing the first causes the second to shift into the vacated index 0, but i has already incremented past it. This is the well-known pitfall of removing elements during a forward indexed traversal: shifted elements can be skipped. A is wrong because it assumes both A's are successfully removed. C is wrong because "B" is never removed. D is wrong because ConcurrentModificationException applies to structural modification during enhanced for-each loops, not standard indexed for loops.

Question 4: APPLIED

Write a method removeDuplicates that takes an ArrayList<String> as a parameter and modifies it so that only the first occurrence of each string remains. The relative order of the remaining elements must be preserved. For example, if the list is ["a", "b", "a", "c", "b"], after the call it should be ["a", "b", "c"]. You may use an additional ArrayList for bookkeeping.

Show answer

Sample solution:

public static void removeDuplicates(ArrayList<String> list) {
    ArrayList<String> seen = new ArrayList<>();
    int i = 0;
    while (i < list.size()) {
        if (seen.contains(list.get(i))) {
            list.remove(i);
        } else {
            seen.add(list.get(i));
            i++;
        }
    }
}

Rubric point 1 (1 pt): The while loop with condition i < list.size() correctly traverses the list. Point 2 (1 pt): seen.contains(list.get(i)) checks for prior occurrence. Point 3 (1 pt): list.remove(i) removes the duplicate. Point 4 (1 pt): i is only incremented in the else branch, preventing the skip-after-remove bug. Point 5 (1 pt): Because we always keep the first occurrence (adding to seen) and remove later duplicates, relative order is preserved.

Question 5: CRITICAL THINKING

A student writes the following code to compute the sum of all even integers in an ArrayList<Integer> called vals:

int sum = 0;
for (int i = 1; i <= vals.size(); i++) {
    if (vals.get(i) % 2 == 0) {
        sum += vals.get(i);
    }
}

(a) Identify two distinct bugs in this code. (b) Provide corrected code.

Show answer

(a) Bug 1: The loop starts at i = 1, so the element at index 0 is never checked. If vals.get(0) is even, it is erroneously excluded from the sum. Bug 2: The condition i <= vals.size() means the loop runs when i equals vals.size(). Since valid indices are 0 through size()−1, vals.get(vals.size()) throws an IndexOutOfBoundsException. (b) Corrected code:

int sum = 0;
for (int i = 0; i < vals.size(); i++) {
    if (vals.get(i) % 2 == 0) {
        sum += vals.get(i);
    }
}