TypeScript · Lesson 6

Data Structures

Build the classic containers (stack, queue, list, heap, LRU, trie, BST, graph) as generic, well-typed TypeScript classes.

5 min read

In short

  • Containers are generic classes with private # fields
  • Empty reads return T | undefined; counts are getters
  • A heap is a tree in an array: push and pop are O(log n)
  • Map keeps insertion order, so LRU is easy
  • State each operation's complexity before you code

Every interview loop and most real codebases eventually need a container that Array and Map don't give you for free. This topic builds the classics as generic classes, so the type checker tracks what goes in and what comes out.

The shape of a generic container

▶ Try
class Stack<T> {
  #items: T[] = [];                      // truly private (runtime), not just `private`

  constructor(items: Iterable<T> = []) {
    for (const item of items) this.push(item);
  }
  push(item: T): void { this.#items.push(item); }
  pop(): T | undefined { return this.#items.pop(); }
  get size(): number { return this.#items.length; }   // read-only from outside
}

const s = new Stack([1, 2, 3]);   // T inferred as number
s.push('x');                      // ✗ compile error: string is not number

Rules of thumb that the exercises enforce:

  • Return T | undefined, never any, for "might be empty" reads (pop, peek, min, get). The caller is then forced to handle the empty case.
  • Expose counts as getters (get size()), so callers can read but not assign them.
  • Take a comparator instead of assuming < works: (a: T, b: T) => number, negative when a comes first. This is the same contract as Array.prototype.sort, so (a, b) => a - b and (a, b) => a.localeCompare(b) just work.
  • Implement [Symbol.iterator] so your container works with for...of, spread and Array.from. A generator method is the shortest way:
▶ Try
class Bag<T> implements Iterable<T> {
  #items: T[] = [];
  *[Symbol.iterator](): Iterator<T> {
    yield* this.#items;
  }
}
const xs = [...new Bag<number>()]; // number[]

Big-O cheat sheet

StructureInsertRemoveLookupNotes
Stack (array)push O(1)*pop O(1)peek O(1)*amortized
Queue (two stacks / ring buffer)O(1)O(1) amortizedpeek O(1)Array.shift() is O(n) on large arrays
Singly linked list (with tail)append/prepend O(1)remove O(n)find O(n)no random access
Binary heapO(log n)pop O(log n)peek O(1)stored in a flat array
LRU cache (Map)O(1)O(1)O(1)Map remembers insertion order
TrieO(L)O(L)O(L)L = word length, independent of word count
BST (unbalanced)O(h)O(h)O(h)h = log n if random, n if sorted input
Graph (adjacency list)edge O(1)neighbors O(deg)BFS/DFS O(V + E)

Heaps in one picture

A binary heap is a complete binary tree stored in an array. For index i:

▶ Try
const parent = (i: number) => (i - 1) >> 1;
const left = (i: number) => 2 * i + 1;
const right = (i: number) => 2 * i + 2;

push appends and sifts up (swap with parent while smaller); pop moves the last element to the root and sifts down (swap with the smaller child). Both touch one root-to-leaf path: O(log n). JavaScript has no built-in priority queue, so you write this yourself in interviews, in Dijkstra, and in schedulers.

Map is an ordered hash table

Map iterates keys in insertion order, and deleting then re-inserting a key moves it to the end. That makes an LRU cache a few lines long:

▶ Try
const m = new Map<string, number>([['a', 1], ['b', 2]]);
m.delete('a'); m.set('a', 1);          // 'a' is now the most recent
const oldest = m.keys().next().value;  // 'b' (type: string | undefined)

Prefer Map over plain objects for dynamic keys: keys can be any type (objects by reference), there's no prototype ('constructor' is not secretly present), and size is O(1).

Trees and graphs

A BST keeps "smaller on the left, larger on the right", so an in-order traversal (left, node, right) yields sorted output. Its weakness: inserting sorted data produces a linked list with height n. Production code uses self-balancing trees (red-black, AVL, B-trees in databases); interviews usually accept the plain BST with that caveat stated out loud.

Graphs are usually an adjacency list: Map<T, T[]> (or Map<T, Set<T>> for O(1) edge checks).

▶ Try
function bfs<T>(adj: Map<T, T[]>, start: T): T[] {
  const seen = new Set<T>([start]);
  const order: T[] = [];
  const queue: T[] = [start];
  for (let head = 0; head < queue.length; head++) {   // index pointer instead of shift()
    const v = queue[head];
    order.push(v);
    for (const n of adj.get(v) ?? []) {
      if (!seen.has(n)) { seen.add(n); queue.push(n); }
    }
  }
  return order;
}
  • BFS finds shortest paths in unweighted graphs (record each vertex's parent, walk back).
  • DFS finds connectivity and cycles, and gives topological order.
  • Topological sort (Kahn's algorithm): repeatedly take vertices with in-degree 0. If you can't take all of them, there's a cycle.

Gotchas

  • Falsy values. if (!this.peek()) breaks for a Stack<number> holding 0. Check size or compare with undefined.
  • Array.prototype.shift is O(n) for big arrays. A queue built on it degrades to O(n²).
  • Recursion depth. A recursive DFS on a 100k-node path graph overflows the call stack. Iterative versions with an explicit stack are safer for unknown inputs.
  • private vs #private. private is erased at runtime (still reachable through (x as any).items); #items is enforced by the engine. Either is fine for exercises.
  • Leaking internals. Returning this.#items from toArray() lets callers mutate your state. Return a copy.
  • Comparator 0 means "equal". For a BST that means "duplicate" (set semantics). For a heap it means "either order is fine".

In interviews / in real codebases

Side note
  • In interviews, say the complexity of each operation before you code and name the trade-off ("two stacks give amortized O(1) dequeue; a ring buffer gives worst-case O(1) but needs resizing").
  • LRU caches, priority queues and tries show up as components in system design too: a CDN eviction policy, a job scheduler, search autocomplete.
  • In product code, reach for Map/Set first and a library for heavier structures. Write your own only when profiling says so. Knowing how they work is what lets you pick the right one.

Practise this lesson

In the app: a short video, 8 exercises checked by real tests and a 12-question concept check. Free with a GitHub account.

Open in the app