PHASE 9Intermediate ~30 min· topic 9 of 13

Topic 9.9

Iterators and Fail-Fast Behaviour

In one line

An Iterator walks a collection one element at a time and is what every for-each loop uses behind the scenes. Most java.util iterators are fail-fast: if the collection is structurally changed by anything other than the iterator itself, the next step throws ConcurrentModificationException.

Think of it like this

A teacher taking the register reads down the class list with a finger on the current name. If the teacher crosses out a name with their own pen as they go, the finger stays in the right place. But if someone else grabs the list and adds or removes names while the teacher is reading, the finger is now pointing at the wrong line, so a careful teacher stops and says "the list changed under me!". That's a fail-fast iterator.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Iterator: An object that walks through a collection one element at a time, remembering where it is.
Iterable: Anything that can hand out an iterator, and so can be used in a for-each loop.
Structural modification: A change to a collection's size or shape: adding, removing, clearing. Replacing a value in place isn't one.
modCount: A counter in the collection that increases on every structural change.
Fail-fast: Stopping with an exception as soon as a problem is detected, rather than carrying on with possibly wrong data.
ConcurrentModificationException: The exception a fail-fast iterator throws when the collection changed behind its back.
Snapshot iterator: An iterator that walks a frozen copy of the data taken when it was created.
Weakly consistent: An iterator that never throws on concurrent change but may or may not show changes made while it runs.

Step by step

01What a for-each loop really is

The compiler turns a for-each over a collection into an iterator loop. Decompile with javap -c and you'll see calls to iterator(), hasNext() and next(), plus a checkcast to the element type (generics are erased, Topic 8.6).

So for (String s : list) list.remove(s); is really "call list.remove while an iterator over list is in the middle of its walk".

Main.javawhole filejava

for (String s : names) {
    System.out.println(s);
}

// is compiled as:
for (Iterator<String> it = names.iterator(); it.hasNext(); ) {
    String s = it.next();
    System.out.println(s);
}

02How ArrayList's iterator detects a change

ArrayList.Itr has three fields: cursor (index of the next element), lastRet (index of the last returned element, or -1) and expectedModCount (a copy of modCount at creation).

next() first calls checkForComodification(), which throws if modCount != expectedModCount. Itr.remove() calls ArrayList.this.remove(lastRet), then sets cursor = lastRet, lastRet = -1 and expectedModCount = modCount, which is why removing through the iterator is safe and why a second remove() (with lastRet == -1) throws IllegalStateException.

ArrayList.java (simplified from the JDK)whole filejava

private class Itr implements Iterator<E> {
    int cursor;                       // index of next element to return
    int lastRet = -1;                 // index of last element returned; -1 if none
    int expectedModCount = modCount;

    public boolean hasNext() { return cursor != size; }

    public E next() {
        checkForComodification();
        int i = cursor;
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0) throw new IllegalStateException();
        checkForComodification();
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;  // stay in sync
    }

    final void checkForComodification() {
        if (modCount != expectedModCount) throw new ConcurrentModificationException();
    }
}

03Trace a CME step by step

List [asha, ben, cara, dev], loop removing names starting with b. Iteration 1 returns asha (cursor 1). Iteration 2 returns ben (cursor 2); names.remove("ben") shifts cara and dev left and makes modCount 5 while the iterator still expects 4. hasNext() checks 2 != 3: true. next() checks the counts: different, so CME.

Without the check, the iterator would have returned dev and silently skipped cara, which moved into index 1. Fail-fast turns that silent skip into a loud error.

Trace a CME step by stepdiagram

Rendering diagram…

04The second-to-last quirk

Remove the second-to-last element inside a for-each and something odd happens: no exception. After removing it, size drops by one and equals cursor, so hasNext() returns false and the loop ends before next() can check modCount. The last element is never visited.

This is why the Javadoc says fail-fast behaviour "cannot be guaranteed" and that CME "should be used only to detect bugs". Code that works in a test with one particular input can be wrong for another.

05The three safe ways to remove

1. Iterator.remove() inside an explicit iterator loop. 2. collection.removeIf(predicate), which is clearer and, for ArrayList, O(n) instead of O(n²). 3. Collect into a separate list and removeAll after the loop.

