Iterator Pattern

Overview

Collections are everywhere in software — lists, trees, graphs, queues, hash tables. Each has a different internal layout, but callers almost always want the same thing: visit every element, one at a time, without caring about how the collection is organized internally.

The Iterator pattern is a behavioral design pattern that decouples traversal logic from collection logic. It gives every collection a common interface for sequential access, so callers can iterate over a binary tree, a flat array, or a custom graph using identical code.

Without Iterator, every collection leaks its internal structure the moment you need to traverse it. With it, you can swap out an array for a tree behind the scenes and not change a single line of client code.

Problem & Motivation

Imagine you are building a file system browser. You have a Directory object that can contain both File objects and nested Directory objects — a classic n-ary tree. A client needs to print every file's path.

The naive approach exposes the internal structure directly: the client calls getChildren(), checks each child's type, recurses manually. Now suppose you later change Directory from an eager in-memory tree to a lazy-loaded structure that fetches entries from disk one level at a time. Every caller breaks.

The deeper problem is that traversal logic is tangled into two places: the client (which knows about children) and the collection (which owns the data). Iterator separates these concerns. The collection provides a dedicated traversal object — the iterator — which remembers the current position and knows how to move forward. The client asks for the next element and trusts the iterator to do the rest.

This matters most when:

• You have multiple collection types that should be traversed the same way.
• You want to support several traversal strategies on the same collection (depth-first vs. breadth-first).
• You want to run multiple independent traversals of the same collection concurrently.

Class Diagram

The diagram shows the key structural relationships:

• Iterator defines the traversal contract: hasNext() to check availability and next() to advance.
• Iterable defines the factory method that produces an iterator for the collection.
• TreeNode implements Iterable and manufactures a DepthFirstIterator by default.
• Both DepthFirstIterator and BreadthFirstIterator implement Iterator, so client code can use either interchangeably.

Implementation

The examples below model a general-purpose n-ary tree of strings and provide two iterators: depth-first (DFS) and breadth-first (BFS). The client code is identical regardless of which iterator is used.

// Iterator interface
interface Iterator<T> {
  hasNext(): boolean;
  next(): T;
}

// Iterable interface
interface Iterable<T> {
  createIterator(strategy?: "dfs" | "bfs"): Iterator<T>;
}

// Node in the tree
class TreeNode<T> implements Iterable<T> {
  value: T;
  children: TreeNode<T>[];

  constructor(value: T, children: TreeNode<T>[] = []) {
    this.value = value;
    this.children = children;
  }

  createIterator(strategy: "dfs" | "bfs" = "dfs"): Iterator<T> {
    return strategy === "bfs"
      ? new BreadthFirstIterator(this)
      : new DepthFirstIterator(this);
  }
}

// Depth-first iterator using an explicit stack
class DepthFirstIterator<T> implements Iterator<T> {
  private stack: TreeNode<T>[];

  constructor(root: TreeNode<T>) {
    this.stack = [root];
  }

  hasNext(): boolean {
    return this.stack.length > 0;
  }

  next(): T {
    const node = this.stack.pop()!;
    // Push children in reverse so left-most child is visited first
    for (let i = node.children.length - 1; i >= 0; i--) {
      this.stack.push(node.children[i]);
    }
    return node.value;
  }
}

// Breadth-first iterator using a queue
class BreadthFirstIterator<T> implements Iterator<T> {
  private queue: TreeNode<T>[];

  constructor(root: TreeNode<T>) {
    this.queue = [root];
  }

  hasNext(): boolean {
    return this.queue.length > 0;
  }

  next(): T {
    const node = this.queue.shift()!;
    this.queue.push(...node.children);
    return node.value;
  }
}

// Build the tree:
//        a
//       / \
//      b   c
//     / \
//    d   e
const tree = new TreeNode("a", [
  new TreeNode("b", [new TreeNode("d"), new TreeNode("e")]),
  new TreeNode("c"),
]);

// Client code — identical for both strategies
const print = (iter: Iterator<string>) => {
  const result: string[] = [];
  while (iter.hasNext()) result.push(iter.next());
  console.log(result.join(", "));
};

print(tree.createIterator("dfs")); // a, b, d, e, c
print(tree.createIterator("bfs")); // a, b, c, d, e

Real-World Examples

Java's java.util.Iterator — Every Java collection (ArrayList, LinkedList, TreeSet, HashMap.entrySet()) implements the Iterable<T> interface, which produces a java.util.Iterator<T>. This is why the enhanced for loop works uniformly across all collection types. You can also replace ArrayList with LinkedList and the loop does not change.

Python's iteration protocol — Any object that implements __iter__ and __next__ becomes iterable. Built-in functions like list(), sum(), and zip() accept any iterable, not just lists. This is how generators (yield) plug seamlessly into for loops and comprehensions without the caller knowing whether it is a list, a generator, or a database cursor streaming rows lazily.

React's flatMap and virtual DOM diffing — When React reconciles a component tree it performs a depth-first traversal of the fiber tree. The fiber architecture models this as an iterative loop with an explicit stack (to avoid call-stack overflow on deep trees) — effectively a hand-rolled iterator pattern applied to a tree of UI nodes.

Database cursor APIs — JDBC's ResultSet, MongoDB's cursor, and SQLAlchemy's Result object all implement Iterator. The client calls next() (or fetchone()) in a loop and never needs to know whether the results are buffered in memory, streamed from the network, or fetched page-by-page from a remote server.

Pros and Cons

When to Use / When to Avoid

Use Iterator when:

• Your collection has a non-trivial internal structure (tree, graph, ring buffer) that you do not want to expose to callers.
• You need to support multiple traversal strategies on the same data structure (DFS vs. BFS, pre-order vs. post-order).
• You want client code to work uniformly across different collection types.
• You are streaming large or infinite data and cannot load all elements into memory at once.
• You need concurrent, independent traversals of the same collection without synchronization.

Avoid Iterator when:

• You are iterating over a plain array or list and the language already provides a for-of / foreach construct. Wrapping it in a custom iterator adds indirection with no benefit.
• Random access is the primary operation. An iterator is a poor substitute for indexed access — reach for a list or array directly.
• Performance is critical in a tight inner loop and allocation of iterator objects is measured as a bottleneck. In that case, inline the traversal manually.
• The collection is so simple that a getAll(): T[] method communicates intent more clearly.

Related Patterns

Composite — Iterator and Composite are natural partners. Composite defines tree structures made of nodes; Iterator provides a uniform way to traverse them. The tree example in this page is a classic Composite structure traversed by a Composite-aware iterator.

Factory Method — createIterator() on the collection is a Factory Method. The collection decides which concrete iterator class to instantiate, shielding callers from that choice.

Visitor — both Iterator and Visitor separate an operation from the structure it operates on. Iterator lets you pull elements out one at a time and process them yourself. Visitor pushes the operation into the structure via double dispatch. Use Visitor when the operation needs to behave differently per node type; use Iterator when the client drives the processing.

Generator / Coroutine — modern languages express Iterator as first-class language constructs. Python's yield, JavaScript's function*, and C#'s yield return let you write iterator logic as ordinary sequential code that the runtime suspends and resumes. These are the idiomatic replacement for hand-rolled iterator classes in those languages.