4.10 Developing Algorithms Using ArrayLists

Implementing ArrayList algorithms means writing traversal-based code that processes a list of object references. Standard tasks include finding a min or max, computing a sum or average, counting or checking for a property, detecting duplicates, shifting or reversing elements, and inserting or deleting items. For AP Computer Science A, use size(), get(), set(), add(), and remove() carefully, especially when the list changes size during traversal.

What Are ArrayList Algorithms in AP Computer Science A?

ArrayList algorithms are traversal patterns that process, search, count, compare, rearrange, insert, or delete elements in an ArrayList. AP CSA Topic 4.10 expects you to implement standard algorithms, adapt them to a specific prompt, and determine the result of code that uses those algorithms.

The most important exam habit is matching the algorithm to the list operation. If the code only reads elements, an enhanced for loop may work. If the code inserts or removes elements, use an indexed loop or while loop so you can control how the index changes when the ArrayList size changes.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science A Exam

ArrayList algorithms show up in both multiple-choice and free-response code writing. In multiple-choice questions you often trace a traversal to predict output or spot why a segment fails. In free-response, one question gives you a class that represents a data set and asks you to write a method that uses, analyzes, or manipulates an ArrayList of objects based on a specification and examples. That often means inserting or removing elements, which forces you to adjust your loop counter so you do not skip elements or reach past the end of the list.

Because these algorithms reuse a small set of patterns, learning them well pays off across many questions. The same traversal logic you use for arrays in 4.5 carries over to ArrayLists, with method calls replacing bracket indexing.

Key Takeaways

• Standard ArrayList algorithms use traversals to find a min or max, compute a sum or average, check if at least one or all elements have a property, count matching elements, look at consecutive pairs, detect duplicates, shift or rotate, reverse, insert, and delete.
• Use size(), get(index), set(index, obj), add(obj), add(index, obj), and remove(index) to access and change elements.
• When you insert or delete during an indexed traversal, adjust the loop counter so you do not skip an element or run past the end.
• Do not add or remove elements while using an enhanced for loop on an ArrayList, since changing the size can cause a ConcurrentModificationException.
• Some problems need you to traverse two or more collections at the same time, lining up matching indices.
• Always plan for edge cases like an empty list, a single element, or no elements matching the criteria.

Key Concepts

The Standard Algorithm Patterns

Most ArrayList problems are versions of a few traversal patterns. Recognizing the pattern first makes the code much easier to write.

• Accumulate a result: sum, average, count of matching elements, or running min or max.
• Check a property: does at least one element satisfy a condition, or do all of them?
• Search: find the index or presence of a value.
• Build a new list: keep only elements that meet criteria, or convert each element into something new.
• Compare elements: look at consecutive pairs, or check for duplicates.
• Restructure: shift, rotate, reverse, insert, or delete.

You do not start each problem from scratch. You identify which pattern fits, then adapt it to the exact specification.

A Reliable Problem-Solving Process

Use the same steps every time:

1. Read the specification and the examples carefully so you know exactly what the method should return or change.
2. Decide which pattern applies.
3. Plan the traversal and any accumulator variables before you type code.
4. Write the method step by step.
5. Trace it with a small list, including edge cases.

Planning first prevents the random coding that causes bugs. The examples in a free-response prompt are not decoration. They tell you precisely what your method must produce.

Accumulator Variables

Accumulators are variables that build up a result as you traverse the list.

• Simple accumulator: a running sum or count.
• Conditional accumulator: only updates when a condition is true, like counting positives.
• Best-so-far accumulator: tracks the current min or max.
• Multiple accumulators: track several values at once, like counting positives and negatives in one pass.

Initialize each accumulator with a sensible starting value before the loop. Counters and sums usually start at 0. A best-so-far value often starts at the first element.

Inserting and Deleting During Traversal

Changing a list while you traverse it is where most ArrayList bugs come from.

• With an indexed loop, remove(index) shifts every later element left by one. If you keep incrementing your index normally, you skip the element that just moved into that position. A common fix is to not increment the index when you remove, or to traverse from the end toward the start.
• add(index, obj) shifts later elements right, which can make a forward loop revisit elements or run long. Adjust the counter to match.
• Do not add or remove elements during an enhanced for loop on an ArrayList. Changing its size can throw a ConcurrentModificationException.

Traversing Multiple Collections at Once

Some algorithms need two or more collections processed together, such as comparing a list of names with a parallel list of scores. Use one index to reach matching positions in each collection, and make sure the index stays in range for every collection you access.

Edge Cases

Test these every time:

• Empty list: operations like finding a maximum have no answer, so decide what to return.
• Single element: confirm the general loop still works with one item.
• No matches: searching for something that is not present needs clear behavior, like returning -1.

Code Examples

Accumulator Algorithm: Finding Maximum

</>Java
import java.util.ArrayList;

