Iterator Pattern | Design Patterns

01

Section One · The Problem

Why Iterator Exists

You have a collection of items — maybe a playlist of songs. But the collection could be stored as an array, a linked list, a tree, a graph, or even a database cursor. Client code that wants to loop through the items must know the internal structure: use index for arrays, follow node.next for linked lists, do DFS/BFS for trees. The naive approach: the client is coupled to the underlying data structure.

Naive approach — client coupled to internal structure

 // ✗ Client must know HOW the collection is stored // Array-based playlist — use index for (int i = 0; i < playlist.songs.length; i++) {
    play(playlist.songs[i]);
}
// Linked list playlist — follow .next pointers Node node = playlist.head;
while (node != null) {
    play(node.song);
    node = node.next;
}
// Tree-based playlist (by genre) — recursive DFS void traverse(TreeNode n) {
if (n == null) return;
    play(n.song);
traverse(n.left);
traverse(n.right);
}
// Change the data structure? Rewrite ALL client traversal code. 

What goes wrong:

Tight coupling to internals — the client must know if the collection uses an array, linked list, or tree; if the implementation changes, all clients break
Encapsulation violation — the client accesses playlist.songs (the internal array) or playlist.head (the internal node) directly
No uniform traversal — each data structure requires different traversal code (index, pointer chasing, recursion); you can’t write one generic loop
Multiple traversals impossible — if two threads want to iterate the same collection at different positions, there’s no way to track independent cursors
Can’t swap traversal strategy — want to iterate a tree in BFS instead of DFS? Rewrite the client. Want reverse order? Rewrite again.

Without Iterator — client knows internal structure

This is the problem Iterator solves — extract the traversal logic into a separate iterator object with a uniform interface (hasNext() + next()). The client iterates any collection structure identically without knowing its internals.

02

Section Two · The Pattern

What Is Iterator?

Iterator is a behavioral pattern that provides a way to access elements of a collection sequentially without exposing the collection’s underlying representation. The collection (aggregate) creates an iterator object that knows how to traverse its elements. The client uses only the iterator’s uniform interface — hasNext() and next() — regardless of whether the collection is an array, tree, graph, or database result set.

 GoF Intent: “Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.”
 — Gamma, Helm, Johnson, Vlissides (1994) 

Analogy — a TV remote’s channel buttons: A TV has hundreds of channels stored in different ways internally — some from cable, some from satellite, some from streaming apps, each with different data formats. But you don’t care. You press Next Channel (like next()) and the TV shows the next channel regardless of where it comes from. The remote is the iterator — it gives you a uniform way to traverse channels without knowing how they’re stored. You can have multiple remotes (multiple iterators on the same collection), each at a different channel position. The TV’s internal channel storage can change completely without affecting how you press Next.

Key insight: Iterator separates what you traverse (the collection) from how you traverse (the cursor logic). The collection is responsible for creating an appropriate iterator (factory method). The iterator is responsible for tracking position and delivering elements. This is so fundamental that Java baked it into the language: for (Song s : playlist) compiles to Iterator<Song> it = playlist.iterator(); while (it.hasNext()) { Song s = it.next(); }.

The collection implements Iterable and provides a factory method iterator()

▶

The client gets an iterator without knowing the collection’s internal structure. Different structures can provide different iterators.

The iterator has a uniform interface: hasNext() and next()

▶

Client code that uses this interface works with ANY collection: arrays, trees, graphs, databases, infinite sequences. One loop for all.

Each iterator instance maintains its own traversal state (cursor position)

▶

Multiple independent traversals on the same collection simultaneously. No conflict between iterators.

The same collection can create different iterators (DFS, BFS, reverse, filtered)

▶

Traversal strategy is swappable without changing the collection or the client. tree.dfsIterator() vs. tree.bfsIterator().

03

Section Three · Anatomy

Participants & Structure

Participant	Role	In the Analogy
Iterator (interface)	Declares the traversal interface: `hasNext()` (is there a next element?) and `next()` (return it and advance). May also declare `remove()`.	The “Next/Previous” button contract — any remote must have these buttons.
Concrete Iterator	Implements the traversal interface for a specific collection. Maintains the current position (cursor). Knows the collection’s internal structure.	The specific remote that knows the cable box’s channel list internally.
Aggregate / Iterable (interface)	Declares a factory method `iterator()` that returns an Iterator. This is the “collection” contract.	The TV contract — every TV must be able to provide a remote.
Concrete Aggregate	Implements the aggregate interface. Returns a concrete iterator that knows how to traverse its specific internal structure.	Your specific TV — it creates a remote configured for its channel storage.
Client	Uses only the Iterator interface (`hasNext()` + `next()`). Never accesses the collection’s internals directly.	You — pressing Next without knowing how channels are stored.

