AP Computer Science A: Lesson 4.9

Traversing ArrayLists

Unit 4: Data Collections

This notebook serves as a complete lesson plan, presentation guide, code sandbox, and homework assignment for Topic 4.9.


πŸ–₯️ Presentation & Slide Deck

Slide 1: ArrayLists vs. Static Arrays

  • Title: Dynamic Traversal with ArrayList
  • Key Differences: Dynamic sizing via .size(), element retrieval via .get(i), and element removal via .remove(i).
  • Traversal Choices: Standard indexed for loop vs. Enhanced for-each loop.

πŸ—£οΈ Teacher Script:

β€œWhen working with dynamic lists, modifying the size while traversing creates major bugs if you aren’t careful. Today we master the famous Index-Shifting Trap!”

Slide 2: The Index-Shifting Bug

Goal: Remove all even numbers from [4, 2, 8, 3, 6].

Flawed Forward Loop:

Code Runner Challenge

Predict what is left after removing the even numbers, then run it and find which numbers were skipped

View IPYNB Source
// CODE_RUNNER: Predict what is left after removing the even numbers, then run it and find which numbers were skipped
import java.util.ArrayList;
import java.util.Arrays;

public class FlawedRemoval {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(4, 2, 8, 3, 6));
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) % 2 == 0) {
                list.remove(i); // Elements shift left, skipping adjacent elements!
            }
        }
        System.out.println(list); // Should be [3]. Is it?
    }
}
FlawedRemoval.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

πŸ—£οΈ Teacher Script:

β€œTrace this carefully: When index 0 (4) is removed, 2 shifts down to index 0. But the loop increments i to 1, looking at index 1 (8). 2 was completely skipped! To avoid this, we traverse backwards from list.size() - 1 down to 0.”

Slide 3: The Backward Traversal Solution

Code Runner Challenge

Run it and compare the result with the forward loop above

View IPYNB Source
// CODE_RUNNER: Run it and compare the result with the forward loop above
import java.util.ArrayList;
import java.util.Arrays;

public class BackwardRemoval {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(4, 2, 8, 3, 6));

        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) % 2 == 0) {
                list.remove(i); // Index shifts only affect already-processed elements!
            }
        }
        System.out.println(list); // Resulting list: [3]
    }
}
BackwardRemoval.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

πŸ“„ Student Homework Assignment Handout

Title: Vocabulary Filter Sandbox

Instructions:

  1. Complete the removeShortWords method below using a backward traversal.
  2. Answer the reflection question on ConcurrentModificationException.

Code Runner Challenge

Finish removeShortWords with a backward loop so all three checks print true

View IPYNB Source
// CODE_RUNNER: Finish removeShortWords with a backward loop so all three checks print true
import java.util.ArrayList;
import java.util.Arrays;

public class WordFilter {

    /**
     * Removes all words with fewer than 4 characters from the list.
     * Uses backward loop traversal.
     */
    public static void removeShortWords(ArrayList<String> words) {
        // TODO: loop from the last index down to 0 and remove words shorter than 4 characters
    }

    public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>(Arrays.asList("the", "cat", "jumped", "over", "a", "lazy", "dog"));
        removeShortWords(words);
        System.out.println(words);
        System.out.println(words.equals(Arrays.asList("jumped", "over", "lazy")));

        // Two short words next to each other: a forward loop skips the second one.
        ArrayList<String> pairs = new ArrayList<>(Arrays.asList("an", "it", "java"));
        removeShortWords(pairs);
        System.out.println(pairs.equals(Arrays.asList("java")));

        ArrayList<String> empty = new ArrayList<>();
        removeShortWords(empty);
        System.out.println(empty.isEmpty());
    }
}
WordFilter.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Short Answer Reflection

Question: Why does using an enhanced for loop (for (String w : words)) throw a ConcurrentModificationException when attempting to call words.remove(w) inside the loop?

Your Answer: (Explain the structural modification rule of enhanced for-each loops in Java)

Submit Assignment

Choose what to hand in: click Add to submission on each runner you want graded (hacks, popcorn hacks), and save it. Leaving out practice runners does not lower your grade, but a required hack you leave out is graded as missing. Your selection is sent as a Gist for automatic review.

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