Iterator Pattern for Custom Collections

Overview

The Iterator pattern provides a way to access elements of an aggregate object sequentially without exposing its underlying representation. It separates the traversal algorithm from the collection structure, so you can iterate over arrays, trees, graphs, or streams through the same interface.

This resource focuses on the part the generic pattern leaves open: custom collections. A tree that needs both depth-first and breadth-first traversal, a linked list that should work with for...of, and a paginated query that yields rows lazily are all the same problem — decouple “how do I walk this” from “what is this”.

When to Use This

• You need to traverse a collection without exposing its internal structure
• Multiple traversal algorithms (pre-order, post-order, level-order) are needed for the same collection
• You want uniform iteration across different collection types — or native for...of support
• Elements arrive lazily: paginated APIs, database cursors, file streams

Skip it when the collection is a plain array — [Symbol.iterator] is already there. The pattern pays off when traversal logic is non-trivial or needs to vary.

Problem

A tree structure requires different traversal orders for different use cases — a file-system dump wants depth-first, a “nearest node first” search wants breadth-first. Hard-coding each traversal inside the tree couples the algorithm to the node implementation; externalizing it means exposing the internals the client shouldn’t see.

Solution

Two traversals, one interface, zero knowledge of the tree’s internals on the client side:

// iterator/Iterator.ts
interface Iterator<T> {
  next(): T | null;
  hasNext(): boolean;
  reset(): void;
}

interface IterableCollection<T> {
  createIterator(): Iterator<T>;
}

// Tree Node
class TreeNode<T> {
  children: TreeNode<T>[] = [];

  constructor(public value: T) {}

  addChild(child: TreeNode<T>): void {
    this.children.push(child);
  }
}

// Depth-First Iterator (pre-order)
class PreOrderIterator<T> implements Iterator<T> {
  private stack: TreeNode<T>[] = [];

  constructor(root: TreeNode<T>) {
    this.stack.push(root);
  }

  next(): T | null {
    if (!this.hasNext()) return null;

    const node = this.stack.pop()!;
    // Push children in reverse order for left-to-right traversal
    for (let i = node.children.length - 1; i >= 0; i--) {
      this.stack.push(node.children[i]);
    }

    return node.value;
  }

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

  reset(): void {
    this.stack = [];
  }
}

// Breadth-First Iterator — index-based queue, O(1) per next()
class LevelOrderIterator<T> implements Iterator<T> {
  private queue: TreeNode<T>[] = [];
  private head = 0;

  constructor(root: TreeNode<T>) {
    this.queue.push(root);
  }

  next(): T | null {
    if (!this.hasNext()) return null;

    const node = this.queue[this.head++];
    this.queue.push(...node.children);

    return node.value;
  }

  hasNext(): boolean {
    return this.head < this.queue.length;
  }

  reset(): void {
    this.queue = [];
    this.head = 0;
  }
}

// A real tree: nodes are addressed by a path map, not a stub
class FileSystem implements IterableCollection<string> {
  private root = new TreeNode<string>('root');
  private nodes = new Map<string, TreeNode<string>>();

  constructor() {
    this.nodes.set('root', this.root);
  }

  addNode(parentPath: string, name: string): void {
    const parent = this.nodes.get(parentPath);
    if (!parent) throw new Error(`Unknown path: ${parentPath}`);
    const child = new TreeNode<string>(name);
    parent.addChild(child);
    this.nodes.set(name, child);
  }

  createIterator(type: 'pre-order' | 'level-order' = 'pre-order'): Iterator<string> {
    if (type === 'level-order') {
      return new LevelOrderIterator(this.root);
    }
    return new PreOrderIterator(this.root);
  }
}

// Usage
const fs = new FileSystem();
fs.addNode('root', 'src');
fs.addNode('root', 'dist');
fs.addNode('src', 'index.ts');

const preOrder = fs.createIterator('pre-order');
console.log('Pre-order:');
while (preOrder.hasNext()) {
  console.log(preOrder.next());  // root, src, index.ts, dist
}

const levelOrder = fs.createIterator('level-order');
console.log('Level-order:');
while (levelOrder.hasNext()) {
  console.log(levelOrder.next());  // root, src, dist, index.ts
}

Two fixes worth noticing versus naive implementations. The level-order iterator uses a head index instead of queue.shift() — shift() reindexes the whole array on every call, turning a traversal into O(n²). And FileSystem keeps a real Map of paths to nodes, so addNode('src', 'index.ts') actually nests under src instead of silently attaching to root.

Variation: Async Iterator for Streams

A paginated query is the same pattern with Promise — the consumer asks for one row, the iterator fetches pages behind the scenes:

// iterator/AsyncStreamIterator.ts
interface AsyncIterator<T> {
  next(): Promise<T | null>;
  hasNext(): boolean;
}

