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.
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.
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
0 through size() − 1. An off-by-one error on the upper bound is the single most common traversal bug.Dynamic Size
size() can change during traversal when elements are added or removed, requiring special care in loop bounds.Two Loop Idioms
for loop (full control over index) and the enhanced for-each loop (concise, read-only access).ConcurrentModificationException
Visual Explanation
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.
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:
i — current index; list.size() — evaluated each iteration (important when removing); get(i) — O(1) random accessBecause 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
elem — a copy of the reference at each position; modifying the list's structure (add/remove) during this loop throws ConcurrentModificationExceptionThe 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
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.
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 |
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.
for (int i = scores.size() - 1; i >= 0; i--) — inside the loop body: if (scores.get(i) < 50) { scores.remove(i); }int sum = 0; for (int s : scores) { sum += s; }. Then double avg = (double) sum / scores.size();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) |
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.
Practice Problems
for loop over an enhanced for-each loop when traversing an ArrayList?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?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);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.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.