What is Iterator pattern

The Iterator pattern is a Behavioral design pattern that provides a standardized mechanism to sequentially traverse elements of a composite collection without exposing its under...

🟢 Junior Level

The Iterator pattern is a Behavioral design pattern that provides a standardized mechanism to sequentially traverse elements of a composite collection without exposing its underlying internal data structure (such as an array, linked list, balanced binary tree, or hash table).

In Java, the pattern is deeply integrated into the language through two core interfaces:

Iterable<T>: Represents any data structure that can be iterated over. It declares Iterator<T> iterator(). Any class implementing Iterable can be traversed using the enhanced for-each loop.
Iterator<T>: The cursor object that performs the traversal. It declares boolean hasNext(), T next(), and default void remove().

Real-World Analogies

Music Playlist: When you press the “Next” button on a media player, it jumps to the next song without requiring you to know whether the track is stored on local SSD storage, streamed from a remote cloud cache, or retrieved from an in-memory queue. The player simply tracks the current pointer and checks if another track exists.
Subway Turnstile: Passengers pass through a turnstile one by one. The turnstile admits the current passenger and awaits the next, without needing to load or visualize the entire crowd at once.

Basic Implementation in Java

import java.util.List;
import java.util.Iterator;

public class IteratorExample {
    public static void main(String[] args) {
        List<String> frameworks = List.of("Spring", "Hibernate", "Quarkus");

        // 1. Explicit Iterator traversal
        Iterator<String> iterator = frameworks.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println("Framework: " + item);
        }

        // 2. Enhanced for-each loop (syntactic sugar over Iterator)
        for (String item : frameworks) {
            System.out.println("For-each: " + item);
        }
    }
}

🟡 Middle Level

`Iterator<E>` vs `ListIterator<E>`

The ListIterator<E> interface extends Iterator<E> and is available exclusively for collections implementing the List interface (indexed collections):

Capability	`Iterator<E>`	`ListIterator<E>`
Traversal Direction	Forward-only (`next()`)	Bidirectional (`next()` and `previous()`)
Boundary Checks	`hasNext()`	`hasNext()` and `hasPrevious()`
Index Tracking	Not supported	`nextIndex()`, `previousIndex()`
Element Modification	Removal only via `remove()`	Removal (`remove()`), replacement (`set(E)`), and insertion (`add(E)`)
Applicability	Any `Collection` (Set, Queue, List)	Strictly `List` implementations (`ArrayList`, `LinkedList`)

List<String> list = new ArrayList<>(List.of("A", "B", "C"));
ListIterator<String> listIterator = list.listIterator();

while (listIterator.hasNext()) {
    String val = listIterator.next();
    if ("B".equals(val)) {
        listIterator.set("B_MODIFIED"); // Replaces element "B"
        listIterator.add("INSERTED");    // Inserts new element between B and C
    }
}

How `for-each` Works Under the Hood

The Java compiler (javac) compiles enhanced for-each loops over Iterable objects directly into classic iterator while-loops:

// Developer's Source Code:
for (String item : list) {
    System.out.println(item);
}

// Bytecode equivalent:
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    String item = it.next();
    System.out.println(item);
}

This explains why invoking list.remove(item) or list.add(item) inside an enhanced for-each loop throws ConcurrentModificationException: the modification alters the collection’s internal state without informing the iterator’s cursor.

Safe Removal Options:

// Option 1: Classic iterator remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("REMOVE_ME")) {
        it.remove(); // Safely updates expectedModCount!
    }
}

// Option 2: Modern Java 8+ removeIf (O(N) bulk removal)
list.removeIf(item -> item.equals("REMOVE_ME"));

Custom `Iterable` & `Iterator` Implementation

Example of an In-Order traversal iterator over a Binary Search Tree (BST) using an explicit stack:

import java.util.*;

public class BinaryTree<T> implements Iterable<T> {
    private Node<T> root;

    private static class Node<T> {
        T value;
        Node<T> left;
        Node<T> right;
        Node(T val) { this.value = val; }
    }

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

