Data structures

01 · DATA HAS A SHAPE

Data has a shape

Every program keeps data somewhere: the songs in a playlist, the friends of a user, the words of a dictionary. Memory itself is just one long row of numbered bytes (the Memory page shows it in hardware). A data structure is the plan you lay on top of that row: what goes where, and what points to what.

The plan matters more than the speed of your computer. Here the same 100,000 numbers are kept two ways, as a list and as a set, and asked the same 2,000 questions:

// The same 100,000 numbers, kept two ways
const n = 100_000;
const list = Array.from({ length: n }, (_, i) => i * 2);
const set = new Set(list);
​
// Ask both the same 2,000 questions: "is x in there?"
const questions = Array.from({ length: 2000 }, (_, i) => i * 97);
​
console.time("array.includes");
let a = 0;
for (const x of questions) if (list.includes(x)) a++;
console.timeEnd("array.includes");
​
console.time("set.has");
let b = 0;
for (const x of questions) if (set.has(x)) b++;
console.timeEnd("set.has");
​
console.log("both found", a, "and", b);

How to read the costs

To compare structures, programmers count how the work grows as the data grows, written in Big-O notation (chapter 6 is all about it). You only need four for now:

• O(1), constant: the same few steps whether there are ten items or ten million.
• O(log n), logarithmic: each step halves what is left. A million items take about 20 steps.
• O(n), linear: the work grows in step with the data. Twice the items, twice the time.
• O(n log n) and O(n²): what good sorting costs, and what comparing every pair costs.

The 3D stage has a plinth for each structure. Scroll on and it walks you along them; each caption carries the cost that defines it.

02 · ARRAYS

Arrays: one block of memory

An array is the simplest structure and the most important: items of the same size, side by side in one contiguous block. Because every slot is the same size, the computer can work out where item i lives with arithmetic, without looking at any other item:

address of a[i] = start + i × size

That is why reading a[5] is O(1): in the 3D the beam jumps from the address calculation straight to slot 5. In JavaScript, a typed array is a real block of memory like this:

// A typed array is a real block of memory: 8 slots of 4 bytes
const a = new Int32Array([7, 3, 9, 1, 4, 8, 2, 6]);
console.log("bytes per element:", a.BYTES_PER_ELEMENT);
console.log("total bytes:", a.byteLength);
​
// Pretend the block starts at address 0x1000.
// Finding a[i] is one multiply and one add, whatever i is:
const base = 0x1000;
for (const i of [0, 1, 5, 7]) {
  const addr = base + i * a.BYTES_PER_ELEMENT;
  console.log("a[" + i + "] lives at 0x" + addr.toString(16), "→", a[i]);
}

C shows the arithmetic in the language itself: a[i] is defined as *(a + i), "the thing at address a plus i elements".

int a[8] = {7, 3, 9, 1, 4, 8, 2, 6};
 
/* a[i] is defined as *(a + i): start address plus i elements */
int x = a[5];           /* the compiler emits: load from (a + 5 * 4) */
int *p = &a[0];
int y = *(p + 5);       /* the same 8 */

The catch is the other half of the scene. To insert at the front, every item has to shuffle one slot to the right to make room: 8 moves for 8 items, a million for a million. Inserting or deleting anywhere but the end is O(n).

// Inserting at the front means moving everything else along
function insertAt(arr, index, value) {
  let moves = 0;
  arr.length++;                       // make room at the end
  for (let i = arr.length - 1; i > index; i--) {
    arr[i] = arr[i - 1];              // shift one slot right
    moves++;
  }
  arr[index] = value;
  return moves;
}
​
const a = [7, 3, 9, 1, 4, 8, 2, 6];
console.log("moves:", insertAt(a, 0, 5));
console.log(a.join(" "));
​
const big = Array.from({ length: 1_000_000 }, (_, i) => i);
console.log("moves for a million:", insertAt(big, 0, -1));

03 · DYNAMIC ARRAYS

Dynamic arrays: growing without paying every time

