Iterator

Real-world analogy

A museum handheld audio guide acts as an iterator. As you explore the Louvre, you do not need to study the building's architectural blueprints, HVAC duct routes, or fire escape maps. You press the "Next" button on the handset. The guide advances to the next painting in the exhibit's curated tour. Different tour guides (a "Quick Highlights" guide versus a "Renaissance Masters" guide) traverse the exact same physical museum along completely different pathways without moving any walls.

The problem

You are building a social network graph where users have friends, followers, and organizational group memberships. Internally, the data structure is represented as a complex adjacency list and binary search tree (UserNode with left, right, and friendsList).

If client code (such as the recommendation engine, feed generator, and export tool) traverses this graph by directly accessing internal node pointers, several critical problems emerge:

1. Breaks Encapsulation: Private graph pointers and memory structures are exposed to client code.
2. Brittle Code: If you refactor the internal data structure from a binary tree to a B-Tree or hash table, all client traversal loops across the codebase break.
3. No Support for Multiple Traversals: If the client wants to perform a Breadth-First Search (BFS) or Depth-First Search (DFS), that complex traversal algorithm is repeated across every client service:

1 // Naive implementation: Client directly coupled to internal node pointers
2 class UserProfileNode {
3   constructor(name) {
4     this.name = name;
5     this.left = null;  // Internal tree pointers leaked to clients!
6     this.right = null;
7   }
8 }
9 
10 // Client must manually traverse internal pointers
11 function printAllUsers(root) {
12   const stack = [root];
13   while (stack.length > 0) {
14     const node = stack.pop();
15     if (node) {
16       console.log(node.name);
17       stack.push(node.right);
18       stack.push(node.left);
19     }
20   }
21 }

1 public class Example {
2     static class UserNode {
3         String name;
4         UserNode left, right; // Leaked internal structure
5         public UserNode(String name) { this.name = name; }
6     }
7 
8     public static void printUsers(UserNode root) {
9         // Client is tightly coupled to binary tree pointers

Client code should not care whether users are stored in a binary search tree, an array, a hash map, or a remote paginated API.

The solution

The Iterator pattern extracts the traversal behavior into a separate Iterator object. The iterator encapsulates the cursor state (e.g. current index or traversal stack) and provides standard methods (hasNext() and next()). The collection becomes an Iterable, exposing a factory method (createIterator()) that returns an iterator.

• Iterator (Iterator): Interface declaring operations to access and step through elements (hasNext(), next()).
• Concrete Iterator (InOrderIterator, BreadthFirstIterator): Tracks current position and implements traversal logic.
• Aggregate (IterableCollection): Interface declaring the factory method (createIterator()).
• Concrete Aggregate (UserTree): Holds the actual data and instantiates the iterator.

Step-by-step implementation

Step 1: Define the iterator interface

Establish standard cursor navigation methods.

1 class Iterator {
2   hasNext() {
3     throw new Error("hasNext() must be implemented");
4   }
5   next() {
6     throw new Error("next() must be implemented");
7   }
8 }

1 public class Example {
2     interface CustomIterator<T> {

Step 2: Implement the collection and concrete iterator

The iterator maintains an internal stack or index, keeping cursor state out of the collection.

Step 3: Iterate uniformly in client code

Clients traverse the aggregate without referencing its internal array or tree pointers.

1 const list = new SimpleList();
2 list.add("Alice");
3 list.add("Bob");
4 
5 const iter = list.getIterator();
6 while (iter.hasNext()) {
7   console.log(`Visited: ${iter.next()}`);
8 }

The complete example

Here is the complete runnable example demonstrating an in-order tree iterator and JavaScript generator integration.

1 --- Classical GoF Iterator Traversal ---
2 Visited: 20
3 Visited: 30
4 Visited: 40
5 Visited: 50
6 Visited: 60
7 Visited: 70
8 Visited: 80
9 
10 --- Native ES2022 for...of Loop ---
11 for...of item: 20
12 for...of item: 30
13 for...of item: 40
14 for...of item: 50
15 for...of item: 60
16 

Variations

External vs internal iteration

1. External Iterator (Active): The client code actively controls iteration pacing using hasNext() and next(). The client can pause, skip elements, break early, or interleave iteration across two collections simultaneously.
2. Internal Iterator (Passive): The collection controls iteration internally, passing each item to a callback function (e.g. list.forEach(item => ...) or Java Streams). Pacing is managed by the collection, and breaking out of loops early is harder.

Fail-fast iterators and ConcurrentModificationException

In multi-threaded or mutable collections, modifying a collection while an iterator is actively traversing it produces non-deterministic errors.

• Java collections maintain a private counter: modCount.
• When an iterator is created, it captures expectedModCount = modCount.
• On every call to next(), it checks if (modCount != expectedModCount) throw new ConcurrentModificationException().
• To safely remove items during iteration, use the iterator's own iterator.remove() method, which updates both counters simultaneously.

Where you've already used it

• Java Enhanced for-loop: Any class implementing java.lang.Iterable can be consumed via for (T item : collection).
• JavaScript Symbol.iterator: Standardizes iteration across Arrays, Maps, Sets, and generator functions with for (const x of iterable).
• Java Database Connectivity (JDBC) ResultSet: Implements cursor iteration via resultSet.next().
• Database Cursor Pagination: Paginating through millions of records in MongoDB, PostgreSQL, or DynamoDB using continuation tokens.

Pros and cons

When not to use it

Do not build custom Iterator classes for simple linear arrays or lists where native indexed loops or language-provided iterators already exist. Reserve custom iterators for trees, graphs, circular buffers, or paginated network streams.

Related patterns

Interview questions

What is the difference between fail-fast and fail-safe iterators? Fail-fast iterators (like in ArrayList) throw ConcurrentModificationException immediately if the underlying collection is modified during iteration. Fail-safe iterators (like in CopyOnWriteArrayList or ConcurrentHashMap) operate on a clone or snapshot of the collection, allowing modifications without exceptions.

Why is it unsafe to modify a collection using list.remove() during an enhanced for-loop? Enhanced for-loops compile into an Iterator. Calling list.remove() modifies modCount on the list without updating the iterator's expectedModCount, causing the next iteration step to throw ConcurrentModificationException. Use iterator.remove() instead.

How does an external iterator enable interleaving multiple collections? Because the client holds two iterator instances (iterA and iterB), the client can call iterA.next() and iterB.next() alternately to merge-sort two sorted streams. Internal iterators (like forEach) cannot be interleaved in this way.

How do JavaScript Generators (function*) relate to the Iterator pattern? A generator function automatically produces an object that implements the Iterator protocol (next() returning { value, done }), pausing execution at each yield and resuming on the subsequent next() call.