Implementing ArrayList Algorithms - AP Computer Science A

SECTION 1

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.

1960s • Early List Processing

Languages like LISP pioneer linked-list abstractions; arrays remain the dominant random-access structure in imperative languages like FORTRAN and C.

1995 • Java 1.0 & the Vector Class

Java ships with the synchronized Vector class—a resizable array—but its thread-safe overhead proves costly for single-threaded algorithms.

1998 • Java 1.2 Collections Framework

The ArrayList class debuts as an unsynchronized, high-performance resizable array implementing the List interface, becoming the standard for AP CS A.

2004 • Generics in Java 5

Parameterized types (e.g., ArrayList<String>) eliminate unsafe casts, making list algorithms type-safe at compile time.

2020s • AP CS A Curriculum Emphasis

The College Board centers ArrayList algorithms in Unit 7, requiring students to implement traversals, insertions, and removals using both indexed and enhanced for loops.

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.

SECTION 2

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

Use a standard 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

The 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

Calling 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

Calling 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

Traverse the list comparing each element to a target. Return the index on match or −1 if not found. The average case inspects n/2 elements.

✦

KEY TAKEAWAY

Think of an ArrayList like a row of chairs in a theater. Adding a chair in the middle forces everyone to the right to scoot over; removing one lets everyone shift left. If you are walking down the row counting people (traversing) and someone removes a chair right behind you, you will accidentally skip a seat unless you step back one position—this is exactly why indexed removal requires an index adjustment.

SECTION 3

Visual Explanation — Traversal & Removal

The top half shows the classic bug: incrementing 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.

SECTION 4

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

INDEXED ACCESS

get(i) → O(1)

Direct array indexing; constant time regardless of list size.

APPEND TO END

add(elem) → amortized O(1)

Usually O(1); occasionally O(n) when resizing is triggered, but amortized over many calls it averages to constant time.

INSERT AT INDEX / REMOVE AT INDEX

add(i, elem) or remove(i) → O(n)

Elements from index i to size−1 must be shifted right (for insert) or left (for remove). Worst case shifts all n elements.

LINEAR SEARCH

Sequential scan → O(n)

Must inspect each element in the worst case. On average, n/2 comparisons.

💡

AP Exam Tip

The AP exam will not ask you to state Big-O notation explicitly, but free-response graders expect efficient solutions. Avoid nested loops over the same list unless the problem specifically requires comparing all pairs—an O(n²) approach when O(n) suffices will lose style points or lead to incorrect logic.

SECTION 5

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.

Six fundamental ArrayList algorithm patterns with code templates. The top row covers read-only and destructive traversals; the bottom row covers insertion and pair comparison. Note how each pattern dictates the loop structure and index management strategy.

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

Summary of loop and index strategies for each pattern

SECTION 6

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"].

Removing Duplicates from an ArrayList<String>

1
Step 1 — Choose a traversal strategy

Because we will be calling 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.
2
Step 2 — Outer loop iterates through each element

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.
3
Step 3 — Inner loop removes later duplicates

For each 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.
4
Step 4 — Write the complete method

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++; } } } }

Input: ["a", "b", "a", "c", "b"] → Output: ["a", "b", "c"]. The while loop re-evaluates list.size() each iteration, so shrinking the list is handled correctly.
5
Step 5 — Trace through the example

i=0 ("a"): j scans and removes index 2 ("a"). List becomes ["a","b","c","b"]. i=1 ("b"): j scans and removes index 3 ("b"). List becomes ["a","b","c"]. i=2 ("c"): no duplicates found. Loop ends.

Final list: ["a", "b", "c"]

SECTION 7

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

Key differences between arrays and ArrayLists on the AP exam

✦

KEY TAKEAWAY

Arrays are like fixed-size toolboxes: fast and lightweight, but you cannot add a slot. ArrayLists are like expandable accordion folders: they adapt to however many documents you insert, but each document must be wrapped in an envelope (autoboxing). Choose the structure that matches your problem's mutability requirements.

SECTION 8

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

How AP-level ArrayList concepts connect to more advanced topics

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.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Consider the following code segment:


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.

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.

Show answer (C)

C. Modifying an ArrayList's size during a for-each loop triggers a ConcurrentModificationException. The enhanced for loop uses an internal Iterator, which detects structural modification. A is wrong because the code never completes successfully. B is wrong for the same reason—it implies partial completion without error. D is wrong because the exception occurs from the iterator's modification check, not from an invalid index.