A fixed block can't grow: the memory right after it may belong to something else. So the arrays you use every day (JavaScript's Array, Python's list, Java's ArrayList, C++'s vector) are dynamic arrays: a fixed block with spare room. When it fills up, they allocate a bigger block, copy everything across, and free the old one.

The trick is to grow by a factor, not by a fixed amount. In the 3D, capacity doubles 1 → 2 → 4 → 8 → 16. Most pushes cost one step; the rare ones that trigger a copy cost more (the pink bars), but each copy buys twice as much room as the last:

// A growable array on top of fixed-size blocks, like a JS array or
// Python list underneath: when it is full, allocate double and copy.
class DynArray {
  constructor() {
    this.capacity = 1;
    this.length = 0;
    this.block = new Array(1);
    this.copies = 0;
  }
  push(value) {
    if (this.length === this.capacity) {
      const bigger = new Array(this.capacity * 2);
      for (let i = 0; i < this.length; i++) {
        bigger[i] = this.block[i];     // the expensive part
        this.copies++;
      }
      this.block = bigger;
      this.capacity *= 2;
    }
    this.block[this.length++] = value;
  }
}
​
const d = new DynArray();
for (let i = 1; i <= 9; i++) {
  d.push(i);
  console.log("push", i, " length", d.length, " capacity", d.capacity, " copies so far", d.copies);
}
​
const big = new DynArray();
for (let i = 0; i < 1_000_000; i++) big.push(i);
console.log("a million pushes cost", big.copies, "copies:", (big.copies / 1e6).toFixed(2), "per push");

Averaged over many operations, push is O(1) amortised: the expensive moments are paid for by the cheap ones around them. The Java documentation states it as a promise: adding an element "has constant amortized time cost". Real growth factors vary, and all of them are factors:

import sys
 
xs = []
for i in range(10):
    xs.append(i)
    print(len(xs), sys.getsizeof(xs))   # bytes jump only when it grows

04 · LINKED LISTS

Linked lists: a chain of references

A linked list gives up the contiguous block. Each item lives in its own small node, wherever the memory allocator found room, and holds a reference (a pointer) to the next node. The list itself is just a reference to the first node, the head; the last node points to null.

The 3D shows both sides of that bargain. To reach index 3 there is no arithmetic to do: you must hop from node to node, so get(i) is O(n), and each hop may land on a different part of memory (the lit squares on the back wall), which the cache hates. But once you hold a node, splicing a new one in after it changes two references and moves nothing: O(1), however long the list.

// Each node holds a value and a reference to the next node
function node(value, next = null) {
  return { value, next };
}
​
// 12 → 7 → 30 → 4 → 19 → null
let head = node(12, node(7, node(30, node(4, node(19)))));
​
function get(head, index) {
  let cur = head;
  for (let i = 0; i < index; i++) cur = cur.next;   // walk, one hop at a time
  return cur;
}
​
function insertAfter(prev, value) {
  prev.next = node(value, prev.next);               // two references change
}
​
function show(head) {
  const out = [];
  for (let cur = head; cur !== null; cur = cur.next) out.push(cur.value);
  return out.join(" → ") + " → null";
}
​
console.log(show(head));
console.log("index 3 is", get(head, 3).value, "(3 hops)");
insertAfter(get(head, 1), 25);
console.log(show(head));

Linked lists shine when you insert and remove in the middle of a sequence you are already walking, or need stable references to items that never move: the free lists inside memory allocators, the run queues of operating-system schedulers, the order list inside an LRU cache. A doubly linked list adds a prev reference to each node, so you can also walk backwards and unlink a node in O(1) given only the node itself.

05 · STACKS & QUEUES

Stacks and queues: rules about order

Stacks and queues aren't new memory layouts. They are rules about which item comes out next, and that restriction is the whole point: code that uses them can't get the order wrong.

