AP® Computer Science A review sheet from Aim for Five (aimforfive.com/csa/units/4/4-9)
Unit 4 · Topic 4.9
4.9 ArrayList Traversals
You traverse an ArrayList much like an array, with an indexed loop or an enhanced for loop. This topic covers both, and the special care needed when you remove elements during a traversal, which is where most ArrayList bugs come from.
Key terms
ArrayListtraversal- skipped elements
IndexOutOfBoundsExceptionConcurrentModificationException
Two ways to traverse
An indexed loop runs i from 0 to size() - 1 and uses get(i). An enhanced for loop visits each element in order. Both loops here add up the lengths of the names, so with "Ana" and "Bo" the total is 5 + 5 = 10:
int total = 0;
for (int i = 0; i < names.size(); i++)
{
total += names.get(i).length();
}
for (String n : names)
{
total += n.length();
}
System.out.println(total);
In the indexed loop, names.get(i).length() gets the element at index i and then calls a String method on it. Chained calls like this are everywhere in ArrayList code.
Use the indexed loop when you need positions, neighbors, or to change the list. Use the enhanced for loop when you only need to read each element. Using an index outside 0 to size() - 1 throws an IndexOutOfBoundsException. Traversals can also be done with recursion (4.17).
Removing while traversing
When you remove the element at index i, everything after it shifts left by one. The element that was at i + 1 is now at i. If the loop then does i++, it skips that element without ever checking it.
There are two standard fixes:
- Only move forward when you didn't remove. Increase
iin anelse, so after a removal you check the same index again. - Traverse backward, from
size() - 1down to 0. Removing an element only shifts elements you've already checked.
The backward fix
for (int i = nums.size() - 1; i >= 0; i--)
{
if (nums.get(i) % 2 == 0)
{
nums.remove(i);
}
}
This removes every even number correctly. Why does going backward work? When you remove the element at index i, only the elements after it shift, and those are the ones you've already checked. The next element to check, at i - 1, hasn't moved.
The forward version with the else works too. After a removal, i stays the same, so the element that just slid into index i gets checked on the next pass:
int i = 0;
while (i < nums.size())
{
if (nums.get(i) % 2 == 0)
{
nums.remove(i);
}
else
{
i++;
}
}
Never change the size inside an enhanced for
An enhanced for loop keeps track of where it is in the list. If you add or remove elements while it's running, it can throw a ConcurrentModificationException. So when you use an enhanced for loop on an ArrayList, don't add or remove elements. Calling set, or calling methods on the element objects, is fine.
Worked examples
Try each one yourself first, then open the solution.
- Example 1
The skipped element
This code is meant to remove all even numbers. What does it print, and why?
ArrayList<Integer> nums = new ArrayList<Integer>(); nums.add(4); nums.add(6); nums.add(7); nums.add(8); for (int i = 0; i < nums.size(); i++) { if (nums.get(i) % 2 == 0) { nums.remove(i); } } System.out.println(nums);Show the solutionHide the solution
- Step 1: Start: [4, 6, 7, 8],
i= 0. 4 is even, so remove it. The list is [6, 7, 8], and 6 is now at index 0. - Step 2:
i++makesi1, so 6 is never checked.get(1)is 7, which is odd. Nothing happens. - Step 3:
i= 2:get(2)is 8, which is even. Remove it: [6, 7]. - Step 4:
i= 3, and3 < 2is false, so the loop ends.
Answer: It prints
[6, 7]. The 6 was skipped because it shifted into index 0 right after the loop moved past index 0. Loop backward, or only increaseiwhen nothing was removed. - Step 1: Start: [4, 6, 7, 8],
- Example 2
Changing size in an enhanced for
wordsholds "go", "tree" and "sky". What happens when this runs?for (String w : words) { if (w.length() < 3) { words.remove(0); } }Show the solutionHide the solution
- Step 1: The first element, "go", has length 2, so
words.remove(0)runs during the enhancedforloop. - Step 2: Changing the list's size while an enhanced
forloop is traversing it isn't allowed. - Step 3: When the loop tries to move to the next element, Java detects the change and throws an exception.
Answer: It throws a
ConcurrentModificationException. Use an indexed loop when you need to remove elements. - Step 1: The first element, "go", has length 2, so
Common mistakes
- Removing in a forward loop and always doing
i++, which skips the element after each removal. - Adding or removing elements inside an enhanced
forloop. - Using
i <= list.size()as the loop condition, which runs one index past the end.
On the exam
- "Remove every element that…" is a classic free-response task for Question 3. Loop backward or use the
elsepattern, and say which in your head before you type.
Connected topics
Videos
Check yourself
4 questions on 4.9 ArrayList Traversals. Pick an answer to see if you got it, and why.
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) % 2 == 0)
{
list.remove(i);
}
}Which of the following represents the contents of list after the code segment executes?
Which of the following replacements for the for loop removes every even number from any ArrayList<Integer> named list that holds positive values?
Consider the following code segment.ArrayList<String> words = new ArrayList<String>();
words.add("sun");
words.add("moon");
for (String w : words)
{
if (w.length() > 3)
{
words.add("star");
}
}
System.out.println(words.size());What is printed as a result of executing the code segment?
Consider the following code segment.ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(3);
nums.add(6);
nums.add(9);
int total = 0;
for (int i = 0; i <= nums.size(); i++)
{
total += nums.get(i);
}
System.out.println(total);What is printed as a result of executing the code segment?
0 of 4 answered