1. LxD Cycle Process

Empathize: Students can call add, get, set, remove, and size correctly in isolation, but freeze when a free-response question asks for “the largest score” or “how many names match,” because that requires combining those single steps inside a loop. A second failure mode shows up only at runtime: removing elements while traversing forward silently skips the element right after the one just removed.

Define:

  • POV: CSA students need to see ArrayList algorithms as the same traversal shape used for arrays, but with size() and get(i) in place of .length and [i], because the loop skeleton for max/min, searching, filtering, and removing is otherwise identical to what they already know.
  • Learning Goal: Students will write traversal algorithms over an ArrayList to find a maximum or minimum, search and count with indexOf/contains/a counting loop, build a filtered list, and remove elements while traversing without skipping any.

Ideate:

  • HMW Question: How might we make the “start max at get(0), not at 0” rule feel necessary instead of arbitrary?
  • HMW Question: How might we make a skipped element during forward removal visible, so the backward-traversal fix feels earned rather than memorized?
  • Activity: Trace a buggy maxValueBuggy on an all-negative list, then trace a forward-removal loop step by step and watch it skip a value.

Prototype & Test: Lesson authors: add what happened in your trial run and what you changed.

2. Lesson Plan

Learning Objective: Write traversal algorithms over an ArrayList to find extremes, search, filter, and safely remove elements.

Success Criteria: You can explain why maxValue starts comparing at index 1, use indexOf/contains versus a counting loop appropriately, build a new filtered list without changing the original, and traverse backward when removing multiple elements by index.

Before you start: ArrayList methods from 4.8 (add, get, set, remove, size) and indexed for loops.

Tech Talk (5 minutes)

add, get, set, remove, and size are single steps. An algorithm combines those steps in a loop to answer a real question: What is the highest score? How many names match? Which elements should stay?

The traversal shape carries over directly from arrays; only the bound and the access method change:

for (int i = 0; i < scores.size(); i++) {   // size(), not .length
    System.out.println(scores.get(i));       // get(i), not scores[i]
}

Two habits keep these algorithms correct. First, when finding a maximum or minimum, start the accumulator at nums.get(0) and loop from index 1, so a list of only negative numbers is not compared against an assumed starting value like 0. Second, when removing elements by index while traversing, go from the last index down to 0; removing a later index never shifts the position of an earlier, unvisited index, so nothing gets skipped.

From the College Board

AP CSA Unit 4, Topic 4.10 focuses on implementing ArrayList algorithms. Quoted from the course and exam description (College Board, 2025, p. 113):

  • 4.10.A “Develop code for standard and original algorithms for a particular context or specification that involve ArrayList objects and determine the result of these algorithms.”
  • 4.10.A.1 “There are standard ArrayList algorithms that utilize traversals to: determine a minimum or maximum value; compute a sum or average; determine if at least one element has a particular property; determine if all elements have a particular property; determine the number of elements having a particular property; access all consecutive pairs of elements; determine the presence or absence of duplicate elements; shift or rotate elements left or right; reverse the order of the elements; insert elements; delete elements.”
  • 4.10.A.2 “Some algorithms require multiple String, array, or ArrayList objects to be traversed simultaneously.”

The related traversal essential knowledge from Topic 4.9 explains why the removal direction matters (College Board, 2025, p. 112):

  • 4.9.A.2 “Deleting elements during a traversal of an ArrayList requires the use of special techniques to avoid skipping elements.”
  • 4.9.A.4 “Changing the size of an ArrayList while traversing it using an enhanced for loop can result in a ConcurrentModificationException. Therefore, when using an enhanced for loop to traverse an ArrayList, you should not add or remove elements.”

3. Reference Guide

Key Vocabulary

Term Definition Example
Traversal Visiting every element of a collection, usually with a loop. for (int i = 0; i < nums.size(); i++)
Accumulator A variable updated across iterations to build a running result. max, count, kept
indexOf(obj) Returns the index of the first match, or -1 if none. roster.indexOf("Amir")
contains(obj) Returns true if any element matches. roster.contains("Jordan")
ConcurrentModificationException Runtime error from adding/removing during an enhanced for loop. Removing inside for (int n : nums)

