Iterating safely

A teacher reads the class register aloud: "Asha, Ravi, Meera, Kiran." You are crossing out the names of students who have left. Suppose that halfway through, you rub out Ravi's name without telling the teacher. The teacher is now pointing at a row that no longer holds what they expect. They stop and say, "Hold on, the register changed."

Java behaves the same way. Walking through a collection from the first item to the last is called iterating, and the loop that does it is reading the collection as it goes. If you add or remove items from inside that loop, the collection and the loop disagree about where they are. Java would rather stop loudly than carry on with wrong answers, so it throws a ConcurrentModificationException. That is a long name for "the collection changed while you were reading it."

This lesson shows the three safe ways to walk a collection, and the one safe way to remove things while you do.

Remember: read freely, but change the list only through the tool that is doing the reading, or after the loop is over.

Every for (x : list) loop in Java uses a helper behind the scenes called an iterator. An iterator is a small object with a bookmark. It knows which item comes next, and it has two jobs: hasNext() answers "is there another item?", and next() hands over that item and moves the bookmark along.

Most collections also keep a version number that goes up every time you add or remove an item. When an iterator is created, it writes down the version it started with. On each step it compares: is the list still on the version I remember? If a removal happened behind its back, the numbers differ, and the iterator throws.

This design is called fail-fast, meaning it fails the moment it notices something is wrong rather than wandering on with bad data. Java describes it as a best effort, not a promise, so never write code that relies on the exception turning up. Treat it as a bug alarm.

Every block below can be pasted into jshell. Start with the loop you already know.

List<String> register = List.of("Asha", "Ravi", "Meera");
for (String name : register) {
    System.out.println(name);
}

Asha
Ravi
Meera

The for-each loop is the neatest way to read every item. It works on any collection. Use it whenever you only need to look.

Now the same walk written out by hand, which is what the compiler turns for-each into:

List<String> register = List.of("Asha", "Ravi", "Meera");
Iterator<String> it = register.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

Asha
Ravi
Meera

Now the trap. Here we cross out every name that ends in "a" while looping over the list:

List<String> register = new ArrayList<>(List.of("Asha", "Ravi", "Meera", "Kiran"));
try {
    for (String name : register) {
        if (name.endsWith("a")) {
            register.remove(name); // the loop is still reading the list
        }
    }
} catch (ConcurrentModificationException e) {
    System.out.println("Stopped by " + e.getClass().getSimpleName());
}

Stopped by ConcurrentModificationException

register.remove(name) changed the list, but the loop's iterator did not know. On the next step it saw a different version and stopped. We caught the exception here only so you can see it. In real code, a crash like this is a bug to fix, not to catch.

The fix is to let the iterator do the removing. It has a remove() method that deletes the item next() just returned, and it updates its own copy of the version, so it never gets confused.

List<String> register = new ArrayList<>(List.of("Asha", "Ravi", "Meera", "Kiran"));
Iterator<String> it = register.iterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.endsWith("a")) {
        it.remove(); // the iterator removes it, so it knows the list changed
    }
}
System.out.println(register);

[Ravi, Kiran]

Call remove() once after each next(), never twice in a row. Calling it before the first next(), or twice without a next() in between, throws an IllegalStateException.

The shortest fix is a method that does the whole loop for you. removeIf takes a rule and removes every item that matches it.

List<String> register = new ArrayList<>(List.of("Asha", "Ravi", "Meera", "Kiran"));
register.removeIf(name -> name.endsWith("a"));
System.out.println(register);

[Ravi, Kiran]

The rule name -> name.endsWith("a") is a lambda, which is a tiny function written inline: "given a name, answer true if it ends in a." You will write more of these in later lessons. Prefer removeIf when the job is simply "remove everything that matches".

One more tool exists for lists: a ListIterator. It can also set (replace) the item it just returned and add a new one beside it, again without upsetting anything. Problem 3 uses it.

Remember: to remove while looping, use Iterator.remove(). To remove everything that matches a rule, use removeIf.

To see why the exception happens, here is a small list that has the version number and the check. It is a cut-down ArrayList: an array, a size, and a version that goes up on every change.

static class TinyList<T> implements Iterable<T> {
    private Object[] items = new Object[4];
    private int size = 0;
    private int version = 0; // goes up on every add or remove

    void add(T value) {
        if (size == items.length) {
            items = Arrays.copyOf(items, size * 2);
        }
        items[size++] = value;
        version++;
    }

