☕ JavaCollections Framework

Iterator

Iterator is the fundamental traversal interface in the Java Collections Framework. Any class implementing Iterable<T> returns an Iterator<T> from its iterator() method, and that iterator is what the enhanced for-each loop uses under the hood. Iterator provides sequential access to elements one at a time, with the ability to remove the current element safely during traversal — something that direct index-based removal or Collection.remove() cannot do safely during iteration. Understanding Iterator means understanding the hasNext/next protocol, why ConcurrentModificationException occurs and when, how Iterator.remove() works correctly, and when to use Iterator directly versus the enhanced for loop. This entry covers the full Iterator contract, the fail-fast mechanism, safe element removal patterns, and iterator implementation.

The Iterator Contract — hasNext, next, remove

Iterator<T> defines three methods. hasNext() returns true if the iteration has more elements to deliver. next() returns the next element and advances the internal cursor; it throws NoSuchElementException if called when hasNext() returns false. remove() removes the element most recently returned by next() from the underlying collection; it is optional and throws UnsupportedOperationException if not supported; it throws IllegalStateException if called before the first next() call or if called twice in a row without an intervening next() call. The standard traversal pattern is: call hasNext() before every call to next() to guard against NoSuchElementException. For collections where the caller knows the exact size, the guard can be omitted, but the guarded pattern is always safe and is the convention. The remove() method is Iterator's most important feature beyond basic traversal. It removes the element that was most recently returned by next() — the "current" element. This removal is safe during iteration because the iterator owns the traversal cursor and adjusts it appropriately after removal. Collection.remove(element) called during iteration modifies the collection's structure without the iterator's knowledge, breaking the iterator's internal state. The enhanced for-each loop expands to an iterator loop — it calls iterator() to get the iterator, calls hasNext() before each iteration, and calls next() at the start of each iteration body. But the for-each loop provides no access to the iterator itself, so remove() cannot be called. To remove elements during iteration, the iterator must be used explicitly.

Java

// ── Basic iteration pattern ───────────────────────────────────────────
List<String> names = new ArrayList<>(
    List.of("Alice", "Bob", "Carol", "Dave", "Eve"));

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
    System.out.print(name + " ");
}
// Alice Bob Carol Dave Eve

// ── What the for-each loop compiles to ───────────────────────────────
// This:
for (String name : names) {
    System.out.println(name);
}
// Compiles to exactly this:
Iterator<String> _it = names.iterator();
while (_it.hasNext()) {
    String name = _it.next();
    System.out.println(name);
}

// ── next() without hasNext() — throws NoSuchElementException ──────────
Iterator<Integer> small = List.of(1, 2).iterator();
System.out.println(small.next());  // 1
System.out.println(small.next());  // 2
// small.next();                   // NoSuchElementException — no more elements

// ── remove() — correct element removal during iteration ───────────────
List<String> list = new ArrayList<>(
    List.of("Alice", "Bob", "Carol", "Dave", "Eve"));
Iterator<String> remover = list.iterator();

while (remover.hasNext()) {
    String name = remover.next();
    if (name.startsWith("C") || name.startsWith("D")) {
        remover.remove();   // safely removes current element
    }
}
System.out.println(list);   // [Alice, Bob, Eve]

// ── IllegalStateException — remove() rules ────────────────────────────
Iterator<String> bad = list.iterator();
// bad.remove();   // IllegalStateException — must call next() first
bad.next();
bad.remove();   // OK — removes first element
// bad.remove(); // IllegalStateException — can't remove twice without next()
bad.next();
bad.remove();   // OK — removes second element

Fail-Fast Iterators and ConcurrentModificationException

Most standard collection iterators in java.util are fail-fast: they detect when the underlying collection has been structurally modified (elements added or removed) since the iterator was created, and throw ConcurrentModificationException. This detection is implemented via a modification count (modCount) maintained by the collection. When the iterator is created, it records the current modCount. Before each next() call, it checks whether the current modCount matches the recorded value. If they differ, a structural modification occurred and the iterator throws. The fail-fast behaviour is a debugging aid, not a contract. The JVM specification says: if a structural modification is detected, ConcurrentModificationException will generally be thrown, but there is no guarantee. The iterator can only detect modifications that happen to change the modCount before the check — certain race conditions may go undetected. Relying on ConcurrentModificationException as a concurrency safety mechanism is wrong; it is only useful for catching bugs during development. Common causes of ConcurrentModificationException: calling Collection.remove() directly on the collection during a for-each loop (instead of Iterator.remove()); adding elements to a collection being iterated; clearing a collection mid-iteration; passing a collection to a method that modifies it during a caller's iteration. The fix in all cases is to use Iterator.remove() for removal during iteration, or to collect changes and apply them after iteration completes. Iterators from java.util.concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedQueue) are weakly consistent and do not throw ConcurrentModificationException. They reflect the state at the time the iterator was created (or a consistent snapshot) and tolerate concurrent modifications.

Java

// ── ConcurrentModificationException — the bug ────────────────────────
List<String> list = new ArrayList<>(
    List.of("Alice", "Bob", "Carol", "Dave"));

// WRONG: removing via Collection.remove() during for-each:
for (String name : list) {
    if (name.equals("Bob")) {
        list.remove(name);   // ConcurrentModificationException!
    }
}