Iterator — UML Class Diagram

Java baked this pattern into the language:

java.lang.Iterable<T> is the Aggregate interface; java.util.Iterator<T> is the Iterator interface.
The for-each loop (for (Song s : playlist)) is syntactic sugar that calls iterator(), hasNext(), and next() automatically.
Every collection in java.util implements Iterable.
You’ve been using Iterator since your first Java loop.

04

Section Four · How It Works

The Pattern In Motion

Scenario: A Playlist stores songs in an array. The client asks for an iterator and loops through songs without knowing the internal storage.

Step 1 — Client calls playlist.iterator()

▶

The playlist creates a new PlaylistIterator with index = 0 and a reference to the internal array. The client receives it as Iterator<Song>.

Step 2 — Client calls it.hasNext()

▶

Iterator checks index < songs.length. Returns true. The client doesn’t know the collection is an array — it just asks “is there more?”

Step 3 — Client calls it.next()

▶

Iterator returns songs[index] and increments index++. The cursor advances. The client gets the element without knowing it came from position 0 of an array.

Step 4 — Repeat until hasNext() returns false

▶

When index == songs.length, hasNext() returns false. The loop ends. The same client code would work if the playlist switched to a linked list — only the iterator changes.

Iterator — Cursor Advancing Through Elements

The pattern in pseudocode

 // ── Same client code for ANY collection type ── Playlist playlist = new Playlist("Road Trip");
playlist.add(new Song("Bohemian Rhapsody"));
playlist.add(new Song("Hotel California"));
playlist.add(new Song("Stairway to Heaven"));
// Using the iterator explicitly Iterator<Song> it = playlist.iterator();
while (it.hasNext()) {
Song s = it.next();
    System.out.println(s.title());
}
// Using for-each (compiles to the SAME iterator code) for (Song s : playlist) {
    System.out.println(s.title());
}
// Output: Bohemian Rhapsody, Hotel California, Stairway to Heaven 

Multiple iterators on the same collection:

If Alice iterates songs 1-3 while Bob iterates songs 2-5, each has their own PlaylistIterator instance with an independent index cursor.
They don’t interfere.
This is impossible with a single embedded cursor in the collection itself — which is exactly why Iterator is a separate object.

05

Section Five · Java Stdlib

You Already Use This

Iterator is the most used design pattern in Java — you use it every time you write a for-each loop. The entire Collections Framework is built on it.

IN JAVA

Example 1 java.util.Iterator<E> — the core Iterator interface with hasNext(), next(), and remove(). Every collection’s iterator() method returns this. The for-each loop compiles to calls on this interface.

Example 2 java.lang.Iterable<T> — the Aggregate interface. Any class implementing Iterable can be used in for-each loops. Collection, List, Set, Queue all extend it. Implementing Iterable enables your custom class in for-each.

Example 3 java.util.ListIterator<E> — an extended Iterator that supports bidirectional traversal (hasPrevious(), previous()), modification (set(), add()), and index access (nextIndex()). Available on List implementations.

Example 4 java.util.Spliterator<T> — the parallel-capable Iterator introduced in Java 8. Supports splitting the collection for parallel Stream processing. trySplit() divides work; tryAdvance() processes one element. This powers stream().parallel().

Stdlib usage — for-each desugars to Iterator

 // What you write: List<String> names = List.of("Alice", "Bob", "Charlie");
for (String name : names) {
    System.out.println(name);
}
// What the compiler generates: Iterator<String> $it = names.iterator();
while ($it.hasNext()) {
String name = $it.next();
    System.out.println(name);
}

Stdlib usage — custom Iterable in for-each

 // Implement Iterable → your class works in for-each loops class NumberRange implements Iterable<Integer> {
private final int start, end;
public NumberRange(int start, int end) { this.start = start; this.end = end; }

    @Override
