TypeScript · Lesson 6
Data Structures
Build the classic containers (stack, queue, list, heap, LRU, trie, BST, graph) as generic, well-typed TypeScript classes.
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)
Mapkeeps 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
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, neverany, 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 whenacomes first. This is the same contract asArray.prototype.sort, so(a, b) => a - band(a, b) => a.localeCompare(b)just work. - Implement
[Symbol.iterator]so your container works withfor...of, spread andArray.from. A generator method is the shortest way:
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
| Structure | Insert | Remove | Lookup | Notes |
|---|---|---|---|---|
| Stack (array) | push O(1)* | pop O(1) | peek O(1) | *amortized |
| Queue (two stacks / ring buffer) | O(1) | O(1) amortized | peek 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 heap | O(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 |
| Trie | O(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:
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:
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).
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 aStack<number>holding0. Checksizeor compare withundefined. Array.prototype.shiftis 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.
privatevs#private.privateis erased at runtime (still reachable through(x as any).items);#itemsis enforced by the engine. Either is fine for exercises.- Leaking internals. Returning
this.#itemsfromtoArray()lets callers mutate your state. Return a copy. - Comparator
0means "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/Setfirst 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