Question 2: BASIC CALCULATION

What is the value of 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

A. 25
B. 20
C. 15
D. 5

Show answer (B)

B. The elements greater than 4 are 7, 8, and 5. Their sum is 7 + 8 + 5 = 20. A (25) is wrong—it would be the sum of all elements. C (15) is wrong—it is 7 + 8, which omits 5 (5 > 4 is true). D (5) counts only the last qualifying element.

Question 3: INTERMEDIATE

Consider the following method:


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]

A. [1, 3, 5, 8]
B. [3, 5, 1, 8]
C. [1, 5, 3, 8]
D. [5, 3, 1, 8]

Show answer (C)

C. The method iterates backward through the list and swaps adjacent elements when the element at index i is less than the element at i−1. The expression list.add(i, list.remove(i-1)) first removes the element at index i−1 (shifting all subsequent elements left by one), then inserts that removed element at index i, effectively swapping the two adjacent elements. Trace with [5, 3, 8, 1]: i=3: list.get(3)=1 < list.get(2)=8? Yes → remove(2) returns 8, list becomes [5, 3, 1], then add(3, 8) → [5, 3, 1, 8] i=2: list.get(2)=1 < list.get(1)=3? Yes → remove(1) returns 3, list becomes [5, 1, 8], then add(2, 3) → [5, 1, 3, 8] i=1: list.get(1)=1 < list.get(0)=5? Yes → remove(0) returns 5, list becomes [1, 3, 8], then add(1, 5) → [1, 5, 3, 8] Result: [1, 5, 3, 8]. This is one backward pass of a bubble-sort variant: the smallest element (1) bubbles all the way to the front, but the other elements are only partially sorted. A is wrong because a single pass does not fully sort the list. B is wrong because the smallest element propagates all the way to the front, not partway. D is wrong because swaps do occur during this pass.

Question 4: APPLIED

4 pts

A teacher stores student scores in an 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.

Show answer

Rubric (4 points): +1 Correctly computes the sum and average: Traverses scores to compute the total sum, then divides by scores.size(). The average must be stored as a double (using a cast or 1.0 multiplier) to avoid integer truncation. +1 Creates and returns a new ArrayList: Declares a new ArrayList<Integer> for the result. Does not modify the original input list. +1 Correct traversal and comparison: Iterates through scores and adds each element that is strictly greater than the average to the result list. +1 Correct return and no off-by-one errors: Returns the result ArrayList. Uses > (not >=) for strictly above average. No bounds or indexing errors. Sample solution:

public static ArrayList<Integer> aboveAverage(ArrayList<Integer> scores) {
  int sum = 0;
  for (int s : scores) {
    sum += s;
  }
  double avg = (double) sum / scores.size();
  ArrayList<Integer> result = new ArrayList<>();
  for (int s : scores) {
    if (s > avg) {
      result.add(s);
    }
  }
  return result;
}

Example trace: scores = [70, 80, 90, 60]. Sum = 300, avg = 75.0. Elements greater than 75.0 are 80 and 90, so the method returns [80, 90].

Question 5: CRITICAL THINKING

3 pts

Write a method 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.

Show answer

Rubric (3 points): +1 Correctly finds the indices of start and end: Uses a linear search to find the first index of start, then searches from startIndex+1 onward for end. Handles the not-found case by returning early. +1 Correctly removes elements between start and end: Removes elements at index startIndex+1 repeatedly (the element at that position shifts down each time) until the element at startIndex+1 equals end. Alternatively, uses a count or computes how many to remove. +1 Preserves start and end elements, handles edge case: Does not remove start or end themselves. If start and end are adjacent, removes nothing. Sample solution:

public static void removeSandwich(ArrayList<String> list, String start, String end) {
  int sIdx = -1;
  for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals(start)) { sIdx = i; break; }
  }
  if (sIdx == -1) return;
  int eIdx = -1;
  for (int i = sIdx + 1; i < list.size(); i++) {
    if (list.get(i).equals(end)) { eIdx = i; break; }
  }
  if (eIdx == -1) return;
  for (int i = 0; i < eIdx - sIdx - 1; i++) {
    list.remove(sIdx + 1);
  }
}

SUMMARY

Summary — Implementing ArrayList Algorithms

Summary

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.