For maps, apply these to the views: map.entrySet().removeIf(e -> e.getValue() == 0), map.keySet().removeIf(...) or map.values().removeIf(...).

Changing an element in place is not structural: list.set(i, x) inside a for-each and map.put(existingKey, newValue) (or entry.setValue) during map iteration are both fine.

06Write your own Iterable

Implement Iterable<T> and return an Iterator<T> with hasNext and next, and your class works in for-each loops. remove has a default implementation that throws UnsupportedOperationException, so read-only iterators don't need it.

next() should throw NoSuchElementException when there's nothing left; that's part of the Iterator contract and what callers who don't check hasNext rely on.

Main.javawhole filejava

record Range(int from, int to) implements Iterable<Integer> {
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            int next = from;
            public boolean hasNext() { return next < to; }
            public Integer next() {
                if (!hasNext()) throw new NoSuchElementException();
                return next++;
            }
        };
    }
}

for (int i : new Range(1, 4)) System.out.print(i + " ");   // 1 2 3

Try it yourself

1
Remove the last element
In the fail-fast example, change the second loop to remove "dev" (the last element). Predict: exception or not? Run it. (It throws: after removal size is 3 but cursor is 4, so hasNext() returns true and next() detects the change.)
2
Call remove twice
In the first example, add a second it.remove(); right after the first. Predict the exception and its type before running (IllegalStateException).
3
A reversed range
Give Range a method Iterable<Integer> reversed() that returns a lambda () -> new Iterator<>() { ... } walking from the top down. Predict the for-each output for new Range(0, 20, 5).reversed().

Code & diagrams

Iterator by hand, iterator.remove and removeIf New tab

Expected output

removed 35
removed 18
after iterator.remove: [72, 90, 41]
after removeIf:        [72, 90, 41]
after set in loop:     [100, 95, 46]

Fail-fast in action, and the second-to-last quirk New tab

The second loop is just as buggy as the first; it only got lucky with hasNext().

Expected output

visit asha
visit ben
CME after removing ben; list is now [asha, cara, dev]
visit asha
visit ben
visit cara
no exception, but dev was never visited: [asha, ben, dev]

Make your own class work in for-each New tab

Iterator.remove's default implementation throws UnsupportedOperationException with the message "remove".

Expected output

for-each: 0 5 10 15
1 4 9
next: 0
then: range exhausted
remove: remove

Snapshot and map-view iteration New tab

Expected output

notify log
notify email
listeners now: [log, email, sms]
in stock: {bun=20, cake=40}

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Remove inside a for-each loop

Loop for (String n : names) { if (n.startsWith("b")) names.remove(n); } over [asha, ben, cara, dev].

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.util.ConcurrentModificationException

at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)

at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)

at Main.main(Main.java:6)

Break #2

Call iterator.remove twice

After one it.next(), call it.remove(); it.remove();.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.IllegalStateException

at java.base/java.util.ArrayList$Itr.remove(ArrayList.java:1062)

at Main.main(Main.java:9)

Myth vs fact

Myth

ConcurrentModificationException means two threads touched the collection.

Fact

Almost always it's one thread modifying a collection inside its own loop. "Concurrent" means "during the iteration", not "from another thread".

Myth

If my loop didn't throw, my removal logic is safe.

Fact

Fail-fast is best effort. Removing the second-to-last ArrayList element skips the last element silently. Use removeIf or Iterator.remove.

Myth

Any change during iteration causes CME.

Fact

Only structural changes do. list.set, entry.setValue and map.put for an existing key are allowed.

Myth

CopyOnWriteArrayList is a faster thread-safe ArrayList.

Fact

Every write copies the whole array. It's great for small, read-mostly lists like listener lists, and terrible for frequently written ones.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
HashMap iterators check modCount too, and so do the default forEach, replaceAll and removeIf implementations at the end of their passes. map.forEach((k, v) -> map.remove(k)) throws CME after the pass completes.
▸
The compiler only generates the iterator form when the expression's static type is an Iterable. For arrays it generates an index loop with a copy of the array reference, so reassigning the array variable inside the loop doesn't affect the iteration.
▸
Spliterator (Java 8) is the iterator's parallel-friendly sibling: it can split itself in half for parallel streams and reports characteristics such as SIZED, ORDERED and SORTED. ArrayList's spliterator is late-binding and fail-fast as well (Topic 10.8).
▸
Iterators hold a reference to their collection, so a long-lived iterator (stored in a field) keeps the whole collection reachable. Short-lived iterators are usually eliminated entirely by the JIT's escape analysis, so for-each over an ArrayList costs about the same as an index loop.