• A stack is last in, first out (LIFO), like a pile of plates: push on top, pop from the top. A JavaScript array with push and pop is already one. Every function call you make lands on a stack: the call stack from chapter 4.
• A queue is first in, first out (FIFO), like a line at a till: enqueue at the back, dequeue from the front. Printers, web servers and message brokers all keep queues of work.

Stacks are perfect for anything nested. Checking that brackets match is the textbook example: push every opener, and every closer must match the opener on top.

// A stack in JavaScript is just an array: push and pop at the end
function balanced(text) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of text) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;   // wrong closer
    }
  }
  return stack.length === 0;                          // nothing left open
}
​
for (const t of ["(a[1] + b) * {c}", "([)]", "((x)", "f(g(h()))"]) {
  console.log(balanced(t) ? "ok  " : "bad ", t);
}

A queue on a plain array is a trap: shift() takes from the front, so in principle every other item moves along one slot, making each dequeue O(n). The 3D shows the fix that real queues use: a ring buffer, a fixed array where the head and the tail chase each other round and wrap past the end. Nothing ever moves; both operations are O(1).

// A queue as a ring buffer: a fixed array, a head and a tail that wrap
class Queue {
  constructor(capacity) {
    this.slots = new Array(capacity);
    this.head = 0;      // where the next item leaves
    this.size = 0;
  }
  enqueue(x) {
    if (this.size === this.slots.length) throw new Error("full");
    const tail = (this.head + this.size) % this.slots.length;
    this.slots[tail] = x;
    this.size++;
  }
  dequeue() {
    if (this.size === 0) return undefined;
    const x = this.slots[this.head];
    this.slots[this.head] = undefined;
    this.head = (this.head + 1) % this.slots.length;   // wrap around
    this.size--;
    return x;
  }
}
​
const q = new Queue(4);
q.enqueue("a"); q.enqueue("b"); q.enqueue("c");
console.log(q.dequeue(), q.dequeue());     // first in, first out
q.enqueue("d"); q.enqueue("e"); q.enqueue("f");
console.log(q.slots, "head =", q.head);    // "e" and "f" wrapped to the front
console.log(q.dequeue(), q.dequeue(), q.dequeue(), q.dequeue());

A deque (double-ended queue) allows both ends; Python's collections.deque is the one to reach for there.

06 · HASH MAPS

Hash maps: from a key straight to a bucket

Arrays find things by position. Most of the time you want to find things by name: the price of "apple", the user with this email. A hash map (also called a hash table or dictionary) does this in O(1) on average, and it is the structure you will use most.

The idea: keep an array of buckets, and use a hash function to turn any key into a number. Take the number modulo the bucket count, and that is the bucket. To look the key up later, hash it again and go straight there. In the 3D, six keys go through FNV-1a, a real hash function, and land in eight buckets:

// FNV-1a: a simple, real hash function (32-bit)
function fnv1a(text) {
  let h = 0x811c9dc5;
  for (const ch of text) {
    h ^= ch.charCodeAt(0);
    h = Math.imul(h, 0x01000193) >>> 0;   // multiply, keep 32 bits
  }
  return h;
}
​
const buckets = 8;
for (const key of ["cat", "dog", "owl", "emu", "yak", "bee"]) {
  const h = fnv1a(key);
  console.log(key.padEnd(4), "hash 0x" + h.toString(16).padStart(8, "0"), "→ bucket", h % buckets);
}
// cat and bee both land in bucket 7: a collision

A hash function must be deterministic (the same key always gives the same number), fast, and spread keys evenly. It doesn't need to be secret: the cryptographic hashes on the Encryption and password pages add a further promise, that you can't work backwards from the output, which hash tables don't need.

Look at cat and bee: different keys, same bucket. That is a collision, and with more keys than buckets it is certain. The simplest fix, chaining, keeps a small list in each bucket and checks the keys in it one by one. Here is a whole hash map in twenty lines, and JavaScript's own:

function fnv1a(text) {
  let h = 0x811c9dc5;
  for (const ch of text) { h ^= ch.charCodeAt(0); h = Math.imul(h, 0x01000193) >>> 0; }
  return h;
}
​
// A hash map with chaining: each bucket is a short list of [key, value]
class HashMap {
  constructor(m = 8) { this.buckets = Array.from({ length: m }, () => []); }
  bucketFor(key) { return this.buckets[fnv1a(key) % this.buckets.length]; }
  set(key, value) {
    const b = this.bucketFor(key);
    const hit = b.find((pair) => pair[0] === key);
    if (hit) hit[1] = value;          // key exists: replace
    else b.push([key, value]);        // new key: add to the chain
  }
  get(key) {
    const hit = this.bucketFor(key).find((pair) => pair[0] === key);
    return hit ? hit[1] : undefined;
  }
}
​
const legs = new HashMap();
legs.set("cat", 4); legs.set("owl", 2); legs.set("bee", 6);
console.log(legs.get("bee"), legs.get("owl"), legs.get("yak"));
console.log(JSON.stringify(legs.buckets));
​
// JavaScript's own: Map (any key type, remembers insertion order)
const m = new Map([["cat", 4], ["owl", 2]]);
m.set("bee", 6);
console.log(m.get("bee"), m.size, [...m.keys()]);

ages = {"ada": 36, "alan": 41}
ages["grace"] = 85            # set: O(1) on average
print(ages.get("alan"))      # get: O(1) on average
print("ada" in ages)         # membership: O(1) on average
 
seen = set()                 # a set is a dict with keys only
seen.add("owl")

07 · COLLISIONS & LOAD

Collisions and the load factor

A hash map is only fast while its chains stay short. The measure is the load factor, α = n / m: items per bucket. In the 3D the table starts with four buckets; hen and yak collide in bucket 0 and the gauge climbs to 0.75. When the next insert would push it over, the table grows: it allocates twice the buckets and rehashes every key into its new home, because hash % 8 differs from hash % 4. Afterwards hen and yak are apart, and no chain is longer than one.

function fnv1a(text) {
  let h = 0x811c9dc5;
  for (const ch of text) { h ^= ch.charCodeAt(0); h = Math.imul(h, 0x01000193) >>> 0; }
  return h;
}
​
class HashMap {
  constructor() { this.buckets = [[], [], [], []]; this.size = 0; }
  load() { return this.size / this.buckets.length; }
  set(key, value) {
    if ((this.size + 1) / this.buckets.length > 0.75) this.grow();
    this.buckets[fnv1a(key) % this.buckets.length].push([key, value]);
    this.size++;
  }
  grow() {
    const old = this.buckets.flat();
    this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);
    for (const [k, v] of old) this.buckets[fnv1a(k) % this.buckets.length].push([k, v]);
    console.log("  grew to", this.buckets.length, "buckets, rehashed", old.length, "keys");
  }
  chains() { return this.buckets.map((b) => b.length).join(" "); }
}
​
const h = new HashMap();
for (const key of ["hen", "yak", "koi", "owl", "fox", "ape"]) {
  h.set(key, true);
  console.log(key, " load", h.load().toFixed(2), " chain lengths:", h.chains());
}

A resize costs O(n), but like the dynamic array it doubles each time, so it is O(1) amortised. Java's HashMap resizes at a load factor of 0.75, which its documentation calls "a good tradeoff between time and space costs". CPython's dict uses open addressing instead of chains (a colliding key tries other slots in the same array) and resizes when two-thirds full.

08 · SETS

Sets: keys without values

A set holds each value at most once and answers one question fast: "is x in here?" Underneath, it is usually a hash map that keeps only the keys, so add, has and delete are O(1) on average. Adding a value that is already there changes nothing: in the 3D, the second dog dissolves into the first.

Sets also do the operations from maths: union (in either), intersection (in both) and difference (in one but not the other). Each costs time proportional to the sets involved, because every element is checked with one O(1) has.