Standard ArrayList Algorithm Categories (EK 4.10.A.1)

  • Minimum or maximum value
  • Sum or average
  • At least one element with a property
  • All elements with a property
  • Count of elements with a property
  • Consecutive pairs of elements
  • Presence or absence of duplicates
  • Shift or rotate elements
  • Reverse the order of elements
  • Insert or delete elements

Safe vs. Unsafe Traversal for Removal

Traversal Safe to remove while traversing?
Indexed for loop, forward (i increasing) Only one removal, or accept skipped elements
Indexed for loop, backward (i decreasing to 0) Yes — earlier indices are never shifted
Enhanced for loop (for (int n : nums)) No — throws ConcurrentModificationException if the list changes size

4. Code Examples

A. Warm-up: The Traversal Shape Carries Over

Run the cell below, then answer the questions that follow.

int[] arrayScores = {70, 85, 90};

ArrayList<Integer> listScores = new ArrayList<Integer>();
listScores.add(70);
listScores.add(85);
listScores.add(90);

System.out.println("array length = " + arrayScores.length);
System.out.println("list size = " + listScores.size());
  1. What loop condition visits every index of arrayScores?
  2. What loop condition visits every index of listScores?
  3. What changes between the two loops? What stays the same?
Check your reasoning
  1. i < arrayScores.length
  2. i < listScores.size()
  3. The bound changes from a field to a method call. The overall shape (start at 0, read one element per iteration, stop before the bound) stays the same.

B. Finding a Maximum

Contract: nums contains at least one element.

Predict: What does maxValue return for [4, 9, 2, 9, 5]? Then run the cell.

public static int maxValue(ArrayList<Integer> nums) {
    int max = nums.get(0);
    for (int i = 1; i < nums.size(); i++) {
        if (nums.get(i) > max) {
            max = nums.get(i);
        }
    }
    return max;
}

ArrayList<Integer> sample = new ArrayList<Integer>();
sample.add(4);
sample.add(9);
sample.add(2);
sample.add(9);
sample.add(5);

System.out.println(maxValue(sample));
Check your reasoning
i nums.get(i) max after this step
start - 4
1 9 9
2 2 9
3 9 9
4 5 9

maxValue returns 9. Starting max at nums.get(0) and looping from index 1 avoids comparing an element to itself.

You decide: Why does this method start max at nums.get(0) instead of 0? Run the cell below, which starts max at 0 instead, on a list of only negative numbers.

public static int maxValueBuggy(ArrayList<Integer> nums) {
    int max = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums.get(i) > max) {
            max = nums.get(i);
        }
    }
    return max;
}

ArrayList<Integer> negatives = new ArrayList<Integer>();
negatives.add(-4);
negatives.add(-9);
negatives.add(-2);

System.out.println(maxValueBuggy(negatives));
Reveal the answer

maxValueBuggy returns 0, a value that never appears in negatives. Starting at 0 assumes a non-negative value is always available for comparison, which is not true here since every real element is less than 0.

C. Searching: indexOf, contains, and Counting Matches

Method call Returns
indexOf(obj) The index of the first element equal to obj, or -1 if none matches
contains(obj) true if some element is equal to obj, otherwise false

Predict: What are firstIndex and hasJordan? Then run the cell.

ArrayList<String> roster = new ArrayList<String>();
roster.add("Amir");
roster.add("Priya");
roster.add("Amir");

int firstIndex = roster.indexOf("Amir");
boolean hasJordan = roster.contains("Jordan");

System.out.println("firstIndex = " + firstIndex);
System.out.println("hasJordan = " + hasJordan);
Check your reasoning

firstIndex is 0, the position of the first "Amir". hasJordan is false; "Jordan" never appears in roster. Both methods compare content with .equals, not object identity.

Both methods stop as soon as one match is found and cannot report how many matches exist in total. Counting every match needs a loop.