public class MaximumFinder {
    public static Integer findMaximum(ArrayList<Integer> numbers) {
        // Edge case: empty list
        if (numbers.isEmpty()) {
            return null;  // Or another agreed-on result for an empty list
        }

        // Initialize accumulator with first element
        int maximum = numbers.get(0);

        // Process remaining elements
        for (int i = 1; i < numbers.size(); i++) {
            int current = numbers.get(i);
            if (current > maximum) {
                maximum = current;  // Update our "best so far"
            }
        }

        return maximum;
    }
}

Handle the empty case first, then start the accumulator with the first element. The same shape works for minimum and other best-so-far problems.

Search Algorithm: Linear Search with Index

</>Java
import java.util.ArrayList;

public class LinearSearchDemo {
    public static int findFirstOccurrence(ArrayList<String> words, String target) {
        for (int i = 0; i < words.size(); i++) {
            if (words.get(i).equals(target)) {
                return i;  // Found it, return position
            }
        }
        return -1;  // Not found, standard convention
    }

    // Variation: find the last occurrence by searching backward
    public static int findLastOccurrence(ArrayList<String> words, String target) {
        for (int i = words.size() - 1; i >= 0; i--) {
            if (words.get(i).equals(target)) {
                return i;
            }
        }
        return -1;
    }
}

Linear search checks each element in order until it finds a match, and you can start from either end. Use .equals() to compare object references like Strings, not ==.

Filter Algorithm: Building a New ArrayList

</>Java
import java.util.ArrayList;

public class FilteringAlgorithms {
    public static ArrayList<Integer> filterPositives(ArrayList<Integer> numbers) {
        ArrayList<Integer> positives = new ArrayList<Integer>();
        for (Integer num : numbers) {
            if (num > 0) {
                positives.add(num);  // Keep elements that match
            }
        }
        return positives;
    }
}

Building a new list lets you use an enhanced for loop safely, because you are not changing the list you are traversing.

Insert and Delete Safely with an Indexed Loop

</>Java
import java.util.ArrayList;

public class RemoveMatches {
    // Removes every element equal to target without skipping elements
    public static void removeAll(ArrayList<String> words, String target) {
        int i = 0;
        while (i < words.size()) {
            if (words.get(i).equals(target)) {
                words.remove(i);   // Do not increment; later elements shifted left
            } else {
                i++;               // Only advance when nothing was removed
            }
        }
    }
}

After remove(i), the next element slides into index i, so you check that same index again instead of advancing. This is the loop-counter adjustment free-response prompts expect when you delete during a traversal.

Comparison Algorithm: Duplicate Detection

</>Java
import java.util.ArrayList;

public class DuplicateDetection {
    public static boolean hasDuplicates(ArrayList<String> words) {
        for (int i = 0; i < words.size(); i++) {
            for (int j = i + 1; j < words.size(); j++) {
                if (words.get(i).equals(words.get(j))) {
                    return true;  // Found a duplicate
                }
            }
        }
        return false;  // No duplicates found
    }
}

The inner loop starts at i + 1 so each pair is compared once. This nested-loop approach compares elements to each other rather than to a single target.

How to Use This on the AP Computer Science A Exam

Code Tracing

For multiple-choice, expect to trace a traversal and predict the output or final list. If no specific list is given, make a small one of your own, like 4 or 5 elements, and follow the loop for the first few iterations to see the pattern. Watch indices closely when the code calls remove or add, since those change the size and shift elements.

Free Response

When you write a method that manipulates an ArrayList of objects:

• Use the provided examples to confirm exactly what to return or change.
• Call the object's methods to read the data you need from each element.
• If you insert or delete, adjust your loop counter so you do not skip or overrun.
• Use a plain indexed for or while loop when you modify size, and save the enhanced for loop for read-only traversals.

Common Trap

Removing inside an enhanced for loop, or removing inside an indexed for loop while still doing i++, are the two mistakes that most often break ArrayList code. When in doubt, switch to a while loop and control the index yourself.

Common Misconceptions

• "Enhanced for loops can add or remove elements." They cannot safely. Changing the size during an enhanced for loop on an ArrayList can throw a ConcurrentModificationException. Use an indexed loop when you modify the list.
• "After remove(i), I should still do i++." No. Removing shifts later elements left, so the next element is now at index i. Advancing skips it.
• "== compares the contents of two objects." For object references like Strings, use .equals(). == checks whether they are the same reference, not whether they hold equal values.
• "An accumulator starts at the right value automatically." You must initialize it. Counters and sums usually start at 0, and a best-so-far value often starts at the first element.
• "Filtering means deleting from the original list." You can also build a new list of the elements that match, which avoids modification-during-traversal problems entirely.
• "ArrayList indices go up to size()." Valid indices run from 0 to size() - 1. Accessing size() or higher throws an IndexOutOfBoundsException.

Related AP Computer Science A Guides

• 4.11 2D Arrays
• 4.15 Sorting
• 4.1 Ethical and Social Implications
• 4.9 Traversing ArrayLists
• 4.5 Developing Algorithms Using Arrays
• 4.16 Recursion