const a = new Set(["cat", "dog", "owl", "bee"]);
const b = new Set(["owl", "bee", "emu", "yak"]);
​
a.add("dog");                         // already there: nothing changes
console.log("size", a.size, "has owl?", a.has("owl"));
​
const union = new Set([...a, ...b]);
const both = new Set([...a].filter((x) => b.has(x)));
const onlyA = new Set([...a].filter((x) => !b.has(x)));
console.log("A ∪ B", [...union]);
console.log("A ∩ B", [...both]);
console.log("A − B", [...onlyA]);
​
// The classic one-liner: remove duplicates
console.log([...new Set([3, 1, 3, 2, 1])]);

Reach for a set whenever you catch yourself writing array.includes(x) inside a loop: that is O(n) per check, and the first example in this chapter showed what it costs. Removing duplicates, tracking "already visited" in a search, and comparing two lists of IDs are all set jobs.

09 · SEARCH TREES

Binary search trees: order and speed

Hash maps find a key fast but know nothing about order: they can't give you "every price between 10 and 20" or "the next name after Smith". A binary search tree (BST) can. Each node has up to two children, with one rule: everything in the left subtree is smaller, everything in the right is bigger.

To find a key, start at the root and compare: smaller, go left; bigger, go right. Each comparison throws away a whole subtree. In the 3D, the search for 65 takes 4 steps among 9 keys. Walking the tree in order (left subtree, node, right subtree) visits the keys sorted, for free.

function insert(node, key) {
  if (node === null) return { key, left: null, right: null };
  if (key < node.key) node.left = insert(node.left, key);
  else node.right = insert(node.right, key);
  return node;
}
​
function search(node, key) {
  let steps = 0;
  while (node !== null) {
    steps++;
    if (key === node.key) return steps;
    node = key < node.key ? node.left : node.right;   // discard half
  }
  return -steps;                                     // not found
}
​
function inOrder(node, out = []) {
  if (node) { inOrder(node.left, out); out.push(node.key); inOrder(node.right, out); }
  return out;
}
​
let root = null;
for (const k of [50, 30, 70, 20, 40, 60, 80, 35, 65]) root = insert(root, k);
console.log("found 65 in", search(root, 65), "steps");
console.log("in order:", inOrder(root).join(" "));

Search, insert and delete all cost O(h), where h is the height of the tree. Trees are everywhere in computing: the file system on your disk, the parse tree from chapter 1, the HTML of this page (the DOM), and the objects inside git, where every commit points to a tree of folders and files.

10 · BALANCED TREES

Balanced trees: keeping the height down

O(h) is only good news if h is small, and a plain BST makes no promise. Insert keys that are already sorted and each one goes to the right of the last: the 3D shows 1 to 7 forming a chain of height 7, which is just a linked list with extra steps. Finding 7 takes 7 comparisons.

function insert(node, key) {
  if (node === null) return { key, left: null, right: null };
  if (key < node.key) node.left = insert(node.left, key);
  else node.right = insert(node.right, key);
  return node;
}
const height = (n) => (n === null ? 0 : 1 + Math.max(height(n.left), height(n.right)));
​
// Sorted input: every key goes right. The "tree" is a linked list.
let chain = null;
for (let k = 1; k <= 1000; k++) chain = insert(chain, k);
console.log("sorted inserts, height:", height(chain));
​
// The same keys, middle first: a perfectly balanced tree
function build(lo, hi) {
  if (lo > hi) return null;
  const mid = Math.floor((lo + hi) / 2);
  return { key: mid, left: build(lo, mid - 1), right: build(mid + 1, hi) };
}
console.log("balanced, height:", height(build(1, 1000)));
console.log("log2(1000) =", Math.log2(1000).toFixed(2));

Self-balancing trees fix this by restructuring as they go. After each insert or delete they check the shape and, where one side has grown too tall, perform rotations: local rearrangements that lift a child above its parent while keeping the left-smaller, right-bigger order. The height stays near log₂ n, so every operation is O(log n) guaranteed. In the 3D, the chain rearranges into a tree of height 3 and finding 7 takes 3 steps.