Predict: How many times does "Amir" appear? Then run the cell.

public static int countMatches(ArrayList<String> names, String target) {
    int count = 0;
    for (int i = 0; i < names.size(); i++) {
        if (names.get(i).equals(target)) {
            count++;
        }
    }
    return count;
}

ArrayList<String> roster2 = new ArrayList<String>();
roster2.add("Amir");
roster2.add("Priya");
roster2.add("Amir");

System.out.println(countMatches(roster2, "Amir"));

Pause: Why does this method call .equals instead of using ==?

Check your reasoning

== on Strings compares references, not the characters they contain. Two different String objects holding the same text are not guaranteed to be ==, but .equals always compares content correctly.

D. Building a Filtered List

An algorithm can traverse one list while building a second one, keeping only the elements that satisfy some condition.

Predict: What does keepAtLeast return for nums = [3, 8, 1, 10, 6] and threshold = 6? Then run the cell.

public static ArrayList<Integer> keepAtLeast(ArrayList<Integer> nums, int threshold) {
    ArrayList<Integer> kept = new ArrayList<Integer>();
    for (int num : nums) {
        if (num >= threshold) {
            kept.add(num);
        }
    }
    return kept;
}

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(3);
nums.add(8);
nums.add(1);
nums.add(10);
nums.add(6);

System.out.println(keepAtLeast(nums, 6));
Check your reasoning

[8, 10, 6]. The enhanced for loop visits every element of nums in order without touching nums itself; only the new list kept is built up.

Why this is safe: the enhanced for loop reads nums but never adds to or removes from it. nums keeps its original size and order the entire time.

E. The Removal Trap: Modifying While Traversing

Removing elements from the same list you are traversing changes what the next iteration sees. Run the cell below and check whether every 2 gets removed.

ArrayList<Integer> valuesBuggy = new ArrayList<Integer>();
valuesBuggy.add(5);
valuesBuggy.add(2);
valuesBuggy.add(2);
valuesBuggy.add(9);

for (int i = 0; i < valuesBuggy.size(); i++) {
    if (valuesBuggy.get(i) == 2) {
        valuesBuggy.remove(i);
    }
}

System.out.println(valuesBuggy);
Check your reasoning
i values before this step action
0 [5, 2, 2, 9] 5 != 2, no removal
1 [5, 2, 2, 9] remove index 1
2 [5, 2, 9] values.get(2) is 9, no removal

Not every 2 is removed. After removing index 1, the second 2 shifts into index 1, but i advances to 2 and skips over it. The final list is [5, 2, 9], still containing a 2.

Do not traverse an ArrayList with an enhanced for loop while adding to or removing from that same list. Its structure is expected to stay unchanged during that kind of loop, and Java can throw a runtime error (ConcurrentModificationException) if it is changed anyway.

Fixing it: traverse backward

Traversing from the last index to the first means every removal only affects indices already visited. Run the corrected version below.

ArrayList<Integer> valuesFixed = new ArrayList<Integer>();
valuesFixed.add(5);
valuesFixed.add(2);
valuesFixed.add(2);
valuesFixed.add(9);

for (int i = valuesFixed.size() - 1; i >= 0; i--) {
    if (valuesFixed.get(i) == 2) {
        valuesFixed.remove(i);
    }
}

System.out.println(valuesFixed);
Check your reasoning
i values before this step action
3 [5, 2, 2, 9] 9 != 2, no removal
2 [5, 2, 2, 9] remove index 2
1 [5, 2, 9] remove index 1
0 [5, 9] 5 != 2, no removal

The final list is [5, 9]. Removing a later index first never changes the position of an earlier, still-unvisited index.

5. Hacks & Practice Tasks

Prepare your submission IPYNB

  1. Create a new notebook in your portfolio homework area: _notebooks/homework.
  2. Add one raw cell at the top with the frontmatter:
---
layout: post
codemirror: true
title: Implementing ArrayList Algorithms HW
categories: [Java]
lesson_language: Java
lesson_topic: Implementing ArrayList Algorithms HW
lesson_part: interactive
lesson_type: lesson
permalink: /csa/unit_04/4_10-hw
author: yourGithubID
---
  1. Add code cells for the Popcorn Hack and both parts of the Homework Hack. Make sure every cell runs with visible output.
  2. Submit the link to your published page at the bottom of this page, and paste this in the description box:
Lesson: CSA 4.10 Implementing ArrayList Algorithms
Popcorn: minValue implemented and tested against all three sample calls
Homework Part A: countAtLeast implemented and tested against all three sample calls
Homework Part B: removeNegatives implemented and tested against all three sample calls

Submission Safety Rules (Read First)

  • One method per cell for the Hacks, ending with a test cell that prints its results.
  • Run each cell and leave the output showing.
  • Traverse backward when the contract requires removing elements in place.
  • Use ## headings or smaller.

Popcorn Hack (In-Class)

Write minValue(ArrayList<Integer> nums) that returns the smallest value in nums. Model it after maxValue.

Contract: nums contains at least one element.

Call Expected result
minValue([4, 9, 2, 9, 5]) 2
minValue([7]) 7
minValue([-3, -1, -9]) -9

Write your solution in the cell below, then run the test cell after it.

public static int minValue(ArrayList<Integer> nums) {
    // Find and return the smallest value.
    return 0;
}


ArrayList<Integer> minTest1 = new ArrayList<Integer>();
minTest1.add(4); minTest1.add(9); minTest1.add(2); minTest1.add(9); minTest1.add(5);
System.out.println(minValue(minTest1)); // expect 2

ArrayList<Integer> minTest2 = new ArrayList<Integer>();
minTest2.add(7);
System.out.println(minValue(minTest2)); // expect 7

ArrayList<Integer> minTest3 = new ArrayList<Integer>();
minTest3.add(-3); minTest3.add(-1); minTest3.add(-9);
System.out.println(minValue(minTest3)); // expect -9
Reveal a solution after writing yours 
public static int minValue(ArrayList<Integer> nums) {
    int min = nums.get(0);
    for (int i = 1; i < nums.size(); i++) {
        if (nums.get(i) < min) {
            min = nums.get(i);
        }
    }
    return min;
}

Self-check: Did you start min at nums.get(0) and loop from index 1? Did you flip the comparison from > to <?

Reflect

  • What I changed from maxValue to get minValue:
  • My additional test call and its expected result:

Homework Hack

Part A — count at least. Write countAtLeast(ArrayList<Integer> nums, int threshold) that returns how many elements of nums are greater than or equal to threshold. Model it after countMatches.

Contract: nums may be empty.

Call Expected result
countAtLeast([3, 8, 1, 10, 6], 6) 3
countAtLeast([1, 2, 3], 5) 0
countAtLeast([], 0) 0

Write your solution in the cell below, then run the test cell after it.

public static int countAtLeast(ArrayList<Integer> nums, int threshold) {
    // Count and return how many elements are >= threshold.
    return 0;
}


ArrayList<Integer> countTest1 = new ArrayList<Integer>();
countTest1.add(3); countTest1.add(8); countTest1.add(1); countTest1.add(10); countTest1.add(6);
System.out.println(countAtLeast(countTest1, 6)); // expect 3

ArrayList<Integer> countTest2 = new ArrayList<Integer>();
countTest2.add(1); countTest2.add(2); countTest2.add(3);
System.out.println(countAtLeast(countTest2, 5)); // expect 0

ArrayList<Integer> countTest3 = new ArrayList<Integer>();
System.out.println(countAtLeast(countTest3, 0)); // expect 0
Reveal a solution after writing yours 
public static int countAtLeast(ArrayList<Integer> nums, int threshold) {
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums.get(i) >= threshold) {
            count++;
        }
    }
    return count;
}

Self-check: Does your method return 0 for an empty list without a special case? Did you use >= and not >?

