Historical Context & Motivation
Before languages offered built-in resizable collections, programmers managed dynamic data by manually allocating arrays, copying elements, and tracking size counters—a tedious and error-prone process. The need for algorithmic patterns over dynamic lists became apparent as software systems grew beyond trivial data sizes. Java's introduction of the ArrayList class in the Collections Framework (Java 1.2, 1998) gave developers a standard abstraction that handles resizing internally, but the responsibility for writing correct traversal, insertion, removal, and search algorithms still falls squarely on the programmer.
The central question this lesson addresses is: given a dynamically sized list of objects, how do you correctly and efficiently traverse, search, filter, and transform that list without introducing off-by-one errors, skipping elements during removal, or causing ConcurrentModificationException? These are the exact pitfalls that the AP exam tests repeatedly.
Core Principles & Definitions
An ArrayList is a generic, resizable-array implementation of the List interface. Unlike a primitive array whose length is fixed at construction, an ArrayList grows and shrinks as elements are added or removed. All ArrayList algorithms on the AP exam rely on a small set of methods: size(), get(int index), set(int index, E element), add(E element), add(int index, E element), and remove(int index).
Indexed Traversal
for loop with an index variable. Required when you need to add or remove elements during iteration, because the index can be adjusted to compensate for shifts.Enhanced For-Each Traversal
for (Type elem : list) loop reads every element without exposing the index. It is concise but must not be used when the list's size changes during iteration.Insertion & Shifting
add(i, elem) shifts every element at index i and above one position to the right, increasing size by 1. This is O(n) in the worst case.Removal & Index Adjustment
remove(i) shifts elements left and decreases size by 1. If you advance the index after removal, you skip the element that shifted into position i.Linear Search
Visual Explanation — Traversal & Removal
i after a removal causes the second "B" to shift into position 1, but i has already advanced to 2, skipping it. The bottom half shows the correct fix—only increment i in the else branch, or traverse backwards.This diagram illustrates the single most common ArrayList bug tested on the AP exam. When you call remove(i), every element to the right of index i shifts one position to the left, and size() decreases by one. If your loop blindly increments i after the removal, the element that just shifted into position i is never inspected. Two canonical fixes exist: use a conditional increment (only advance i when no removal occurs), or traverse the list backwards so that shifts affect only indices you have already visited.
How ArrayList Operations Work Internally
Although the AP exam does not require you to implement ArrayList itself, understanding the internal mechanics deepens your grasp of why certain algorithms are efficient and others are not. Internally, an ArrayList wraps a plain Object[] array and maintains an integer size field. When add() is called and the backing array is full, the ArrayList allocates a new array (typically 1.5× the old capacity), copies all elements, and then inserts the new element.
Time Complexity of Key Operations
Common Algorithm Patterns
The AP CS A exam recycles a small set of algorithmic patterns that can be combined to solve virtually any ArrayList free-response question. Mastering these patterns transforms unfamiliar problems into straightforward template applications.
| Pattern | Loop Type | Index Adjustment | Modifies Size? |
|---|---|---|---|
| Accumulate (sum, max, count) | for-each or indexed | Standard i++ | No |
| Linear search | Indexed | Standard i++; return on match | No |
| Remove all matching | Indexed (backward preferred) | Backward: i−−; Forward: conditional i++ | Yes ↓ |
| Insert after matching | Indexed forward | After insert: i += 2 to skip inserted element | Yes ↑ |
| Consecutive pairs | Indexed to size()−1 | Standard i++; bound is size()−1 | No |
Worked Example — Removing Duplicates
Write a method removeDuplicates that takes an ArrayList<String> and removes all duplicate occurrences so that only the first occurrence of each string remains. For example, ["a", "b", "a", "c", "b"] becomes ["a", "b", "c"].
remove() during traversal, we must use an indexed for loop. A forward traversal with conditional increment works well here: for each element, scan the remainder of the list for duplicates and remove them.for (int i = 0; i < list.size(); i++) — this advances normally because we never remove the element at index i itself, only elements after it.i, start j = i + 1 and scan forward. If list.get(j).equals(list.get(i)), call list.remove(j) and do NOT increment j. Otherwise, increment j.public static void removeDuplicates(ArrayList<String> list) {
for (int i = 0; i < list.size(); i++) {
int j = i + 1;
while (j < list.size()) {
if (list.get(j).equals(list.get(i))) {
list.remove(j);
} else {
j++;
}
}
}
}while loop re-evaluates list.size() each iteration, so shrinking the list is handled correctly.ArrayList vs. Array — Strengths & Limitations
The AP exam expects you to choose between arrays and ArrayLists based on the problem requirements. Understanding the trade-offs between these two data structures is essential for both the multiple-choice and free-response sections.
| Feature | Array | ArrayList |
|---|---|---|
| Size | Fixed at creation | Dynamic; grows/shrinks automatically |
| Primitives | Stores primitives directly (int, double) | Wrapper classes only (Integer, Double) |
| Access syntax | arr[i] | list.get(i) |
| Insert/remove in middle | Manual shifting required | Built-in add(i, e) / remove(i) |
| Length / size | .length (field) | .size() (method) |
| Ideal when | Size is known and fixed; primitives needed | Size varies; frequent insertion/removal |
Connection to Advanced Data Structures
The ArrayList algorithms you learn in AP CS A are foundational patterns that reappear throughout computer science. In a data structures course, you will encounter LinkedLists, where insertion and removal at arbitrary positions become O(1) once you have a reference to the node, but random access degrades to O(n). The traversal patterns—forward iteration, conditional removal, accumulation—transfer directly, though the implementation uses node pointers instead of integer indices.
| Concept | AP CS A (ArrayList) | Beyond AP (Advanced) |
|---|---|---|
| Traversal | Indexed for-loop, for-each | Iterators, streams, recursive traversal |
| Removal during iteration | Backward loop or conditional i++ | Iterator.remove(), removeIf() |
| Search | Linear scan O(n) | Binary search O(log n), hash lookup O(1) |
| Sorting | Selection/insertion sort | Merge sort, quicksort, Collections.sort() |
| Type safety | Generics (ArrayList<E>) | Bounded wildcards, covariance |
Understanding why remove() shifts elements and how that affects your loop index prepares you to reason about more complex data structure invariants in courses on algorithms and systems programming. The discipline of asking "does my loop variable still point to the right element after a mutation?" is the same discipline that prevents bugs in concurrent programming, database cursor management, and network packet processing.
Practice Problems
ArrayList<String> list = new ArrayList<>(Arrays.asList("A", "B", "B", "C"));
for (String s : list) {
if (s.equals("B")) {
list.remove(s);
}
}
What happens when this code executes?
A. The list becomes ["A", "C"] with both "B" elements removed.
B. The list becomes ["A", "B", "C"] with only the first "B" removed.
C. A ConcurrentModificationException is thrown.
D. An IndexOutOfBoundsException is thrown.result after the following code executes?
ArrayList<Integer> nums = new ArrayList<>(Arrays.asList(3, 7, 2, 8, 5));
int result = 0;
for (int n : nums) {
if (n > 4) {
result += n;
}
}
A. 25
B. 20
C. 15
D. 5
public static void mystery(ArrayList<Integer> list) {
for (int i = list.size() - 1; i > 0; i--) {
if (list.get(i) < list.get(i - 1)) {
list.add(i, list.remove(i - 1));
}
}
}
If list is initially [5, 3, 8, 1], what is list after calling mystery(list)?
A. [1, 3, 5, 8]
B. [3, 5, 1, 8]
C. [1, 5, 3, 8]
D. [5, 3, 1, 8]ArrayList<Integer> called scores. Write a method public static ArrayList<Integer> aboveAverage(ArrayList<Integer> scores) that returns a new ArrayList containing only the scores that are strictly above the average of all scores. Do not modify the original list. Assume scores is non-empty and contains at least one element.public static void removeSandwich(ArrayList<String> list, String start, String end) that removes all elements between the first occurrence of start and the first occurrence of end that appears after start, exclusive (i.e., keep both start and end in the list but remove everything between them). If start or end is not found (or end does not appear after start), do nothing.Summary — Implementing ArrayList Algorithms
ArrayList algorithms on the AP CS A exam revolve around a small set of repeatable patterns. Traversal can use either an indexed for-loop or a for-each loop, but you must use the indexed form whenever insertion or removal changes the list's size during iteration. The cardinal rule for removal during forward traversal is to avoid incrementing the index after a remove—or equivalently, traverse backwards. For insertion during traversal, increment the index by 2 to skip the newly inserted element.
Common patterns include accumulation (sum, count, min, max), linear search (return index or −1), filtering (remove elements matching a condition), and consecutive pair comparison (loop bound is size() - 1). Each pattern dictates a specific loop structure and index management strategy. Mastering these six templates equips you to decompose any FRQ into familiar building blocks.