AP Computer Science A · Unit 4 lecture · Part 8 of 14 · 11 min

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

Mr. Thompkins
Looping through an ArrayList is exactly like looping through an array, with size() and get(i) instead of length and brackets. Exactly like it, that is, until you remove something. Then the floor moves under your feet.

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()?
Three different things. An array uses the field length: arr.length. A String uses the method length(): s.length(). An ArrayList uses the method size(): list.size(). The exam will offer you the wrong one in a choice, so match the type every time.

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);
  1. line 2 i goes up on every pass, even after a remove
  2. line 6 The next word slides into index i and is never checked
output › [cup, kettle]
A forward loop that removes. Short words should all be gone, but "cup" survives.
iwords.get(i)actionlist after
0tearemove[cup, mug, kettle, pot]
1mugremove (cup was skipped)[cup, kettle, pot]
2potremove[cup, kettle]
33 < 2 is false: stop[cup, kettle]
The trace. After "tea" is removed, "cup" slides to index 0, and i moves on to 1.

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);
  1. line 2 Backward: a removal only shifts items you already checked
output › [kettle]
The same job, backward. Every short word is removed.
Pause and think
Write the while loop version in your head: start at i = 0, and decide when to do i++. What does it leave in words?
I thought about it. Show me
int i = 0; while (i < words.size()) { if (words.get(i).length() < 4) { words.remove(i); } else { i++; } }. After a removal, i stays put, so the element that slid into index i gets checked next. It leaves [kettle], the same as the backward loop.

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}
  1. line 2 An enhanced for over a list
  2. line 6 Changing the size inside it breaks the loop
output › Exception in thread "main" java.util.ConcurrentModificationException
Changing the size of the list that an enhanced for is walking through.
?Wait, so when is an enhanced for safe with an ArrayList?
Whenever the list's size doesn't change during the loop: reading every element, calling methods on the elements, or adding to a different list. For any add or remove on the list you're walking, use an index loop.

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}
  1. line 4 Build a new list; the original is only read
  2. line 9 Adding to a different list is safe in an enhanced for
  3. line 16 Same max pattern as arrays: start with element 0
  4. line 19 Strict >, so the first of two equal lengths wins
output › longOnes([Jo, Priya, Sam, Marisol], 4) is [Priya, Marisol] longest([fig, plum, kiwi, mango, lime]) is "mango"
Filter into a new list, and find the longest String.
Write the method
Write removeBelow(ArrayList<Integer> list, int min), which removes every element less than min and returns how many it removed. For [8, 3, 5, 1, 9, 4] and min 5, it returns 3 and the list becomes [8, 5, 9].
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);
  1. line 5 Backward traversal
  2. line 7 get returns an Integer; < unboxes it
  3. line 9-10 Remove, and count it
output › 3 [8, 5, 9]
  1. 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.
  2. Keep a counter for the return value: int removed = 0; before the loop.
  3. Test each element: if (list.get(i) < min). get returns an Integer, which unboxes for the comparison.
  4. Inside the if: list.remove(i); removed++;
  5. 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
  1. Removing inside a loop: which direction is safe?
  2. You need a counter that survives the loop. Declare it before the loop.
  3. The return goes after the loop, not inside it.
Check yourself
What is printed?
// 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);
  1. A[4, 5, 8]
  2. B[5]
  3. C[5, 8]
  4. 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.

Exam tip from Mr. T

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.