Implementing
ArrayList Algorithms

Master the core algorithms for traversing, inserting, removing, and searching elements using Java's ArrayList.

AP Computer Science A

What is an ArrayList?

An ArrayList is a resizable array implementation of the List interface in Java. Unlike a standard array, its size grows and shrinks automatically as elements are added or removed.

Dynamic Size

Grows automatically when elements are added beyond current capacity.

Index-Based

Access any element in \( O(1) \) time using .get(i).

Objects Only

Stores object references, not primitives: use Integer instead of int.

Essential ArrayList Methods

1

.add(element): appends to the end in \( O(1) \) amortized time.

2

.add(index, element): inserts at index, shifts elements right: \( O(n) \).

3

.get(index): returns the element at the given index: \( O(1) \).

4

.set(index, element): replaces element at index, returns old value: \( O(1) \).

5

.remove(index): removes element at index, shifts elements left: \( O(n) \).

6

.size(): returns the number of elements currently stored: \( O(1) \).

Visualizing Insert & Remove

Traversal Patterns

Standard for Loop

Use when you need the index, or plan to modify the list during traversal.

Enhanced for Loop

Cleaner syntax for read-only traversal. Cannot modify the list (ConcurrentModificationException).

// Standard for loop
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// Enhanced for-each loop
for (String item : list) {
    System.out.println(item);
}

Forward vs Backward Traversal

	Forward (from index \(0\))	Backward (from index \(\text{size()}-1\))
Direction	Left to right	Right to left
Use for	General reading, searching	Removing elements safely
Index after remove	Elements shift: skip risk	Already-visited elements shift
Pattern	i = 0; i < size(); i++	i = size()-1; i >= 0; i--

The Traverse-Check-Act Pattern

How to Apply the Pattern

1

Identify the task: Are you searching, filtering, counting, or transforming?

2

Choose traversal direction: Forward for read-only, backward for removal.

3

Choose loop type: Standard for if you need index access or will modify the list. Enhanced for for simple reads.

4

Write the condition: What must be true about the current element to trigger action?

5

Perform the action: Add, remove, set, or accumulate into a result variable.

6

Adjust the index if removing forward: Decrement \( i \) after removing to avoid skipping.

Example: Remove All Negatives

Given an ArrayList<Integer>, remove every element that is less than zero.

// Backward traversal — safe removal
public static void removeNegatives(ArrayList<Integer> list) {
    for (int i = list.size() - 1; i >= 0; i--) {
        if (list.get(i) < 0) {
            list.remove(i);
        }
    }
}

Tracing the Removal

Example: Linear Search

Find the index of the first occurrence of a target value. Return -1 if not found.

public static int linearSearch(ArrayList<String> list, String target) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i).equals(target)) {
            return i;
        }
    }
    return -1;
}

Example: Sum & Average

The accumulator pattern initializes a running total, then adds each element's contribution during traversal.

public static double average(ArrayList<Integer> nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return (double) sum / nums.size();
}

Example: Filtering into a New List

Sometimes the goal is to create a new list of elements that meet a condition, leaving the original unchanged.

// Return a new list of even numbers
public static ArrayList<Integer> getEvens(ArrayList<Integer> nums) {
    ArrayList<Integer> evens = new ArrayList<>();
    for (int num : nums) {
        if (num % 2 == 0) {
            evens.add(num);
        }
    }
    return evens;
}

Advanced: Simultaneous Traversal

When comparing two ArrayLists element-by-element, traverse both at once using a standard for loop up to the smaller size.

// Count matching elements at the same index
public static int countMatches(ArrayList<String> a, ArrayList<String> b) {
    int count = 0;
    int minSize = Math.min(a.size(), b.size());
    for (int i = 0; i < minSize; i++) {
        if (a.get(i).equals(b.get(i))) {
            count++;
        }
    }
    return count;
}

Common Mistakes

Forward Remove Skip

Removing in a forward loop without decrementing \( i \) causes the next element to shift into the current index and be skipped.

Using == for Objects

Using == instead of .equals() compares memory addresses, not values. Works for primitives, fails for Strings and wrapper types.

Off-by-One Errors

Using \( i \le \text{list.size()} \) instead of \( i < \text{list.size()} \). Valid indices range from \( 0 \) to \( \text{size()} - 1 \).

Algorithm Summary

Algorithm	Loop Type	Direction	Key Method
Linear Search	Standard for	Forward	.get(), .equals()
Remove by condition	Standard for	Backward	.remove(\(i\))
Accumulate (sum, count)	Enhanced for	Forward	\( \text{+=} \) operator
Filter to new list	Enhanced for	Forward	.add()
Insert at position	Standard for	Forward	.add(\(i\), elem)
Compare two lists	Standard for	Forward	Math.min(), .get()

Question 1 of 5

What is the output of the following code?

ArrayList<Integer> list = new ArrayList<>(); list.add(10); list.add(20); list.add(30); list.add(1, 15); System.out.println(list);

add(1, 15) inserts 15 at index 1, shifting 20 and 30 to the right. The list becomes [10, 15, 20, 30].

Question 2 of 5

You want to remove all occurrences of the String "spam" from an ArrayList. Which loop structure is safest?

A backward standard for loop is safest because elements that shift after removal have already been visited. Enhanced for loops throw ConcurrentModificationException when modifying. Forward loops without \( i\text{--} \) skip elements.

Question 3 of 5

Consider this code fragment:

ArrayList<String> words = /* initialized */; for (int i = 0; i < words.size(); i++) { if (words.get(i).length() <= 3) { words.remove(i); } }

If words starts as ["hi", "hello", "go", "yes"], what is the result?

The trace is: i=0, "hi" is removed. List becomes ["hello", "go", "yes"]. i increments to 1. i=1, the element at index 1 is now "go", which is removed. List becomes ["hello", "yes"]. i increments to 2. The loop terminates as the condition (2 < 2) is false. This pattern is flawed; for example, in ["a", "b", "word"], removing "a" would cause "b" to be skipped.

Question 4 of 5

What is the time complexity of calling list.add(0, element) on an ArrayList with \( n \) elements?

Inserting at index 0 requires shifting all \( n \) existing elements one position to the right to make room. This shift operation takes \( O(n) \) time.

Question 5 of 5

Which line of code correctly checks if element at index \( i \) in an ArrayList<String> equals the String "target"?

ArrayLists use .get(i) for element access (not bracket notation). String comparison requires .equals() to compare values, not == which compares references. Option D is not a valid ArrayList method signature.

ImplementingArrayList Algorithms

What is an ArrayList?

Essential ArrayList Methods

Visualizing Insert & Remove

Traversal Patterns

Forward vs Backward Traversal

The Traverse-Check-Act Pattern

How to Apply the Pattern

Example: Remove All Negatives

Tracing the Removal

Example: Linear Search

Example: Sum & Average

Example: Filtering into a New List

Advanced: Simultaneous Traversal

Common Mistakes

Algorithm Summary

Question 1 of 5

Question 2 of 5

Question 3 of 5

Question 4 of 5

Question 5 of 5

Implementing
ArrayList Algorithms