public Iterator<Integer> iterator() {
return new Iterator<>() {
int current = start;
public boolean hasNext() { return current <= end; }
public Integer next() { return current++; }
        };
    }
}
// Now works in for-each! for (int n : new NumberRange(1, 5)) {
    System.out.print(n + " "); // 1 2 3 4 5
}

Streams are lazy iterators:

Java 8 Stream<T> is a modern evolution of Iterator.
It adds lazy evaluation, chaining (filter, map, reduce), and parallelism.
Under the hood, streams use Spliterator (a splitting iterator).
The conceptual pattern is the same: traverse elements without exposing the data structure.

06

Section Six · Implementation

Build It Once

Domain: Playlist with multiple traversal strategies. A Playlist implements Iterable<Song> and provides both forward and reverse iterators. The client uses the standard for-each loop or can request a reverse iterator.

Java — Iterator Pattern Playlist (core)

 // ── Song record ── record Song(String title, String artist, int durationSec) {}
// ── Iterable aggregate: Playlist ── class Playlist implements Iterable<Song> {
private final List<Song> songs = new ArrayList<>();
public void add(Song s) { songs.add(s); }

    @Override
public Iterator<Song> iterator() { // forward return new ForwardIterator();
    }
public Iterator<Song> reverseIterator() { // reverse return new ReverseIterator();
    }
// Inner class iterators have access to songs list
}

Inner class iterators:

In Java, iterators are typically implemented as inner classes of the collection.
This gives them direct access to the collection’s private fields (like songs) without exposing those fields publicly.
The iterator is tightly coupled to its collection by design — but the client is decoupled from both via the Iterator interface.

07

Section Seven · Watch Out

Common Mistakes

Mistake #1 — Modifying the collection while iterating (ConcurrentModificationException): If you add or remove elements from a collection while iterating it with a for-each loop or an iterator, Java throws ConcurrentModificationException. This is a fail-fast mechanism to prevent corrupt iteration. Fix: Use Iterator.remove() to safely remove during iteration. Or collect indices/items to remove first, then modify after the loop. For concurrent access, use CopyOnWriteArrayList or ConcurrentHashMap.

✗ Wrong — modify during for-each

 // ✗ Throws ConcurrentModificationException List<String> names = new ArrayList<>(List.of("A", "B", "C"));
for (String name : names) {
if (name.equals("B")) {
        names.remove(name); // ← BOOM! ConcurrentModificationException
}
}

✔ Correct — use Iterator.remove()

 // ✓ Safe removal using the iterator Iterator<String> it = names.iterator();
while (it.hasNext()) {
if (it.next().equals("B")) {
        it.remove(); // ← safe — iterator handles bookkeeping
}
}

Mistake #2 — Calling next() without checking hasNext():

If you call next() when there are no more elements, it throws NoSuchElementException.
Fix: Always check hasNext() before next(). The for-each loop handles this automatically; the mistake only happens with explicit iterator usage.

Mistake #3 — Exposing the internal collection via getSongs():

If you return the internal list from the aggregate (return songs;), clients bypass the iterator entirely and access the collection directly.
This defeats encapsulation.
Fix: Return Collections.unmodifiableList(songs) or better, provide only the iterator() method. The client should have no way to access elements except through the iterator.

Mistake #4 — Storing the iterator for later reuse:

An exhausted iterator (where hasNext() returns false) cannot be “reset.” There’s no reset() method in Java’s Iterator.
Fix: Create a new iterator via collection.iterator() each time you want to re-traverse. Iterators are cheap, disposable objects.

Mistake #5 — Implementing Iterable on a class that isn’t a collection:

If your class isn’t logically a collection of elements, implementing Iterable is confusing.
A DatabaseConnection isn’t iterable; a ResultSet is.
Fix: Only implement Iterable on classes where “loop through this” makes semantic sense.

08

Section Eight · Decision Guide

When To Use Iterator

Use Iterator When

You need to traverse a collection without exposing its internal structure — the client shouldn’t know if it’s an array, tree, or hash table
You want to support multiple simultaneous traversals on the same collection — each iterator has its own independent cursor
You want to provide multiple traversal strategies (forward, reverse, filtered, DFS, BFS) without changing the collection or client
You are building a custom collection that should work with for-each loops — implement Iterable
You need lazy/on-demand elements — generate elements in next() without precomputing the entire sequence (infinite iterators, database cursors)

