Aim for FiveComputer Science A

Unit 4 · Topic 4.10

4.10 Implementing ArrayList Algorithms

Every array algorithm from 4.5 works on an ArrayList too, and the list's methods make inserting and deleting much easier. This topic covers building one list from another, inserting in the right place, deleting, and traversing two collections at the same time, the core skills for free-response Question 3.

Key terms

  • insert and delete
  • parallel traversal
  • filtering a list
  • standard algorithms

The standard algorithms carry over

Min and max, sum and average, at least one, all, counting, consecutive pairs, duplicates, shifting, rotating and reversing all work on an ArrayList. Translate the array code: arr.length becomes list.size(), arr[i] becomes list.get(i), and arr[i] = x becomes list.set(i, x).

Two more algorithms are much easier with lists than with arrays: inserting elements and deleting them. add(index, obj) and remove(index) do the shifting for you.

Shifting and rotating get shorter too. list.add(list.remove(0)); rotates a list left by one: remove(0) takes out the first element and returns it, and add puts it on the end. In an array, the same job needed a saved value and a whole loop (4.5).

Building a new list

Many problems ask you to build a new list from an existing one, keeping only the elements that pass some test, or keeping one piece of information from each object. Create an empty list, traverse the original, and add what you want to keep. The original list doesn't change.

When the question says to change the original list instead, delete the elements that fail the test, using the backward loop or the else pattern from 4.9.

Inserting in order

To insert a value into a list that's already sorted, walk forward until you find the first element that isn't smaller, then add at that index:

public static void insertInOrder(ArrayList<Integer> list, int value) { int i = 0; while (i < list.size() && list.get(i) < value) { i++; } list.add(i, value); }

The i < list.size() check comes first, so short-circuiting (2.5) stops get(i) from running off the end when the value belongs at the very end. If the list is empty, the loop doesn't run and the value goes in at index 0.

Traversing two collections at once

Some problems need two strings, arrays or lists at the same time, such as comparing a student's answers with an answer key position by position. Use one index for both, and make sure it stays in range for each. If the two might have different sizes, loop only up to the smaller size.

Other problems pair a list with a different kind of collection, like checking each word in a list against the letters of a string, or copying values from an array into a list. The same rule applies: know which index belongs to which collection, and check each against its own size.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Write a method: filtering objects

    A Review has getText() and getStars() methods. Write a static method praise that returns a new list holding the text of every review with at least minStars stars, in the original order. One solution:public static ArrayList<String> praise(ArrayList<Review> reviews, int minStars) { ArrayList<String> result = new ArrayList<String>(); for (Review r : reviews) { if (r.getStars() >= minStars) { result.add(r.getText()); } } return result; }

    Show the solution
    1. Step 1: Start with an empty ArrayList<String>, since the result holds texts, not reviews.
    2. Step 2: Traverse the reviews. An enhanced for loop is fine, because you only read the original list and never change its size.
    3. Step 3: For each review that passes the test, add its text to the result.
    4. Step 4: Return the new list after the loop. With reviews ("Loved it", 5), ("Meh", 2) and ("Pretty good", 4), praise(rs, 4) returns [Loved it, Pretty good]. If no review qualifies, it returns an empty list, [], not null.

    Answer: The method above. For the sample reviews it returns [Loved it, Pretty good] with a minimum of 4, and [] with a minimum of 6.

  2. Example 2

    Write a method: comparing two lists

    guesses and answers are lists of the same size. Write a method that returns how many positions hold equal strings. One solution:public static int countMatches(ArrayList<String> guesses, ArrayList<String> answers) { int count = 0; for (int i = 0; i < guesses.size(); i++) { if (guesses.get(i).equals(answers.get(i))) { count++; } } return count; }

    Show the solution
    1. Step 1: Both lists are traversed with the same index i, so guesses.get(i) is compared with answers.get(i).
    2. Step 2: Strings are compared with equals, not ==.
    3. Step 3: With guesses B, C, A, D and answers B, A, A, C, positions 0 and 2 match.

    Answer: The method above; for that example it returns 2.

Common mistakes

  • Changing the original list when the question asks you to return a new one, or the other way around.
  • Checking list.get(i) < value before i < list.size(), which can go out of bounds at the end of the list.
  • Using == to compare String or other object elements. Use equals, or compare values from getters.

On the exam

  • Free-response Question 3, Data Analysis with ArrayList, is a single method worth 5 points since the 2025 update. It's always an ArrayList now (it used to be an array or an ArrayList). It usually means traversing a list of objects, calling their methods, and counting, filtering, or removing.
  • Use the getter methods the question gives you. You can't use another class's private instance variables.

Connected topics

Videos

  • AP Computer Science A - Topic 4.10 - Part 1: Implementing ArrayList Algorithms

    Tim Gallagher Computer ScienceWatch on YouTube (opens in a new tab)

  • AP CSA Data Collections – Implementing ArrayList Algorithms

    Goldie's Math EmporiumWatch on YouTube (opens in a new tab)

  • Search And Remove From ArrayLists (Java Tutorial)

    Bill BarnumWatch on YouTube (opens in a new tab)

  • AP Computer Science A - Topic 4.10 - Part 2: Implementing ArrayList Algorithms

    Tim Gallagher Computer ScienceWatch on YouTube (opens in a new tab)

  • ArrayList Algorithms in Java | AP CSA Unit 7

    Stefan WebsterWatch on YouTube (opens in a new tab)

  • 2026 AP Computer Science A Exam Review - Exploring FRQ 3: Data Analysis with ArrayLists

    Tim Gallagher Computer ScienceWatch on YouTube (opens in a new tab)

Check yourself

4 questions on 4.10 Implementing ArrayList Algorithms. Pick an answer to see if you got it, and why.

Question 1 of 4

Consider the following method.public static void insertSorted(ArrayList<Integer> list, int value) { int index = 0; while (index < list.size() && list.get(index) < value) { index++; } list.add(index, value); }Assume list contains [2, 5, 9]. What are the contents of list after the calls insertSorted(list, 7) and insertSorted(list, 1)?

Question 2 of 4

Consider the following code segment.ArrayList<String> words = new ArrayList<String>(); words.add("tree"); words.add("ox"); words.add("apple"); words.add("sky"); ArrayList<String> longOnes = new ArrayList<String>(); for (String w : words) { if (w.length() > 3) { longOnes.add(0, w); } } System.out.println(longOnes);What is printed as a result of executing the code segment?

Question 3 of 4

Consider the following method.public static int countMatches(ArrayList<String> a, ArrayList<String> b) { int count = 0; for (int i = 0; i < a.size() && i < b.size(); i++) { if (a.get(i).equals(b.get(i))) { count++; } } return count; }Assume a contains ["red", "blue", "green", "gold"] and b contains ["red", "green", "green"]. What value is returned by countMatches(a, b)?

Question 4 of 4

Consider the following code segment.ArrayList<Integer> list = new ArrayList<Integer>(); list.add(4); list.add(4); list.add(7); list.add(7); list.add(7); list.add(4); for (int i = list.size() - 1; i > 0; i--) { if (list.get(i).equals(list.get(i - 1))) { list.remove(i); } }Which of the following represents the contents of list after the code segment executes?

0 of 4 answered