    private class InOrderIterator implements Iterator<T> {
        private final Deque<Node<T>> stack = new ArrayDeque<>();

        public InOrderIterator(Node<T> root) {
            pushLeftBranch(root);
        }

        private void pushLeftBranch(Node<T> node) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            Node<T> current = stack.pop();
            pushLeftBranch(current.right);
            return current.value;
        }
    }
}

🔴 Senior Level

Fail-Fast Mechanics: `modCount` vs `expectedModCount`

Standard collections (ArrayList, HashMap, LinkedList, HashSet) use a Fail-Fast design:

The collection maintains an internal counter: protected transient int modCount = 0;.
Every structural mutation (add, remove, clear, grow) increments modCount++.
When an Iterator is created, it captures the current counter: int expectedModCount = modCount;.

On every call to next() or remove(), the iterator checks:

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

[!WARNING] Senior Interview Distinction: Fail-Fast behavior is not guaranteed in multithreaded environments without synchronization. The modCount field is not declared volatile. CPU caches or register caching can prevent one thread from seeing updates made by another thread immediately. Fail-Fast is designed solely to catch single-threaded concurrent modification programming bugs.

Fail-Fast vs Fail-Safe vs Weakly Consistent

Category	Implementations	Behavior on Modification	Reflects Concurrent Writes?	`iterator.remove()` Support
Fail-Fast	`ArrayList`, `HashMap`, `LinkedList`	Throws `ConcurrentModificationException` immediately	No (traversal aborts)	Supported (synchronizes `expectedModCount`)
Fail-Safe (Snapshot)	`CopyOnWriteArrayList`, `CopyOnWriteArraySet`	Never throws exception; traverses an immutable snapshot array	Never (isolated from writes made after creation)	Throws `UnsupportedOperationException`
Weakly Consistent	`ConcurrentHashMap`, `ConcurrentLinkedQueue`	Never throws exception; traverses live node links	May reflect some concurrent modifications	Supported

Evolution to `Spliterator<T>` in Java 8+

To support parallel data pipelines in the Stream API, standard single-threaded iterators were supplemented by Spliterator<T> (Splitable Iterator):

public interface Spliterator<T> {
    boolean tryAdvance(Consumer<? super T> action); // Step-by-step traversal (hasNext + next)
    Spliterator<T> trySplit();                       // Partitions data range in half for parallel threads
    long estimateSize();                             // Estimated elements remaining
    int characteristics();                           // Bitmask describing data source properties
}

trySplit(): Enables ForkJoinPool.commonPool() to recursively split data partitions across available CPU cores.
characteristics(): Bitmask flags (ORDERED, DISTINCT, SORTED, SIZED, NONNULL, IMMUTABLE, CONCURRENT) that allow the Stream API compiler to eliminate unnecessary pipeline operations. For example, if DISTINCT is set, .distinct() operations are discarded as no-ops.

Primitive Specializations: Avoiding GC Allocation Churn

Iterating over numerical streams using Iterator<Integer> incurs severe autoboxing overhead (int $\to$ Integer), allocating millions of transient heap objects in Eden space and triggering Garbage Collection pauses.

Java provides specialized primitive iterators to eliminate boxing:

PrimitiveIterator.OfInt
PrimitiveIterator.OfLong
PrimitiveIterator.OfDouble

int[] numbers = {1, 2, 3, 4, 5};
PrimitiveIterator.OfInt it = Arrays.stream(numbers).iterator();
while (it.hasNext()) {
    int val = it.nextInt(); // 0 heap allocations, zero autoboxing overhead!
}

4 Tricky Questions

1. Why does modifying a collection inside an enhanced `for-each` loop throw `ConcurrentModificationException`, and how does `Collection.removeIf()` optimize this?

Answer: The enhanced for-each loop compiles into an Iterator traversal. When you call collection.remove(item) directly on the collection, the collection increments its internal modCount, but the iterator’s expectedModCount is not updated. On the next loop iteration, it.next() checks modCount == expectedModCount, detects the mismatch, and throws a ConcurrentModificationException. In contrast, Collection.removeIf(predicate) delegates bulk removal directly to the collection implementation. In ArrayList, removeIf performs a single-pass in-place compaction ($O(N)$) using a bitset of matching elements, avoiding repeated $O(N)$ array-copy shifts that occur when calling iterator.remove() repeatedly in a loop.