class DatabaseQueryIterator implements AsyncIterator<Record<string, unknown>> {
  private currentPage: Record<string, unknown>[] = [];
  private pageIndex = 0;
  private offset = 0;
  private hasMore = true;

  constructor(
    private query: string,
    private pageSize: number = 100,
    private db: { query: (sql: string, params: unknown[]) => Promise<Record<string, unknown>[]> }
  ) {}

  async next(): Promise<Record<string, unknown> | null> {
    if (this.pageIndex >= this.currentPage.length) {
      if (!this.hasMore) return null;
      await this.loadNextPage();
    }

    if (this.pageIndex >= this.currentPage.length) return null;
    return this.currentPage[this.pageIndex++];
  }

  hasNext(): boolean {
    return this.hasMore || this.pageIndex < this.currentPage.length;
  }

  private async loadNextPage(): Promise<void> {
    this.currentPage = await this.db.query(
      `${this.query} LIMIT ${this.pageSize} OFFSET ${this.offset}`,
      []
    );
    this.offset += this.pageSize;
    this.pageIndex = 0;
    this.hasMore = this.currentPage.length === this.pageSize;
  }
}

The caller sees a uniform next()/hasNext() contract whether the collection is a tree in memory or a million-row table behind pagination. That’s the whole point: the traversal strategy lives in the iterator, not in the loop that consumes it.

How It Works

1. Iterator declares the interface for traversal with next(), hasNext(), and reset()
2. Concrete Iterator implements traversal logic for a specific collection structure
3. Aggregate declares the factory method for creating iterators
4. Concrete Aggregate returns a new iterator instance configured for its structure

The client’s loop (while (it.hasNext())) never learns whether elements came from a stack, a queue, a cursor, or an HTTP page — and the collection never learns which traversal ran.

Symbol.iterator vs. a Custom Iterator Interface

In TypeScript/JavaScript you have two doors into this pattern, and they serve different callers:

• Symbol.iterator makes your class work with for...of, spread ([...list]), destructuring, Promise.all, and every library that accepts iterables. It’s the idiomatic choice — see the MDN iteration protocols.
• A named interface (next()/hasNext()/reset()) buys you things Symbol.iterator can’t: rewinding mid-traversal (reset()), choosing the algorithm per call (createIterator('level-order')), and exposing traversal state explicitly. It’s the right shape when traversal itself is the feature.

The pragmatic pattern: implement Symbol.iterator for the default traversal so for...of just works, and keep createIterator(type) for named alternative traversals.

Generators: The Concise Implementation

A manual next()/hasNext() pair tracks state by hand — a stack, a queue, an index. A generator (function*) inverts that: you write the traversal as normal code with yield, and the runtime manages the state machine. Three lines of generator replace a whole iterator class:

class TreeNode<T> {
  children: TreeNode<T>[] = [];
  constructor(public value: T) {}
}

function* preOrder<T>(node: TreeNode<T>): Generator<T> {
  yield node.value;
  for (const child of node.children) {
    yield* preOrder(child);  // delegate to the recursive generator
  }
}

yield* forwards each yielded value from the recursive call, so the recursion reads exactly like the traversal order. Generators are also lazy by construction — values are computed only when consumed, which matters for large or infinite sequences.

Specifying the Iterator Contract

The interface is three methods; the contract is the questions callers will ask that the type system can’t answer. Decide and document four things:

1. Order guarantee. Pre-order DFS and BFS produce different sequences from the same tree — say which one the default iterator returns, or callers will assume “natural order” and be wrong.
2. Laziness. Does next() compute on demand or materialize up front? Lazy is right for streams and big graphs; eager snapshots are right when the collection might mutate mid-traversal.
3. Restart semantics. Can a consumed iterator be reused? Java’s answer is no (Iterator is single-pass); the custom interface here offers reset(). Symbol.iterator handles this differently — each for...of calls the method again, so the iterable is reusable even though each iterator is single-use.
4. End-of-iteration value. null on exhaustion (this example) vs. { done: true } (the protocol) vs. throwing. Callers write while loops against whatever you pick — pick one and keep it uniform across all your iterators.

Under-specified contracts are why “iterator” bugs cluster in production: consumers guess at order, reuse dead iterators, or never observe exhaustion because hasNext() lies.

Testing Your Iterator

Iterators earn their keep on edge cases, and they’re cheap to test because they’re pure state machines:

function collect<T>(it: { next(): T | null; hasNext(): boolean }): T[] {
  const out: T[] = [];
  while (it.hasNext()) out.push(it.next()!);
  return out;
}

// Exhaustion: single node tree yields exactly one value, then stops
const single = new FileSystem();
expect(collect(single.createIterator())).toEqual(['root']);
expect(single.createIterator().next()).toBe('root');