Remember this

1
Iterable<T> is the interface for anything you can loop over; it has one key method, iterator(). An Iterator<T> has hasNext() (is there another element?), next() (return it and move on) and remove() (remove the element next() just returned). Since Java 8, Iterator also has forEachRemaining(action), and Iterable has forEach(action).
2
The enhanced for loop (for (String s : list), Java 5) is compiler sugar. For an Iterable, the compiler rewrites it into for (Iterator<String> i = list.iterator(); i.hasNext(); ) { String s = i.next(); ... }. For an array, it becomes an ordinary index loop. So everything about iterators applies to every for-each loop over a collection.
3
Fail-fast works with the modCount field from Topic 9.2. Every structural modification (adding or removing elements, clearing, resizing a map; not set on a list or put on an existing map key) increments modCount. An iterator records expectedModCount when created and compares them in next() and remove(); if they differ, it throws ConcurrentModificationException (CME). The name is misleading: no second thread is needed, and most CMEs come from one thread changing a collection inside its own for-each loop.
4
The safe ways to remove while iterating: call iterator.remove() (it changes the collection and updates expectedModCount together), use removeIf(predicate) (Java 8, a single efficient pass), or collect what to remove and call removeAll afterwards. iterator.remove() may be called **once per next()**; a second call, or a call before the first next(), throws IllegalStateException.
5
Fail-fast is best effort, not a guarantee. ArrayList's hasNext() is just cursor != size, so removing the second-to-last element inside a for-each makes the loop end quietly without visiting the last element and without throwing. Never write code that relies on catching CME; treat it as a bug report.
6
Concurrent collections take different approaches. CopyOnWriteArrayList iterators work on a snapshot of the array taken when the iterator was created: they never throw and never see later changes. ConcurrentHashMap iterators are weakly consistent: they never throw, and may or may not reflect changes made during iteration (Topic 13.8). You can also make your own classes loopable by implementing Iterable.

Explain it without notes

How does a for-each loop over a List work under the hood?

What is a fail-fast iterator and how is it implemented?

Why is fail-fast described as "best effort"? Give an example where no exception is thrown.

What are the correct ways to remove elements from a collection while iterating over it?

Practice

Using an explicit Iterator, remove every negative number from [3, -1, 4, -1, 5, -9] and print the list and how many were removed.

Write an Iterable<Character> called Letters that yields the letters of a word in reverse order, and print "stack" reversed with a for-each loop.

Remove from a TreeMap<String, Integer> of {a=1, b=0, c=3, d=0} every entry whose value is 0 using a view, then double the remaining values with replaceAll. Print the map.

Trade-offs

↔
Fail-fast iterators catch bugs early at the cost of a counter check per step; snapshot iterators never fail but cost a full array copy per write; weakly consistent iterators never fail and never copy but may show a mix of old and new state.
↔
removeIf is clearer and faster than iterator removal for ArrayList, but only removes by a condition. When the decision depends on neighbours or position, an explicit Iterator/ListIterator is the tool.
↔
Implementing Iterable makes your types pleasant to use, but every iterator you write must handle NoSuchElementException and (if it supports removal) the IllegalStateException rules correctly.

Done when you can

Done when you can rewrite a for-each loop as the iterator loop it compiles to.
Done when you can explain modCount, expectedModCount and when CME is thrown.
Done when you can explain why removing the second-to-last element doesn't throw.
Done when you remove during iteration only with Iterator.remove, removeIf or a separate pass.
Done when you can implement Iterable for your own class.
Done when you know which iterators are fail-fast, snapshot or weakly consistent.

Command Palette

Words you'll meet

Step by step

01What a for-each loop really is

02How ArrayList's iterator detects a change

03Trace a CME step by step

04The second-to-last quirk

05The three safe ways to remove

06Write your own Iterable

Try it yourself

Remove the last element

Call remove twice

A reversed range

Code & diagrams

Break it on purpose

Remove inside a for-each loop

Call iterator.remove twice

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can