ArrayList Traversals
Why this matters
Imagine you're the designated DJ for a road trip with your friends. You've got a huge ArrayList of songs, but you need to make some edits. Maybe you want to find all the songs by Taylor Swift, or maybe you need to remove all the songs that are less than two minutes long because they kill the vibe. How do you go through the entire playlist, song by song, to check each one? You can't just magically know where they are. You have to start at the beginning and systematically check every single entry.
This process of "walking through" a list is called traversal. It's a fundamental skill in programming. In this lesson, we'll master the different ways to traverse an ArrayList, learn how to safely modify a list as we go, and sidestep the common exceptions that trip up so many students.
Concept overview
flowchart TD
A[Start: i = list.size() - 1] --> B{i >= 0?};
B -- Yes --> C{Is list.get(i) a value to remove?};
B -- No --> G[End];
C -- Yes --> D[list.remove(i)];
C -- No --> E[i--];
D --> E;
E --> B;
Core explanation
Hey everyone, it's Saavi. Let's talk about one of the most common things you'll ever do with an ArrayList: visiting every element inside it. This is called traversal.
Think of your ArrayList as a line of numbered mailboxes on a street. If you need to check every mailbox for a specific letter, you'd start at mailbox #0, then go to #1, then #2, and so on, until you reach the end. That's exactly what traversal is in code.
The Standard for Loop Traversal
The most classic and versatile way to traverse an ArrayList is with a standard for loop. It gives you precise control over the index.
Let's say we have an ArrayList of test scores and we want to print each one.
ArrayList<Integer> scores = new ArrayList<>();
scores.add(88);
scores.add(92);
scores.add(77);
scores.add(100);
// Start at index 0, go up to (but not including) the size, increment by 1
for (int i = 0; i < scores.size(); i++) {
<figure class="lesson-figure"><div class="shr-widget" data-shr-widget="{"code":["ArrayList<Integer> scores = new ArrayList<>();","scores.add(88); scores.add(92); scores.add(77); scores.add(100);","","for (int i = 0; i < scores.size(); i++) {"," System.out.println(\"Score at index \" + i + \": \" + scores.get(i));","}"],"type":"for_loop_trace","array":[88,92,77,100],"trace_steps":[{"line":4,"vars":{"i":0},"output":"Score at index 0: 88","highlight_cell":0},{"line":4,"vars":{"i":1},"output":"Score at index 1: 92","highlight_cell":1},{"line":4,"vars":{"i":2},"output":"Score at index 2: 77","highlight_cell":2},{"line":4,"vars":{"i":3},"output":"Score at index 3: 100","highlight_cell":3}]}" aria-label="An animation showing a for loop iterating through an ArrayList of scores, highlighting the current index and updating the printed output."></div><figcaption class="lesson-figure-caption">Tracing a standard `for` loop accessing elements by index.</figcaption></figure>
// Use .get(i) to access the element at the current index
System.out.println("Score at index " + i + ": " + scores.get(i));
}Output:
Score at index 0: 88
Score at index 1: 92
Score at index 2: 77
Score at index 3: 100Notice the loop condition: i < scores.size(). We use < and not <=. This is critical. If our list has 4 elements, the indices are 0, 1, 2, and 3. scores.size() is 4. If we tried to access scores.get(4), the program would crash with an IndexOutOfBoundsException because that "mailbox" doesn't exist.
The Enhanced for Loop (The "for-each" Loop)
If you only need to read the elements and don't care about their index, Java gives us a cleaner, simpler syntax: the enhanced for loop.
It’s like saying, "for each score in the scores list, do this."
ArrayList<String> friends = new ArrayList<>();
friends.add("Maya");
friends.add("Carlos");
friends.add("Priya");
// "For each String named 'friendName' in the 'friends' list..."
for (String friendName : friends) {
System.out.println("Hello, " + friendName + "!");
}Output:
Hello, Maya!
Hello, Carlos!
Hello, Priya!It’s clean and less prone to off-by-one errors. But it has a major limitation...
The Big Trap: Modifying an ArrayList While Traversing
The Danger of the Enhanced for Loop
You should not add or remove elements from an ArrayList while traversing it with an enhanced for loop. If you try, Java will throw a ConcurrentModificationException.
Think of it this way: the enhanced for loop is like a tour guide who has a fixed itinerary. If you suddenly try to bulldoze one of the buildings on the tour (remove an element), the guide gets confused and immediately stops the tour to prevent further chaos. It's a safety feature.
So, if you need to modify the list, the enhanced for loop is not the right tool.
The for Loop Deletion Problem
"Okay, Saavi," you might say, "I'll just use a standard for loop to remove elements." Great idea! But there's a subtle trap here, too.
Let's try to remove all names shorter than 5 characters from a list.
ArrayList<String> names = new ArrayList<>();
names.add("Liam"); // length 4
names.add("Sofia"); // length 5
names.add("Noah"); // length 4
names.add("Aaliyah"); // length 7
// Let's try removing names shorter than 5 letters...
for (int i = 0; i < names.size(); i++) {
if (names.get(i).length() < 5) {
names.remove(i); // Uh oh...
}
}
System.out.println(names); // [Sofia, Noah, Aaliyah]Wait, "Noah" is still in the list! Why?
Let's trace it.
i = 0:names.get(0)is "Liam". Its length is 4. We remove it. The list is now[Sofia, Noah, Aaliyah]. Crucially, "Sofia" is now at index 0, and "Noah" is at index 1.- The loop increments
ito 1. i = 1: The loop now checksnames.get(1), which is "Noah". It completely skipped "Sofia" because "Sofia" slid down into the spot we just emptied.i = 1:names.get(1)is "Noah". Its length is 4. We remove it. The list is now[Sofia, Aaliyah].- The loop increments
ito 2. i = 2: The loop conditioni < names.size()(is 2 < 2?) is now false. The loop ends.
The final list is [Sofia, Aaliyah]. We successfully removed "Liam" but our logic was flawed and we missed one. On the AP exam, this flawed logic would produce [Sofia, Noah, Aaliyah] because the second short name is skipped.
The Solutions for Safe Deletion
You have two reliable ways to solve this.
1. Traverse Backwards: If you go from the end of the list to the beginning, removing an element doesn't affect the indices of the elements you still need to visit.
for (int i = names.size() - 1; i >= 0; i--) {
if (names.get(i).length() < 5) {
names.remove(i);
}
}
System.out.println(names); // [Sofia, Aaliyah] -> This works!2. Adjust the Index When Traversing Forward:
If you must go forward, you can manually correct for the shift. When you remove an element at index i, the next element slides into index i. To avoid skipping it, you need to decrement i so the loop re-evaluates the same index on the next iteration.
for (int i = 0; i < names.size(); i++) {
if (names.get(i).length() < 5) {
names.remove(i);
i--; // Counteract the i++ in the loop header
}
}
System.out.println(names); // [Sofia, Aaliyah] -> This also works!While both are correct, traversing backwards is generally considered cleaner and less error-prone. It's my go-to recommendation.
See it in action
Worked examples
Let's walk through a couple of common scenarios you'll face on the AP exam.
Calculating the Average
Problem: You're given an ArrayList of Integer objects representing the daily high temperatures in Boston for a week. Write a method calculateAverage that takes this list and returns the average temperature as a double.
Solution Walkthrough:
- 1The GoalTo find the average, we need the sum of all temperatures and the total number of days.
- 2The TraversalWe need to visit every element to add it to a running total. Since we are only reading the data, we can use a simple enhanced for-each loop.
- 3The Code
public double calculateAverage(ArrayList<Integer> temps) { // If the list is empty, the average is 0 to avoid division by zero. if (temps.size() == 0) { return 0.0; } double sum = 0.0; // Use a double for the sum to maintain precision. // Use an enhanced for-loop for simple, read-only traversal. for (Integer temp : temps) { sum += temp; // Add each temperature to the sum. } // The average is the sum divided by the number of elements. return sum / temps.size(); } - 4Why this worksThe enhanced for-loop is perfect here. It's readable and handles the iteration for us. We initialize a
sumto zero, loop through each temperature, add it to the sum, and finally, divide by the list's size. We use adoublefor the sum to prevent integer division, which would truncate any decimal part.
Removing Failing Grades
Problem: A teacher, Mr. Davis, has an ArrayList of student scores. He wants to remove all scores below 60. Write a method removeFailing that modifies the list in place.
Solution Walkthrough:
- 1The GoalTraverse a list and remove elements that meet a certain condition (score < 60).
- 2The ChallengeWe are modifying the list while traversing. This means an enhanced for-loop is out, and a standard
forloop needs to be handled carefully. - 3The Wrong MoveA common mistake is to write a simple forward loop without adjusting the index. As we saw, this skips elements after a removal.
- 4The Correct Approach (Traversing Backwards)This is the safest and cleanest way. By starting at the end, removing an element at index
idoesn't change the index of any elements ati-1,i-2, etc., which are the ones we still have to check.public void removeFailing(ArrayList<Integer> scores) { // Traverse backwards from the end of the list to the beginning. for (int i = scores.size() - 1; i >= 0; i--) { // Check the condition for removal. if (scores.get(i) < 60) { // Remove the element at the current index. scores.remove(i); } } } - 5Why this worksLet's say the list is
[85, 45, 90, 59].i = 3:scores.get(3)is 59. It's < 60. Remove it. List is now[85, 45, 90].i = 2:scores.get(2)is 90. It's not < 60. Do nothing.i = 1:scores.get(1)is 45. It's < 60. Remove it. List is now[85, 90].i = 0:scores.get(0)is 85. It's not < 60. Do nothing. The loop finishes, and the list is correctly modified to[85, 90]. No elements were skipped.
Try it yourself
Ready to try a couple on your own? Think through the logic, especially if you need to modify the list.
- 1Word FilterWrite a method
filterLongWordsthat takes anArrayList<String>and anint minLength. It should return a newArrayList<String>containing only the words from the original list that areminLengthor longer.- Hint: Since you're creating a new list, you don't have to worry about the tricky removal logic. A simple traversal to read from the old list and
addto the new one is perfect. Which type of loop is cleanest for that?
- Hint: Since you're creating a new list, you don't have to worry about the tricky removal logic. A simple traversal to read from the old list and
- 2In-Place DoublerWrite a method
doubleValuesthat takes anArrayList<Integer>. The method should modify the list in place, replacing every value with two times its original value. For example,[1, 5, 10]should become[2, 10, 20].- Hint: You need to change the elements, but not add or remove them. This means you need access to the index to use the
set(index, value)method. Which loop gives you easy access to the index?
- Hint: You need to change the elements, but not add or remove them. This means you need access to the index to use the
Practice — 8 questions
In simple terms, ArrayList traversal is about visiting each item in a list, one by one, to read, change, or remove it, just like checking off tasks on a to-do list.
ArrayList<Integer> scores = new ArrayList<>();
scores.add(88);
scores.add(92);
scores.add(77);
scores.add(100);
// Start at index 0, go up to (but not including) the size, increment by 1
for (int i = 0; i < scores.size(); i++) {
[[fig:standard_for_loop_trace]]
// Use .get(i) to access the element at the current index
System.out.println("Score at index " + i + ": " + scores.get(i));
}- 4.9.A: Develop code used to traverse the elements of an ArrayList and determine the results of these traversals.
- 4.9.A.1
- Traversing an ArrayList is when iteration or recursive statements are used to access all or an ordered sequence of the elements in an ArrayList.
- 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.3
- Attempting to access an index value outside of its range will result in an IndexOutOfBoundsException.
- 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.
flowchart TD
A[Start: i = list.size() - 1] --> B{i >= 0?};
B -- Yes --> C{Is list.get(i) a value to remove?};
B -- No --> G[End];
C -- Yes --> D[list.remove(i)];
C -- No --> E[i--];
D --> E;
E --> B;
Read what Saavi narrates
(upbeat, warm intro music)
Hey everyone, it's Saavi from Shrutam. Let's talk about a core skill you'll use constantly in AP Computer Science: ArrayList traversals.
Imagine you're the DJ for a road trip. You've got a huge playlist, but you need to make some edits... maybe remove all the songs that are too short. How do you go through the entire playlist, song by song, to check each one? You have to start at the beginning and systematically check every single entry. This process of "walking through" a list is called traversal. It's all about accessing every element in an ArrayList in a specific order, usually from first to last, so we can examine or modify each piece of data.
Now, let's work through a really common and important example: removing items from a list as you go. This is where things can get tricky.
Let's say a teacher, Mr. Davis, has an ArrayList of student scores, and he wants to remove all scores below 60. The goal is to traverse the list and remove elements that meet that condition. A common mistake is to just loop from the beginning to the end. But if you remove an item, the list shrinks, and everything after it shifts down one spot. Your loop counter, however, keeps marching forward, causing it to skip the very next item. It's a classic bug.
So, what's the right way? The safest and cleanest approach is to traverse backwards. Start your loop at the end of the list and work your way to the beginning.
Imagine a for loop that starts with an index set to the last position in the list... that's the list's size minus one. The loop continues as long as the index is greater than or equal to zero, and it decrements the index each time. Inside the loop, you check if the score at the current index is less than sixty. If it is, you remove it.
Why does this work so well? Because when you remove an item, it only affects the indices of items that come *after* it in the list. But since you're going backwards, you've already processed all those items! You never have to worry about skipping one.
One of the most common mistakes I see is when students try to use an enhanced for-loop, that's the "for-each" loop, to remove elements. Don't do it! Java will actually stop you with an error called a Concurrent Modification Exception. Think of it as a safety feature. That loop is designed for reading data, not changing the size of the list while you're in the middle of using it.
So remember: when you need to remove items, a backwards for-loop is your best friend. It's clean, it's safe, and it always gets the job done right.
You've got this. Keep practicing, and don't be afraid to trace your code on paper to see how the list changes. Happy coding!
(upbeat, warm outro music)
This throws a `ConcurrentModificationException`. The enhanced loop isn't designed for the list's size to change during its execution.
Use a standard `for` loop, either by traversing backward or by decrementing the index after a removal.
When you remove `list.get(i)`, the element that was at `i+1` shifts to index `i`. The loop's `i++` then moves to `i+1`, skipping the element that just shifted into the current spot.
After calling `list.remove(i)`, add the line `i--;`. Better yet, just traverse backward from `list.size() - 1` down to 0.
The valid indices for an `ArrayList` are from `0` to `size() - 1`. On the last iteration, `i` will equal `list.size()`, and `list.get(list.size())` will throw an `IndexOutOfBoundsException`.
Always use `<` in the condition: `for (int i = 0; i < list.size(); i++)`.
In `for (String name : names)`, the `name` variable holds the *actual element* ("Maya", "Carlos"), not its index (0, 1). Trying to do `names.get(name)` makes no sense and won't compile if `name` isn't an integer.
Remember that the enhanced loop gives you the element itself. Just use the loop variable directly.
While creating a new list is a valid filtering strategy, it doesn't meet the requirements of the problem. The AP exam often tests your ability to modify a data structure directly.
Read the prompt carefully. If it says to modify the list in place, you must use a technique like the backward traversal loop to remove elements from the original list.