Iterator Pattern for Custom Collection Traversal in

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, allowing you to iterate over arrays, trees, graphs, or streams with the same interface.

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

Problem

A tree structure requires different traversal orders for different use cases, but each traversal is tightly coupled to the tree’s node implementation.

Solution

// 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
class LevelOrderIterator<T> implements Iterator<T> {
  private queue: TreeNode<T>[] = [];

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

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

    const node = this.queue.shift()!;
    this.queue.push(...node.children);

    return node.value;
  }

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

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

// File system with iterator
class FileSystem implements IterableCollection<string> {
  private root = new TreeNode<string>('root');

  addNode(parentPath: string, name: string): void {
    const parent = this.findNode(parentPath);
    if (parent) {
      parent.addChild(new TreeNode<string>(name));
    }
  }

  private findNode(path: string): TreeNode<string> | null {
    // Simplified path lookup
    return this.root;
  }

  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');

const preOrder = fs.createIterator('pre-order');
console.log('Pre-order:');
while (preOrder.hasNext()) {
  console.log(preOrder.next());
}

const levelOrder = fs.createIterator('level-order');
console.log('Level-order:');
while (levelOrder.hasNext()) {
  console.log(levelOrder.next());
}

Variation: Async Iterator for Streams

// 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;
  }
}

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

Production Considerations

• Implement Symbol.iterator for native for...of loop support in TypeScript
• Use generators (function*) for concise iterator implementation
• Consider async iterators for paginated APIs and streaming data

Common Mistakes

• Exposing the internal collection index, allowing clients to modify it
• Not handling concurrent modification during iteration
• Implementing only one traversal when multiple are needed

Troubleshooting

• Pattern does not fit the problem: re-evaluate the forces (performance, scalability, team size, coupling). A pattern is only appropriate when its trade-offs match your constraints.
• Too many abstractions: if adding a pattern increases complexity without a clear benefit, simplify. Not every module needs a factory, decorator, or strategy.
• Tight coupling after refactoring: check that interfaces are stable and dependencies point inward.
• Tests break when the design changes: favor stable contracts over internal structure.
• Performance regression from indirection: measure before and after. Layers, decorators, and adapters can add latency; cache or inline hot paths if needed.

Advanced Topics

Scenario: Iterator for Custom Collections

// 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 without intermediate arrays
• Lazy evaluation: generators only compute when consumed
• In JS, Map, Set, String, Array, NodeList are iterable by default

### How do I make my class iterable with for...of?

Implement [Symbol.iterator]() that returns an object with next(). next() returns { done: boolean, value: T }. When done is true, iteration ends. Alternatively, use a generator: *[Symbol.iterator]() { let current = this.head; while (current) { yield current.value; current = current.next; } }. The generator manages state automatically: more concise and less error-prone.