9 Generic Data Structures

This chapter shows how generics, iterators, and generators work together to decouple independent concerns and maximize reuse in TypeScript. It begins by motivating generics through a reusable identity function and a type-safe alternative to any, then revisits Optional<T> to illustrate how generic types encapsulate behavior independently of the concrete data they carry. Throughout, the emphasis is on separating domain-specific logic from general mechanisms, enabling the compiler to infer types and preserve type safety while reducing duplication.

Building on that foundation, the chapter replaces concrete structures (a number-only binary tree and a string-only linked list) with generic BinaryTreeNode<T> and LinkedListNode<T>, highlighting that data structures have three aspects: the data, the shape (layout), and shape-preserving operations. Traversal is then abstracted via Iterator<T> and Iterable<T>, allowing generic algorithms like print and contains to operate uniformly over different structures. The for...of syntax streamlines consumption of Iterables, and generators provide concise, memory-efficient traversals (yielding values on demand) while supporting multiple traversal strategies over the same structure without coupling algorithms to shapes.

Finally, the chapter extends iteration to infinite streams and pipeline-style processing. Generators can produce unbounded data (for example, random numbers), and can be composed into lazy, demand-driven pipelines with small, reusable stages such as square, take, and drop. Because evaluation occurs only when values are requested, these pipelines scale naturally to continuous or large data flows. The overall result is a modular, type-safe approach where generic data structures define shape, iterators unify traversal, and generators enable concise algorithms and flexible, composable data-processing pipelines.

Generic identity with a type parameter T and two instances: identity<number>() with the concrete type (value: number) => number and identity<Widget[]>() with the concrete type (value: Widget[]) => Widget[].

In-order traversal: recursively go left until we reach the leftmost node, then go to its parent, then to the right node. Next we go back to the parent of the parent, then go to its right node. It’s always left, then when that subtree is all visited parent, then right.

Binary tree example

Linked list example

inOrder() traverses the binary tree in-order and adds all values to a queue. next() dequeues values and returns them during traversal.

BinaryTreeIterator implements binary tree traversal. LinkedListIterator implements linked list traversal. Both implement the Iterator contract. print() and contains() take an Iterator as argument, so we can mix and match the functions with different data structures.

inOrderIterator() is a generator, so it returns an IterableIterator<T>. Like inOrder(), this function recursively traverses the tree but instead of queuing items, it yields them. Calling next() on the returned iterator resumes the generator and yields the next value.

Pipeline and call sequence. take() requests a value from square()’s iterator. square() requests a value from generateRandomNumber()’s iterator. generateRandomNumbers() yields a value to square(). square() yields a value to take().

FAQ

function* inOrderIterator<T>(root: BinaryTreeNode<T>): IterableIterator<T> {
  if (root.left) yield* inOrderIterator(root.left);
  yield root.value;
  if (root.right) yield* inOrderIterator(root.right);
}

function print<T>(iterable: Iterable<T>): void {
  for (const x of iterable) console.log(x);
}
function contains<T>(needle: T, iterable: Iterable<T>): boolean {
  for (const x of iterable) if (x === needle) return true;
  return false;
}

function* square(src: Iterable<number>): IterableIterator<number> {
  for (const x of src) yield x * x;
}
function* take<T>(src: Iterable<T>, n: number): IterableIterator<T> {
  for (const x of src) { if (n-- <= 0) return; yield x; }
}
function* generateRandomNumbers(): IterableIterator<number> {
  while (true) yield Math.random();
}
for (const v of take(square(generateRandomNumbers()), 5)) console.log(v);

class LinkedListNode<T> implements Iterable<T> {
  constructor(public value: T, public next?: LinkedListNode<T>) {}
  [Symbol.iterator](): Iterator<T> {
    return (function* (head: LinkedListNode<T>): IterableIterator<T> {
      let cur: LinkedListNode<T> | undefined = head;
      while (cur) { yield cur.value; cur = cur.next; }
    })(this);
  }
}