// WRONG: adding during iteration:
for (String name : list) {
    if (name.equals("Alice")) {
        list.add("Frank");   // ConcurrentModificationException!
    }
}

// ── Fixes for safe removal during iteration ───────────────────────────

// Fix 1: Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("Bob")) {
        it.remove();   // safe — iterator knows about the removal
    }
}
System.out.println(list);   // [Alice, Carol, Dave]

// Fix 2: List.removeIf() — cleaner, no explicit iterator
list.removeIf(name -> name.startsWith("C"));
System.out.println(list);   // [Alice, Dave]

// Fix 3: Collect, then remove after iteration
List<String> toRemove = new ArrayList<>();
for (String name : list) {
    if (name.length() > 4) toRemove.add(name);
}
list.removeAll(toRemove);

// Fix 4: Stream.filter() + collect — produces new list
List<String> filtered = list.stream()
    .filter(name -> !name.equals("Dave"))
    .collect(Collectors.toList());

// ── Fail-fast detection mechanism ────────────────────────────────────
// ArrayList maintains: int modCount (inherited from AbstractList)
// ArrayList.iterator() records: int expectedModCount = modCount
// Before each next(): if (modCount != expectedModCount) throw CME

// Trace:
ArrayList<String> al = new ArrayList<>(List.of("a", "b", "c"));
// al.modCount = 3 (3 structural mods: construction counts each add)
Iterator<String> tracker = al.iterator();
// tracker.expectedModCount = 3

al.add("d");   // al.modCount becomes 4
// tracker.expectedModCount is still 3

// tracker.next();  // checks: 4 != 3 → ConcurrentModificationException

// ── Weakly consistent: concurrent iterators ────────────────────────────
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("a", 1); map.put("b", 2); map.put("c", 3);

// ConcurrentHashMap's iterator is weakly consistent — never throws CME
Iterator<Map.Entry<String, Integer>> concIt = map.entrySet().iterator();
map.put("d", 4);   // safe — ConcurrentHashMap iterator tolerates this
while (concIt.hasNext()) {
    System.out.println(concIt.next());  // may or may not see "d"
}

Implementing Iterator — Custom Traversal

Implementing a custom Iterator is necessary when creating a custom data structure that should support the enhanced for-each loop or be passed to algorithms that consume iterators. The implementation requires maintaining traversal state — typically a current position — and correctly implementing all three methods including the optional remove(). A class enables for-each iteration by implementing Iterable<T>, which requires an iterator() method that returns a fresh Iterator<T>. Each call to iterator() must return a new, independent iterator starting from the beginning of the collection — two iterators on the same collection must not share traversal state. The custom iterator must handle edge cases: hasNext() must return false when exhausted; next() must throw NoSuchElementException (not return null) when called on an exhausted iterator; remove() must throw IllegalStateException if called before the first next() or called twice without an intervening next(); remove() must throw UnsupportedOperationException if removal is not supported. The most common implementation pattern for collections backed by an array uses an index field. For linked-structure collections (linked lists, trees), a current node reference serves as the cursor. For lazy sequences (ranges, generated sequences), the iterator computes the next value on demand.

Java

// ── Custom Iterable and Iterator ─────────────────────────────────────
public class NumberRange implements Iterable<Integer> {

    private final int start;
    private final int end;
    private final int step;

    public NumberRange(int start, int end, int step) {
        if (step <= 0) throw new IllegalArgumentException("Step must be positive");
        this.start = start;
        this.end   = end;
        this.step  = step;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new RangeIterator();
    }

    private class RangeIterator implements Iterator<Integer> {

        private int current = start;

        @Override
        public boolean hasNext() {
            return current < end;
        }

        @Override
        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException(
                "No more elements in range [" + start + ", " + end + ")");
            int value = current;
            current += step;
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException(
                "NumberRange does not support element removal");
        }
    }
}

// ── Usage — for-each works automatically ──────────────────────────────
NumberRange range = new NumberRange(0, 10, 2);
for (int n : range) System.out.print(n + " ");
// 0 2 4 6 8

// Can create multiple independent iterators:
Iterator<Integer> it1 = range.iterator();
Iterator<Integer> it2 = range.iterator();  // independent — starts from 0 again
it1.next();   // advances it1 to 2
it2.next();   // it2 still at 0 next

// ── Custom Iterator for a linked list ─────────────────────────────────
public class SimpleLinkedList<T> implements Iterable<T> {

    private static class Node<T> {
        T data; Node<T> next;
        Node(T data) { this.data = data; }
    }

    private Node<T> head;
    private int     size;

    public void addFirst(T data) {
        Node<T> node = new Node<>(data);
        node.next = head;
        head = node;
        size++;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedIterator();
    }

    private class LinkedIterator implements Iterator<T> {

        private Node<T>  current = head;
        private Node<T>  prev    = null;
        private boolean  canRemove = false;

        @Override
        public boolean hasNext() { return current != null; }

        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            prev      = current;
            current   = current.next;
            canRemove = true;
            return prev.data;
        }

        @Override
        public void remove() {
            if (!canRemove) throw new IllegalStateException(
                "Call next() before remove()");
            // Removal from linked list is simplified here
            // Full implementation would track the node before prev
            canRemove = false;
        }
    }
}

Iterator

The Iterator Contract — hasNext, next, remove

Fail-Fast Iterators and ConcurrentModificationException

Implementing Iterator — Custom Traversal

Related Topics in Collections Framework