JAVA / COLLECTIONS
Iterators, fail-fast behaviour and safe removal
Remove elements from a collection while iterating without hitting ConcurrentModificationException, and explain exactly what fail-fast checks and when.
What you will learn
- Rewrite a deleting for-each as an explicit Iterator loop with it.remove()
- Predict when a mid-loop edit throws and when it silently skips an element
- Tell a structural change from a value change such as Map.Entry.setValue
- Pick between removeIf, Iterator.remove and iterating over a copy
Understanding Iterators, fail-fast behaviour and safe removal
An iterator is a small separate object that remembers a position inside a collection. A for-each loop over an Iterable is compiled into iterator(), hasNext() and next() calls, so every for-each already has one; you simply have no variable to call remove() on. For ArrayList that object is little more than an int cursor plus a copy of the list's modification counter, and because the cursor lives outside the list, the list will happily shift elements out from under it.
Every structural change, meaning one that changes the size, increments a field named modCount on the collection. When an iterator is created it copies that number into expectedModCount, and next() compares the two before doing any work; a mismatch means something edited the collection behind the iterator's back, so it throws ConcurrentModificationException instead of returning a shifted or wrong element. The check sits in next() rather than hasNext(), and hasNext() on ArrayList is just cursor != size, so deleting the second-to-last element lets size drop to meet the cursor, the loop ends quietly, and the last element is never visited.
Iterator.remove() is the one edit an iterator survives, because the iterator performs it: ArrayList's version deletes the element next() last returned, moves the cursor back to that index so nothing is skipped, then re-copies modCount into expectedModCount. That is also why remove() must follow exactly one next(); with nothing last returned it throws IllegalStateException. For a plain predicate, removeIf does the same walk in one call inside the collection, and when you need to add while reading, iterate over a copy and mutate the original.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
public class FailFast {
public static void main(String[] args) {
List<String> a = new ArrayList<>(Arrays.asList("ant", "bee", "cow", "doe"));
try {
for (String s : a) {
if (s.equals("bee")) {
a.remove(s);
}
}
} catch (ConcurrentModificationException e) {
System.out.println("for-each threw " + e.getClass().getSimpleName());
System.out.println("list after the failed loop: " + a);
}
List<String> b = new ArrayList<>(Arrays.asList("ant", "bee", "cow", "doe"));
Iterator<String> it = b.iterator();
while (it.hasNext()) {
if (it.next().equals("bee")) {
it.remove();
}
}
System.out.println("iterator.remove gave: " + b);
List<String> c = new ArrayList<>(Arrays.asList("ant", "bee", "cow", "doe"));
c.removeIf(s -> s.equals("bee"));
System.out.println("removeIf gave: " + c);
}
}An iterator carries its own cursor and its own copy of the collection's structural-modification count, so the only edit it can survive mid-loop is one it makes itself.
Worked examples
The removal that does not throw
Deleting the second-to-last element during a for-each ends the loop early instead of raising an exception.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SilentSkip {
public static void main(String[] args) {
List<String> animals = new ArrayList<>(Arrays.asList("ant", "bee", "cow", "doe"));
for (String s : animals) {
System.out.println("visited " + s);
if (s.equals("cow")) {
animals.remove(s);
}
}
System.out.println("no exception, list is " + animals);
}
}Example explained
Line 1hasNext() on ArrayList's iterator is exactly cursor != size, with no modification check in it.
Line 2After next() returns "cow" the cursor is 3; removing it drops size to 3, so hasNext() reports false.
Line 3next() therefore never runs again and the modCount comparison that would have thrown never happens.
Line 4"doe" is missing from the loop, not from the list, so the bug shows up as a skipped element rather than a stack trace.
Value change versus structural change
Entry.setValue leaves a map iterator valid, while adding one new key invalidates it immediately.
import java.util.ConcurrentModificationException;
import java.util.LinkedHashMap;
import java.util.Map;
public class Structural {
public static void main(String[] args) {
Map<String, Integer> stock = new LinkedHashMap<>();
stock.put("nails", 5);
stock.put("screws", 2);
for (Map.Entry<String, Integer> e : stock.entrySet()) {
e.setValue(e.getValue() * 10);
}
System.out.println("setValue is fine: " + stock);
try {
for (String key : stock.keySet()) {
stock.put(key + "!", 0);
}
} catch (ConcurrentModificationException ex) {
System.out.println("new key broke the loop");
}
System.out.println("size is now " + stock.size());
}
}Example explained
Line 1e.setValue(...) writes through to the existing entry and leaves modCount untouched, so the entrySet iterator stays valid.
Line 2put with a key that already exists is non-structural too; only a new key or a removal bumps modCount.
Line 3The first put("nails!", 0) does add a mapping, so the iterator's next step sees the mismatch and throws.
Line 4The failure comes after one key was already inserted, which is why the map ends up with size 3 and a half-finished edit.
Editing in place with ListIterator
ListIterator.set and ListIterator.add change a list mid-walk without breaking the iteration.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;
public class Edits {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
ListIterator<Integer> it = nums.listIterator();
while (it.hasNext()) {
int n = it.next();
if (n % 2 == 0) {
it.set(n * n);
} else {
it.add(0);
}
}
System.out.println(nums);
System.out.println("hasPrevious=" + it.hasPrevious());
}
}Example explained
Line 1it.set(n * n) overwrites the element next() just returned and changes no size, so no counter moves.
Line 2it.add(0) inserts at the cursor and then steps over it, so each inserted 0 is never returned by next().
Line 3Both methods resync expectedModCount themselves, which is why the list can grow during the walk.
Line 4add() clears the record of the last returned element, so calling it.remove() straight after it would throw IllegalStateException.
Important notes
Fail-fast is best effort: modCount is an ordinary unsynchronised int, so it reliably catches accidental single-threaded edits but is no protection against two threads.
CopyOnWriteArrayList and ConcurrentHashMap hand out weakly consistent iterators that never throw ConcurrentModificationException but may not show edits made after the iterator was created, and the CopyOnWriteArrayList iterator rejects remove() outright.
Common mistakes
Calling list.remove(x) inside a for-each and trusting it because a small test passed; the same code throws ConcurrentModificationException on other data, or silently leaves the following element unprocessed.
Calling it.next() twice in one pass, once in the condition and once in the body; the loop consumes two elements per round and hits NoSuchElementException on an odd-sized collection.
Calling it.remove() before any next(), or twice after one next(); both throw IllegalStateException because remove deletes whatever next() last returned and there is nothing to delete.
Try it yourself
Change, predict, then run
Build new ArrayList<>(Arrays.asList("a", "b", "c", "d")) and delete "c" three ways: a for-each with list.remove that prints each element visited, an explicit Iterator with it.remove(), and removeIf. Compare which elements each loop actually visited.
Open the Java workspaceCheck your understanding
A four-element ArrayList is walked with a for-each loop and the third element is removed with list.remove when it is reached. No exception is thrown and the fourth element is never printed. Why?
- hasNext() only compares the cursor to the current size, so after the removal cursor 3 equals size 3 and the loop ends before next() can run its modCount check
- ArrayList tolerates one structural change per iteration and only reports the second one
- Removing the element that next() just returned always resyncs expectedModCount, whichever method performs the removal
- The comodification check runs in hasNext(), which reported the mismatch as an ordinary end of iteration
Show answer
The comparison of modCount against expectedModCount lives in next() and remove(), while hasNext() is nothing more than cursor != size; shrinking the list makes size meet the cursor, so the loop exits before any check runs and the last element is skipped. Option 3 is tempting because that resync really does happen, but only inside Iterator.remove(); list.remove() knows nothing about the iterator, so the counters stay out of step and the list is quietly left with an unvisited element.