// Order: the two traversals produce different, documented sequences
const fs = new FileSystem();
fs.addNode('root', 'a'); fs.addNode('root', 'b'); fs.addNode('a', 'c');
expect(collect(fs.createIterator('pre-order'))).toEqual(['root', 'a', 'c', 'b']);
expect(collect(fs.createIterator('level-order'))).toEqual(['root', 'a', 'b', 'c']);

// hasNext() is idempotent — calling it twice doesn't consume an element
const it = fs.createIterator();
expect(it.hasNext()).toBe(true);
expect(it.hasNext()).toBe(true);
expect(it.next()).toBe('root');

The hasNext() idempotency test is the one that catches real bugs: plenty of hand-rolled iterators consume state inside hasNext() and silently skip every other element.

Production Considerations

• Implement Symbol.iterator for native for...of loop support in TypeScript
• Use generators (function*) for concise iterator implementation
• Consider async iterators (for await...of) for paginated APIs and streaming data
• Decide on concurrent-modification semantics up front: Java-style fail-fast (throw on mutation during iteration) vs. snapshot semantics (iterate over a stable copy)
• Keep iterators single-use unless reset() is part of the contract — reusing a consumed iterator is a common bug source

Common Mistakes

• Exposing the internal collection index, allowing clients to modify it mid-traversal
• Not handling concurrent modification during iteration — silently skipping or repeating elements
• Implementing only one traversal when multiple are needed
• Using queue.shift() in breadth-first code — O(n) per call; use a head index or real deque
• Loading the whole result set when a lazy/paginated iterator would stream it

Iterating a LinkedList with for…of

The full payoff of Symbol.iterator: a custom LinkedList that behaves like a built-in collection — for...of, spread, destructuring — plus alternative iterators for reverse and filtered traversal:

// Iterator for custom LinkedList
class LinkedListNode<T> {
  constructor(public value: T, public next: LinkedListNode<T> | null = null) {}
}

class LinkedList<T> implements Iterable<T> {
  private head: LinkedListNode<T> | null = null;
  private tail: LinkedListNode<T> | null = null;
  private size = 0;

  append(value: T) {
    const node = new LinkedListNode(value);
    if (!this.head) { this.head = node; this.tail = node; }
    else { this.tail!.next = node; this.tail = node; }
    this.size++;
  }

  // Implement Symbol.iterator to support for...of
  [Symbol.iterator](): Iterator<T> {
    let current = this.head;
    return {
      next(): IteratorResult<T> {
        if (!current) return { done: true, value: undefined };
        const value = current.value;
        current = current.next;
        return { done: false, value };
      }
    };
  }

  // Reverse iterator using generator
  *reverseIterator(): Generator<T> {
    const values: T[] = [];
    let current = this.head;
    while (current) { values.unshift(current.value); current = current.next; }
    for (const v of values) yield v;
  }

  // Filter iterator
  *filterIterator(pred: (v: T) => boolean): Generator<T> {
    let current = this.head;
    while (current) {
      if (pred(current.value)) yield current.value;
      current = current.next;
    }
  }
}

// Usage
const list = new LinkedList<number>();
list.append(1); list.append(2); list.append(3); list.append(4); list.append(5);

// for...of works thanks to Symbol.iterator
for (const v of list) console.log(v); // 1, 2, 3, 4, 5

// Reverse iterator
for (const v of list.reverseIterator()) console.log(v); // 5, 4, 3, 2, 1

// Filter iterator
for (const v of list.filterIterator(x => x % 2 === 0)) console.log(v); // 2, 4

// Spread operator also works
const arr = [...list]; // [1, 2, 3, 4, 5]

Lessons:

• Symbol.iterator makes any iterable compatible with for...of, spread, destructuring
• Generators (function*) are the most concise way to implement iterators
• Custom iterators — filter, reverse, map, slice — avoid intermediate arrays
• Lazy evaluation: generators only compute when consumed
• In JS, Map, Set, String, Array, NodeList are iterable by default

Troubleshooting

• for…of doesn’t work on my class: you implemented a named interface (next()/hasNext()) but not [Symbol.iterator] — for...of only speaks the symbol protocol. Add it, even if it delegates to your custom iterator.
• Level-order traversal is slow on large trees: check for queue.shift() — it reindexes the array every call. Swap in a head index or a deque and the traversal goes from O(n²) back to O(n).
• Iterator skips or repeats elements after mutation: the collection changed mid-traversal. Either document fail-fast behavior (throw a concurrent-modification error) or iterate over a snapshot.
• Async iterator hangs at the end: hasNext() returning true after the last page usually means hasMore was computed as page.length > 0 instead of page.length === pageSize — a short final page then triggers one more fetch that returns nothing.
• Every consumer re-implements the traversal: if three call sites contain the same while loop over internals, the traversal belongs inside an iterator on the collection, not in client code.

Further Reading

• MDN — Iteration protocols
• MDN — function* (generators)
• MDN — for await…of