4.9-4.10 ArrayList traversals and algorithmsLooping through a list that changes

The standard traversal is for (int i = 0; i < list.size(); i++), with list.get(i) as the current element. An enhanced for, for (String w : words), also works for reading every element. All the array algorithms from 4.5 carry over: sums, counts, max and min, any and all, neighbors.
?Wait, is it length, length() or size()?
The removal trap
Here's the trap. When you remove the element at index i, every later element slides one index to the left, so the element that was at i + 1 is now at i. If the loop then does i++, it jumps right over that element and never checks it.
1// words holds [tea, cup, mug, kettle, pot]2for (int i = 0; i < words.size(); i++)13{4 if (words.get(i).length() < 4)5 {6 words.remove(i);27 }8}9System.out.println(words);
- line 2 i goes up on every pass, even after a remove
- line 6 The next word slides into index i and is never checked
| i | words.get(i) | action | list after |
|---|---|---|---|
| 0 | tea | remove | [cup, mug, kettle, pot] |
| 1 | mug | remove (cup was skipped) | [cup, kettle, pot] |
| 2 | pot | remove | [cup, kettle] |
| 3 | 3 < 2 is false: stop | [cup, kettle] |
There are two standard fixes. The cleanest is to traverse backward, from size() - 1 down to 0. A removal then only shifts elements you've already checked. The other is a while loop that only does i++ when it keeps the element, so after a removal it looks at the same index again.
1// words holds [tea, cup, mug, kettle, pot]2for (int i = words.size() - 1; i >= 0; i--)13{4 if (words.get(i).length() < 4)5 {6 words.remove(i);7 }8}9System.out.println(words);
- line 2 Backward: a removal only shifts items you already checked
I thought about it. Show me
And the enhanced for? Never add to or remove from a list while an enhanced for is traversing that same list. Java notices the size changed underneath it and throws a ConcurrentModificationException.
1// pets holds [cat, dog, eel]2for (String p : pets)13{4 if (p.equals("dog"))5 {6 pets.add("pup");27 }8}
- line 2 An enhanced for over a list
- line 6 Changing the size inside it breaks the loop
?Wait, so when is an enhanced for safe with an ArrayList?
Building and changing lists
ArrayList algorithms add two moves to the array toolbox: inserting and deleting elements. A common pattern is to build a brand new list from the old one, keeping only what passes a test. Another is to find the max or min of something about each element, like its length.
1public static ArrayList<String> longOnes(2 ArrayList<String> names, int min)3{4 ArrayList<String> result = new ArrayList<String>();15 for (String n : names)6 {7 if (n.length() >= min)8 {9 result.add(n);210 }11 }12 return result;13}1415public static String longest(ArrayList<String> words)16{317 String best = words.get(0);18 for (int i = 1; i < words.size(); i++)19 {420 if (words.get(i).length() > best.length())21 {22 best = words.get(i);23 }24 }25 return best;26}
- line 4 Build a new list; the original is only read
- line 9 Adding to a different list is safe in an enhanced for
- line 16 Same max pattern as arrays: start with element 0
- line 19 Strict >, so the first of two equal lengths wins
1public static int removeBelow(ArrayList<Integer> list,2 int min)3{4 int removed = 0;5 for (int i = list.size() - 1; i >= 0; i--)16 {7 if (list.get(i) < min)28 {9 list.remove(i);310 removed++;311 }12 }13 return removed;14}15// list holds [8, 3, 5, 1, 9, 4]16System.out.println(removeBelow(list, 5) + " " + list);
- line 5 Backward traversal
- line 7 get returns an Integer; < unboxes it
- line 9-10 Remove, and count it
- It removes, so traverse backward: for (int i = list.size() - 1; i >= 0; i--).
Why?
Backward means a removal never makes you skip an element. - Keep a counter for the return value: int removed = 0; before the loop.
- Test each element: if (list.get(i) < min). get returns an Integer, which unboxes for the comparison.
- Inside the if: list.remove(i); removed++;
- After the loop, return removed;. Check: 4, 1 and 3 are removed (in that order, from the back), 3 in all, leaving [8, 5, 9].
Answer: Traverse backward, remove each element below min while counting, and return the count. For the example it returns 3 and leaves [8, 5, 9].
Stuck? Get a hint
- Removing inside a loop: which direction is safe?
- You need a counter that survives the loop. Declare it before the loop.
- The return goes after the loop, not inside it.
// nums holds [2, 4, 5, 6, 8]
for (int i = 0; i < nums.size(); i++)
{
if (nums.get(i) % 2 == 0)
{
nums.remove(i);
}
}
System.out.println(nums);- A[4, 5, 8]
- B[5]
- C[5, 8]
- D[4, 5, 6, 8]
Show the answer
A. i = 0 removes 2, and 4 slides to index 0. i = 1 checks 5 (odd). i = 2 removes 6, and 8 slides to index 2. Then i = 3 is not less than size 3, so the loop ends. The 4 and the 8 were skipped: [4, 5, 8]. The second choice is what the programmer wanted, which needs a backward loop.

FRQ 3, Data Analysis with ArrayList, is worth 5 points and almost always involves a list of objects. Expect points for traversing every element, calling the right methods on each object, the condition, adding or removing correctly, and the return. A forward loop that removes loses the "without skipping" point.
- Traverse with for (int i = 0; i < list.size(); i++) and list.get(i), or an enhanced for to read.
- A removal shifts later elements left. Traverse backward, or only do i++ when you keep the element.
- Never change a list's size inside an enhanced for over that list: ConcurrentModificationException.
- Building a new list with add is a safe way to filter.