• AVL trees (Adelson-Velsky and Landis, 1962), the first: the two subtrees of any node differ in height by at most one.
• Red-black trees (Guibas and Sedgewick, 1978): a looser rule that needs fewer rotations. Java's TreeMap is one.
• B-trees (Bayer and McCreight, 1972): nodes with hundreds of keys each, so the tree is only three or four levels deep even for huge tables. They suit disks, where reading one big block costs about the same as reading one byte. Almost every database index is a B-tree, chapter 11's subject.

-- A database index is a balanced tree (a B-tree) over a column
CREATE INDEX users_by_email ON users (email);
 
-- Now this is a walk down a few tree levels, not a scan of every row
SELECT * FROM users WHERE email = 'ada@example.com';

11 · HEAPS

Heaps: always know the smallest

Sometimes you don't need everything in order, only the most urgent item: the next timer to fire, the cheapest route so far, the task with the highest priority. A heap keeps exactly that at hand. A min-heap is a tree with a weaker rule than a BST: every parent is smaller than or equal to its children. So the smallest item is always at the root: peek is O(1).

The clever part is where it lives. A heap is a complete tree (every level full except the last, which fills from the left), so it fits in a plain array with no pointers at all: the children of index i are at 2i + 1 and 2i + 2. The 3D shows the tree and its array together. push(2) adds 2 at the end and swaps it up past bigger parents; pop() takes the root, moves the last item to the top and swaps it down past smaller children. Both are O(log n): at most one swap per level.

// A min-heap stored in a plain array.
// Node i has children 2i+1 and 2i+2, and parent floor((i-1)/2).
class MinHeap {
  constructor(items = []) { this.a = items; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];        // bubble up
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];      // sift down
        i = m;
      }
    }
    return top;
  }
}
​
const h = new MinHeap([3, 8, 5, 12, 10, 9, 7]);
h.push(2);
console.log("after push(2):", h.a.join(" "));
console.log("pop →", h.pop());
console.log("after pop:   ", h.a.join(" "));
const sorted = [];
while (h.a.length) sorted.push(h.pop());
console.log("popping them all:", sorted.join(" "));

A heap is the usual way to build a priority queue. Python ships one in heapq; route-finding algorithms like Dijkstra's use one to always expand the closest place next.

import heapq
 
tasks = [(3, "email"), (1, "fix the outage"), (2, "review")]
heapq.heapify(tasks)                  # O(n)
heapq.heappush(tasks, (0, "fire alarm"))
print(heapq.heappop(tasks))          # (0, 'fire alarm')
print(heapq.heappop(tasks))          # (1, 'fix the outage')

12 · GRAPHS

Graphs: anything connected to anything

Lists, trees and heaps all have a fixed shape. A graph has none: it is a set of nodes (vertices) joined by edges, and any node may connect to any other. Road maps, social networks, the links between web pages, the routers of the Internet, the dependencies between packages, and git's history of commits are all graphs. Edges can have a direction (a follows b) and a weight (a road's length).

There are two standard ways to store one, and the 3D shows both beside the same graph:

• An adjacency matrix: an n × n grid with a 1 where an edge exists. Checking one edge is O(1), but it always takes n² cells: a million users would need a trillion.
• An adjacency list: each node keeps a list of its neighbours. Space is proportional to n + e, and walking a node's neighbours costs only its degree. Most real graphs are sparse (few edges per node), so this is the usual choice.

The most useful thing to do with a graph is to search it. Breadth-first search (BFS) explores in rings, all nodes 1 hop away, then 2, then 3, using a queue, and so finds the fewest hops to everything. In the 3D, each node lights its row of the matrix and list as BFS reads its neighbours. Swap the queue for a stack and you get depth-first search, which dives down one path before backing up.