2. Why is the Fail-Fast behavior of Java collections described as “best-effort” rather than guaranteed in concurrent environments?

Answer: The internal modCount variable that tracks structural modifications is declared as a plain transient int, without the volatile modifier. In multi-threaded execution without external synchronization, memory barrier guarantees do not apply. One CPU core may update modCount in its L1/L2 cache while another core running an iterator loop reads a stale value of modCount from registers or local cache. As a result, the check modCount != expectedModCount can evaluate to false even though concurrent modifications occurred, leading to data corruption or infinite loops instead of a ConcurrentModificationException.

3. How does `Spliterator` enable parallel stream processing, and what role does `characteristics()` play?

Answer: Spliterator introduces trySplit(), which splits the source collection into two balanced, non-overlapping partitions. One partition is processed by the current thread while the second is dispatched to a worker thread in the ForkJoinPool. This splitting continues recursively until partition sizes reach optimal granularity. The characteristics() method returns an integer bitmask (e.g., SORTED, SIZED, DISTINCT, CONCURRENT). The Java Stream API engine uses these flags to perform execution pipeline optimizations—such as skipping .sorted() or .distinct() stages if the underlying source already declares those characteristics.

4. Why does calling `remove()` on an iterator from `CopyOnWriteArrayList` throw `UnsupportedOperationException`?

Answer: CopyOnWriteArrayList uses a snapshot-based Fail-Safe iterator. When iterator() is called, it captures a direct reference to the underlying array (final Object[] array) at that exact point in time. Because all mutations on a CopyOnWriteArrayList create a brand new copy of the array rather than modifying the existing array in place, allowing the iterator to mutate its captured snapshot array would either be meaningless (mutations would not reflect in the collection) or require complex synchronization. To enforce immutability, the iterator’s remove(), set(), and add() methods throw UnsupportedOperationException.

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“The Iterator pattern provides a uniform, sequential traversal mechanism across collections without exposing their internal storage representation. In Java, it is implemented via Iterable and Iterator, forming the foundation of the enhanced for-each loop. Java collections feature three iterator models: Fail-Fast (detects concurrent modifications via modCount), Fail-Safe (iterates over an immutable array snapshot in CopyOnWriteArrayList), and Weakly Consistent (in ConcurrentHashMap). In modern Java, Spliterator powers parallel Stream processing via trySplit(), while primitive specializations like PrimitiveIterator.OfInt eliminate autoboxing allocation overhead.”

Key Architectural Takeaways

Iterable vs Iterator: Iterable creates an iterator (iterator()); Iterator executes the traversal (next(), hasNext()).
for-each Under the Hood: Compiles into an Iterator loop; direct collection mutations trigger ConcurrentModificationException.
Safe Traversal Removal: Use iterator.remove() or collection.removeIf().
Fail-Fast Mechanics: Driven by modCount != expectedModCount; best-effort in concurrent code because modCount is not volatile.
Parallel Traversal: Spliterator.trySplit() enables multi-core partitioning in the Stream API.

Red Flags & Anti-Patterns

🚩 Calling collection.remove() inside an enhanced for-each loop: Triggers guaranteed ConcurrentModificationException.
🚩 Assuming ConcurrentModificationException only occurs in multithreaded code: It most frequently occurs in single-threaded code due to improper collection modification during iteration.
🚩 Using boxed Iterator<Integer> in high-throughput hot paths: Use PrimitiveIterator.OfInt to prevent Eden space GC churn.
🚩 Assuming CopyOnWriteArrayList iterator supports remove(): It is an immutable snapshot and throws UnsupportedOperationException.

How is Observer implemented in Java — Listener traversal patterns
What Proxy types exist — Dynamic proxies in collections
What pattern categories exist — Behavioral pattern taxonomy
What anti-patterns do you know — Concurrency and architectural pitfalls