    void removeAt(int index) {
        System.arraycopy(items, index + 1, items, index, size - index - 1);
        items[--size] = null;
        version++;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<>() {
            private int position = 0;
            // The iterator writes down the version it started with.
            private final int expectedVersion = version;

            @Override
            public boolean hasNext() {
                return position < size;
            }

            @Override
            @SuppressWarnings("unchecked")
            public T next() {
                if (version != expectedVersion) {
                    throw new ConcurrentModificationException();
                }
                if (position >= size) {
                    throw new NoSuchElementException();
                }
                return (T) items[position++];
            }
        };
    }
}

Go through it in order.

• version starts at 0 and goes up by one in add and in removeAt. That is how the list notices it has changed.
• iterator() returns an anonymous class, meaning an object made on the spot without giving its class a name. It holds position, the bookmark, and expectedVersion, the version it wrote down at birth.
• next() checks first. If version has moved on, it throws ConcurrentModificationException. Only then does it hand back the item.
• The @SuppressWarnings("unchecked") is there because the array holds plain Objects, and we know they are really Ts.

Now remove from the list inside a for-each loop over it:

TinyList<String> register = new TinyList<>();
register.add("Asha");
register.add("Ravi");
register.add("Meera");
try {
    for (String name : register) {
        System.out.println("saw " + name);
        register.removeAt(0); // the version changes mid-loop
    }
} catch (ConcurrentModificationException e) {
    System.out.println("Stopped by " + e.getClass().getSimpleName());
}

saw Asha
Stopped by ConcurrentModificationException

The first step worked and printed "Asha". We then removed an item, so version moved on. The second next() compared the numbers and threw. That is the whole mechanism. The real ArrayList keeps the same kind of counter, and calls it modCount.

Two things to take from the table. First, a loop is always O(n), and what you do inside it decides whether the total grows much faster. Second, if you have a lot to remove from an ArrayList, removeIf is the kind choice, because one pass beats many shifts.

static void removeShort(List<String> names, int minLength) {
    throw new UnsupportedOperationException("remove every name shorter than minLength, in place");
}

static void removeShort(List<String> names, int minLength) {
    Iterator<String> it = names.iterator();
    while (it.hasNext()) {
        if (it.next().length() < minLength) {
            it.remove();
        }
    }
}

static void dropRepeats(List<Integer> sorted) {
    throw new UnsupportedOperationException("remove each number that equals the one before it");
}

static void dropRepeats(List<Integer> sorted) {
    Iterator<Integer> it = sorted.iterator();
    Integer previous = null;
    while (it.hasNext()) {
        Integer current = it.next();
        // equals, not ==: two Integer objects can hold the same number
        if (current.equals(previous)) {
            it.remove();
        } else {
            previous = current;
        }
    }
}

static void doubleAll(List<Integer> numbers) {
    throw new UnsupportedOperationException("replace every number with twice its value, in place");
}

static void doubleAll(List<Integer> numbers) {
    ListIterator<Integer> it = numbers.listIterator();
    while (it.hasNext()) {
        it.set(it.next() * 2); // set replaces the item next() just returned
    }
}

Iteration is a favourite because one short bug shows whether you understand how collections work.

• "Why does this loop throw ConcurrentModificationException?" Because the list was changed outside the iterator while the loop was running. The iterator's remembered version no longer matches the list's.
• "How do you remove while iterating?" Use Iterator.remove(), or removeIf for a rule. Name both, and say which you would pick.
• "What does fail-fast mean?" The iterator checks for changes on each step and throws immediately instead of returning wrong data. Add that it is best-effort: it is a bug alarm, not something to catch and rely on.
• "Is it only a threading problem?" No. The classic case is one thread, one loop, and a remove in the wrong place. The name says "concurrent", but the commonest cause is plain single-threaded code. Lesson 12 comes back to the multi-threaded kind.
• "Why does it.remove() need a next() first?" It removes the item next() just returned. With no item returned, there is nothing to remove, so it throws IllegalStateException.
• "Iterator or ListIterator?" ListIterator works on lists only, walks both ways, and can set and add. Use a plain Iterator for everything else.
• Say the cost. "A walk is O(n). Removing during the walk is O(1) on a LinkedList and O(n) per item on an ArrayList, so removeIf is better for many removals."

Made by VeraStack Labs