const nodes = ["A", "B", "C", "D", "E", "F"];
const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["C", "D"], ["C", "E"], ["D", "E"], ["E", "F"]];
​
// Adjacency matrix: n × n cells, 1 where an edge exists
const idx = Object.fromEntries(nodes.map((v, i) => [v, i]));
const matrix = nodes.map(() => nodes.map(() => 0));
// Adjacency list: each node keeps a list of its neighbours
const adj = Object.fromEntries(nodes.map((v) => [v, []]));
​
for (const [u, v] of edges) {
  matrix[idx[u]][idx[v]] = matrix[idx[v]][idx[u]] = 1;
  adj[u].push(v); adj[v].push(u);
}
console.log("   " + nodes.join(" "));
nodes.forEach((v, i) => console.log(v + "  " + matrix[i].join(" ")));
console.log(adj);
​
// Breadth-first search: fewest hops from A to everything
const dist = { A: 0 };
const queue = ["A"];
while (queue.length) {
  const u = queue.shift();
  for (const v of adj[u]) if (!(v in dist)) { dist[v] = dist[u] + 1; queue.push(v); }
}
console.log(dist);

13 · TRIES

Tries: trees of letters

A trie (from retrieval; Edward Fredkin named it in 1960) stores strings by sharing their beginnings. Each edge is one letter, each path from the root spells a prefix, and a mark on a node says "a word ends here". In the 3D, car, cart and cat share c and a.

Looking up a word costs O(length of the word), however many words are stored. More usefully, every word starting with a prefix sits in one subtree: walk down to do and everything below is do, dog, dot. That is autocomplete, spell checkers, and the longest-prefix match routers use to pick where to send a packet.

class Trie {
  constructor() { this.root = { kids: {}, end: false }; }
  insert(word) {
    let n = this.root;
    for (const ch of word) n = n.kids[ch] ??= { kids: {}, end: false };
    n.end = true;                     // a word stops here
  }
  find(prefix) {
    let n = this.root;
    for (const ch of prefix) { n = n.kids[ch]; if (!n) return null; }
    return n;
  }
  has(word) { return this.find(word)?.end === true; }
  complete(prefix) {
    const out = [];
    const walk = (n, s) => {
      if (n.end) out.push(s);
      for (const ch of Object.keys(n.kids).sort()) walk(n.kids[ch], s + ch);
    };
    const start = this.find(prefix);
    if (start) walk(start, prefix);
    return out;
  }
}
​
const t = new Trie();
for (const w of ["car", "cart", "cat", "do", "dog", "dot"]) t.insert(w);
console.log(t.has("cart"), t.has("ca"), t.has("cow"));
console.log("do… →", t.complete("do"));
console.log("ca… →", t.complete("ca"));

The price is memory: a node per letter, each with its own table of children. Compressed variants (radix trees, which merge chains of single children into one edge) cut that down.

14 · CHOOSING ONE

Choosing the right structure

Every structure is a trade: it makes some operations cheap by making others expensive or by spending memory. So choose by asking what your program does most, then pick the structure that makes that cheap:

• Look things up by a key or ID? Hash map. Only need yes/no? Set.
• Need them in order, or ranges like "between 10 and 20"? A balanced tree, or a sorted array if the data rarely changes (binary search is O(log n)).
• Always want the smallest, largest or most urgent? Heap.
• Process in arrival order, or the most recent first? Queue, or stack.
• Things connected to things? Graph, as an adjacency list unless it is small and dense.
• Searching by prefix? Trie.
• Everything else? Start with an array. It is the most cache-friendly, the simplest, and fast enough far more often than its Big-O suggests. Measure before you get clever.

Real programs combine them. A word counter uses a map for the counts and an array to rank them; an LRU cache is a hash map plus a doubly linked list; a database is B-trees over pages of arrays.

// Word count: a Map does the counting, an array does the ranking
const text = "the cat sat on the mat and the dog sat on the cat";
​
const counts = new Map();
for (const w of text.split(" ")) counts.set(w, (counts.get(w) ?? 0) + 1);
​
const top = [...counts].sort((a, b) => b[1] - a[1]).slice(0, 3);
console.log(top);