Reflect

  • What I changed from countMatches to get countAtLeast:
  • My additional test call and its expected result:

Part B — remove negatives safely. Write removeNegatives(ArrayList<Integer> nums) that removes every negative value from nums in place, without skipping any element.

Contract: Modify nums directly; do not return a new list. nums may contain zero, one, or many negative values, and may already contain none.

Starting list List after the call
[3, -1, 5, -2, 0] [3, 5, 0]
[-1, -2, -3] []
[4, 5] [4, 5]

Write your solution in the cell below, then run the test cell after it.

public static void removeNegatives(ArrayList<Integer> nums) {
    // Traverse in a direction that is safe for removal.
}


ArrayList<Integer> test1 = new ArrayList<Integer>();
test1.add(3); test1.add(-1); test1.add(5); test1.add(-2); test1.add(0);
removeNegatives(test1);
System.out.println(test1); // expect [3, 5, 0]

ArrayList<Integer> test2 = new ArrayList<Integer>();
test2.add(-1); test2.add(-2); test2.add(-3);
removeNegatives(test2);
System.out.println(test2); // expect []

ArrayList<Integer> test3 = new ArrayList<Integer>();
test3.add(4); test3.add(5);
removeNegatives(test3);
System.out.println(test3); // expect [4, 5]
Reveal a solution after writing yours 
public static void removeNegatives(ArrayList<Integer> nums) {
    for (int i = nums.size() - 1; i >= 0; i--) {
        if (nums.get(i) < 0) {
            nums.remove(i);
        }
    }
}

Self-check: Does your loop start at the last index and move toward 0? Does it leave every non-negative value in its original order?

Reflect

  • The direction my loop traverses, and why:
  • What happens if I traverse forward instead, on [-1, -2, 3]:

Exit Ticket

  1. Why does maxValue start comparing at index 1 instead of index 0?
  2. What is the key difference between indexOf and a loop that counts every match?
  3. Why is it safe to build a new list with an enhanced for loop over the original, but unsafe to remove from the original during that same loop?
  4. When removing multiple elements by index from an ArrayList, why does traversing backward avoid skipped elements?
Exit-ticket key
  1. max is initialized with nums.get(0), so comparisons should begin at the next element to avoid comparing an element to itself.
  2. indexOf stops at the first match and reports only its position. A counting loop checks every element and can report how many matches exist in total.
  3. Building a new list only reads the original; its size and order never change during the loop. Removing from the original changes its size and shifts later elements, which the enhanced for loop does not expect.
  4. Removing a later index does not change the position of any earlier, unvisited index, so every index scheduled to be checked still gets checked exactly once.

6. Grading Plan (1 Point Total)

Part Points What earns the points
Popcorn (minValue) 0.25 Correctly models maxValue, starting at get(0) and comparing with <.
Homework Part A (countAtLeast) 0.25 Correct count for all three sample calls, including the empty-list case.
Homework Part B (removeNegatives) 0.25 Traverses backward and leaves every non-negative value in its original order.
Code quality and reflection 0.25 Every cell runs with visible output, and the Reflect prompts are answered in the student’s own words.
Total 1.0  

Quick Validation Checklist

  • Every Hack cell runs and prints visible output that matches the expected results.
  • minValue starts its accumulator at nums.get(0), not 0.
  • removeNegatives traverses from the last index to 0.
  • All three Reflect prompts are answered.
  • The Exit Ticket questions are answered before submitting.

7. Lesson Revisions & Feedback Evidence

Feedback Received: Lesson authors: what your peers said in the practice run.

Revision Made: Lesson authors: what you changed because of it.

References

College Board. (2025). AP Computer Science A course and exam description [Effective fall 2025]. See Topic 4.10, Implementing ArrayList Algorithms, p. 113, and Topic 4.9, ArrayList Traversals, p. 112.

Submit Assignment

Click to upload or drag and drop
PDF, ZIP, images, documents, or Jupyter notebooks (.ipynb) (Max 10MB per file)

Need to update a submission later? Open the submissions dashboard.