Avoid Iterator When

You need random access by index — iterators are sequential; use List.get(i) directly
The collection is so simple that a plain array or list suffices — don’t wrap a list in a custom iterator if List.iterator() already works
You need Stream operations (filter, map, reduce, parallel) — use stream() instead of writing a custom iterator
Performance is critical and the iterator overhead (object creation, method calls) matters — raw indexed loops are faster for tight inner loops

Iterator vs. Related Patterns

Pattern	What It Does	When to pick it
Iterator ← this	Provides sequential access to elements without exposing internals	Traverse any collection uniformly; custom data structures; lazy generation
Visitor	Performs operations on elements of a complex structure	Need to add operations to a structure without modifying element classes
Composite	Treats tree structures uniformly (part-whole hierarchy)	Recursive tree traversal where nodes and leaves share an interface
Stream (Java 8+)	Lazy, chainable, potentially parallel traversal with transformations	Need filter/map/reduce, parallel processing; modern Java idiomatic code

Decision Flowchart

09

Section Nine · Practice

Problems To Solve

Iterator problems test whether you can build custom iterators for non-trivial data structures, support multiple traversal strategies, and handle edge cases like empty collections and concurrent modification.

Difficulty	Problem	Key Insight
Easy	Range Iterator Build a `Range` class that implements `Iterable<Integer>`. Constructor takes `start`, `end`, and optional `step`. It should work in a for-each loop: `for (int n : new Range(0, 10, 2))` → 0, 2, 4, 6, 8, 10. Support negative step for descending ranges. Don’t store all values — generate lazily in `next()`.	Tests the lazy generation insight: the iterator computes the next value on demand without storing the full range. Key: `hasNext()` checks `current <= end` (or `>= end` for negative step). The collection stores nothing — it’s just a factory for iterators.
Medium	Flatten Iterator (Nested Lists) Build an iterator that flattens a `List<List<Integer>>` into a single sequential stream. `[[1,2],[3],[],[4,5]]` → `1, 2, 3, 4, 5`. Handle empty inner lists. The iterator must work with the standard `Iterator<Integer>` interface: `hasNext()` and `next()`.	Tests maintaining a two-level cursor: `outerIndex` (which sublist) and `innerIndex` (position within sublist). The tricky part: `hasNext()` must skip empty sublists by advancing `outerIndex` until it finds a non-empty sublist or exhausts the list. This is a common interview question.
Medium	Binary Tree Iterator (In-Order) Build an in-order iterator for a binary search tree. The BST stores integers. The iterator must produce elements in ascending order: left → node → right. Use `hasNext()` and `next()`. Constraint: do NOT precompute all elements into a list — use a stack to achieve O(h) space where h is the tree height.	Tests iterating a non-linear structure with O(h) space. The key: push all left children onto a stack initially. On `next()`: pop the top, return its value, then push all left children of its right subtree. `hasNext()` is just `!stack.isEmpty()`. This is LeetCode #173 (BST Iterator).
Hard	Peeking + Filtering + Merging Iterator Build three iterator decorators: (1) `PeekableIterator<T>` — adds `peek()` (look at next without consuming). (2) `FilterIterator<T>` — wraps an iterator and skips elements that don’t match a `Predicate`. (3) `MergeIterator<T extends Comparable>` — takes N sorted iterators and produces a single sorted stream (like merge in merge-sort). Chain them: merge 3 sorted lists, then filter to even numbers, then peek.	Tests the Decorator pattern applied to iterators. `PeekableIterator` buffers one element. `FilterIterator` must advance the underlying iterator in `hasNext()` until a match is found (or exhaustion). `MergeIterator` uses a min-heap of (value, iterator) pairs — `next()` pops the smallest, advances that iterator, re-inserts if it has more. These are the building blocks of database query engines and stream processing.

Interview Tip:

When asked about Iterator, the interviewer wants to see: (1) Iterable (aggregate creates iterators) and Iterator (uniform hasNext()/next() interface); (2) for-each compiles to iterator calls; (3) each iterator has independent state (multiple traversals simultaneously); (4) ConcurrentModificationException and how to avoid it.
Stand-out answers mention: lazy generation (infinite iterators), O(h) tree iterators using a stack, how Spliterator enables parallel streams, and that Iterator is so successful it was baked into the language syntax.