Foundations of Data Structures: A Visual Guide

A data structure is a decision about layout. The values are the same. What changes is which question is cheap: the i-th item, the next item, the smallest item, the item with this key, the neighbors of this node, or whether two items have already been joined.

This note is a reference for those decisions. Each structure has the same five parts: where the idea came from, what the operations cost, a plain explanation, a diagram you can step through, and the same operations in TypeScript and Python. The code is the textbook structure. The TypeScript is what the diagrams run, and it can be copied into a file and typechecked. The Python is those same steps for 3.10 or newer. Neither one is a description of how a particular engine stores its built-in arrays, maps, or sets.

How to use this guide

Each diagram is one operation, broken into the assignments that matter.

• Play runs the steps on a timer. Pause stops it. Step and Back move one change. Reset returns to the first picture. Speed runs from 1× to 4×.
• With the controls focused, the right arrow steps forward, the left arrow steps back, and Home resets.
• The sentence under the picture is the same state as the drawing. On a narrow screen, scroll the picture if it is wider than the page. The sentence still names every value.
• Now, Visited, Queued, and Collision are written on the picture. Color repeats those words. A pointer is an arrow with a name such as next or parent.
• If the system asks for reduced motion, automatic play stays off. Step still works, and nothing slides.
• On any code sample, choose TypeScript or Python. Every sample on the page follows. Arrow keys move between the two languages while a language tab is focused. The choice is remembered in this browser.

The comparison table below is the map. The sections are the reason the cells say what they say.

Complexity at a glance

These are the usual bounds in the RAM model. “Expected” means a hash that spreads keys. “Amortized” means the average over a sequence, not a promise about one call. The letter h is the height of a tree. The letter L is the length of a key. The closing section states the assumptions in one place.

A balanced search tree, such as a red-black tree, keeps h logarithmic. A plain binary search tree does not. The hash bounds collapse if every key lands in one bucket. Both of those sentences are doing more work than the table can show on its own.

Arrays

History

Indexed blocks of storage are older than any one programming language. What changed in the late 1950s was that a language would name the block for you. The FORTRAN group at IBM, writing in 1957, treated arrays as a basic way to talk about a sequence of numbers by subscript. The growing array in this section is the later textbook object: when the block is full, allocate a longer one, copy, and continue. Cormen, Leiserson, Rivest, and Stein analyze the geometric version of that growth. Doubling the capacity makes a sequence of appends cheap on average, even though a single append can copy every element.

Time complexity

Index

O(1)

Unsorted search

O(n)

Middle insert

O(n)

Append

Amortized O(1)

Reading or writing a slot by index is O(1), provided the index is in range. Inserting or deleting at an arbitrary index moves every later element, so it is O(n). Appending is O(1) most of the time. When length meets capacity, the copy is O(n). If capacity doubles each time, those copies across n appends add up to fewer than 2n element moves, so the amortized cost of one append is O(1). A sequence of appends that grows by one slot each time is not amortized O(1). The constant factor in the growth is the whole proof.

Space is O(n) for the values, plus up to almost n empty slots just after a doubling. That spare capacity is intentional.

Explanation

A dynamic array is a numbered row of equal slots, plus a length that says how many of those slots are real values. The address of slot i is the base address plus i times the size of one slot. That arithmetic is the whole trick. It is also why inserting in the middle has to slide the tail.

Use an array when you have a sequence, you mostly grow it at the end, and you want index access or a tight scan. Text buffers, dynamic tables, the backing store of a stack, and the pixel row of an image are all this shape. A scan of an array is kind to the CPU cache because the next value is the next address. A linked list does not have that property.

Do not use an array when the common edit is in the middle of a long sequence and you do it on a hot path. Do not treat a JavaScript array as this object without looking. The language defines arrays as exotic objects with a length, and an engine may store a dense array in a contiguous block while storing a sparse one very differently. Deleting an element with delete can leave a hole. splice is the honest middle insert, and it moves the tail.

Compared with a linked list, the array wins on access and on scanning. The list wins when you already hold the node and only need to splice. Compared with a hash table, the array wins when the key is a small integer index and order matters.

Diagram

Code

export class DynamicArray<T> {
  slots: (T | undefined)[];
  length = 0;

  constructor(capacity = 4) {
    this.slots = Array.from({ length: capacity }, () => undefined);
  }

  get capacity(): number {
    return this.slots.length;
  }

  /** Shift the tail right, then write. Returns true if the block was replaced. */
  insert(index: number, value: T): boolean {
    if (index < 0 || index > this.length) throw new RangeError('index out of range');
    const resized = this.ensure(this.length + 1);
    for (let cursor = this.length; cursor > index; cursor -= 1) {
      this.slots[cursor] = this.slots[cursor - 1];
    }
    this.slots[index] = value;
    this.length += 1;
    return resized;
  }

  push(value: T): boolean {
    return this.insert(this.length, value);
  }

  private ensure(needed: number): boolean {
    if (needed <= this.slots.length) return false;
    let capacity = Math.max(1, this.slots.length);
    while (capacity < needed) capacity *= 2;
    const next: (T | undefined)[] = Array.from({ length: capacity }, () => undefined);
    for (let index = 0; index < this.length; index += 1) next[index] = this.slots[index];
    this.slots = next;
    return true;
  }
}

from typing import Generic, TypeVar

T = TypeVar("T")


class DynamicArray(Generic[T]):
    def __init__(self, capacity: int = 4) -> None:
        self.slots: list[T | None] = [None] * capacity
        self.length = 0

    @property
    def capacity(self) -> int:
        return len(self.slots)

    def insert(self, index: int, value: T) -> bool:
        """Shift the tail right, then write. Returns true if the block was replaced."""
        if index < 0 or index > self.length:
            raise IndexError("index out of range")
        resized = self._ensure(self.length + 1)
        cursor = self.length
        while cursor > index:
            self.slots[cursor] = self.slots[cursor - 1]
            cursor -= 1
        self.slots[index] = value
        self.length += 1
        return resized

    def push(self, value: T) -> bool:
        return self.insert(self.length, value)

    def _ensure(self, needed: int) -> bool:
        if needed <= len(self.slots):
            return False
        capacity = max(1, len(self.slots))
        while capacity < needed:
            capacity *= 2
        nxt: list[T | None] = [None] * capacity
        for index in range(self.length):
            nxt[index] = self.slots[index]
        self.slots = nxt
        return True

Singly linked lists

History

Knuth records that an internal IBM memorandum by H. P. Luhn, in January 1953, used chains of records hanging off buckets, and that this was one of the first uses of linked linear lists. The idea became something a programmer could write down as a language a few years later. Information Processing Language, built by Allen Newell, Cliff Shaw, and Herbert Simon around 1956, was organized around lists. The Turing Award citation for Newell treats that list processing as part of the foundation IPL left to later languages, including LISP.

Time complexity

Reach index i

O(i)

Insert after a held node

O(1)

Delete with predecessor

O(1)

Search

O(n)

Reaching the i-th node is O(i), which is O(n) in the worst case. Once you hold a node, inserting after it is O(1), and it is two assignments in a fixed order. Searching is O(n). Extra space is one pointer per node, plus whatever the allocator adds around each allocation. For a small value, the pointer and the allocation can cost more than the value.

Explanation

A singly linked list stores each value in a node, and each node stores where the next one is. There is no arithmetic that jumps to the tenth node. You follow next ten times. The compensation is local surgery: if you are already holding a node, you can splice a neighbor without sliding a tail. One pointer per node points forward. The head is the only named entrance. The last node points at null.

Create the new node so that it already points at the old successor. Then swing the predecessor. If you swing the predecessor first, the rest of the list is no longer reachable. That is the failure mode the diagram is built to prevent.

A singly linked list is a good shape for a queue when you keep both a head and a tail, for a hash bucket chain, and for any structure that grows by consing onto the front. It is a poor shape for random access, for going backward, and for deleting a node when all you hold is the node itself. You need the predecessor to repair next, and finding it is another walk.

Diagram

Code

export interface SNode<T> {
  value: T;
  next: SNode<T> | null;
}

/** Point the new node at the old successor before swinging the predecessor. */
export function insertAfter<T>(node: SNode<T>, value: T): SNode<T> {
  const created: SNode<T> = { value, next: node.next };
  node.next = created;
  return created;
}

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


@dataclass
class SNode(Generic[T]):
    value: T
    next: SNode[T] | None = None


def insert_after(node: SNode[T], value: T) -> SNode[T]:
    """Point the new node at the old successor before swinging the predecessor."""
    created = SNode(value, node.next)
    node.next = created
    return created

Doubly linked lists

History

The second link does not have a single inventor to name. Once a list is a chain of nodes, storing the predecessor is the direct way to delete a node you already hold. Knuth presents singly and doubly linked lists together as basic forms of the linear list. The cost of the extra word, and the bugs that come from updating one direction and not the other, are the reason it is its own structure.

Time complexity

Reach index i

O(n)

Insert at a known node

O(1)

Delete at a known node

O(1)

Insert and delete at a known node are O(1). You update at most four pointers: the two neighbors, then the detached node if you want it clearly unreachable. Indexing is still O(n). A scan still chases pointers, so a long list of small values is often slower than the array it was meant to beat, even when the big-O of a splice looks better.

Explanation

A second pointer names the predecessor. The extra word per node buys a deletion that does not search. Forgetting one direction leaves a pointer into a node the list has otherwise dropped, or a neighbor that still names the node you meant to remove.

Doubly linked lists show up in LRU caches, in intrusive lists inside kernels, and anywhere an object must leave a collection without a search. Prefer an array of handles, or a hash table, when you need lookup by key. Prefer a singly linked list when you only ever insert at the front and memory is tight.

Diagram

Code

export interface DNode<T> {
  value: T;
  next: DNode<T> | null;
  prev: DNode<T> | null;
}

/** Unlink a node you already hold. Each living neighbor is updated once. */
export function removeNode<T>(node: DNode<T>): void {
  const previous = node.prev;
  const following = node.next;
  if (previous) previous.next = following;
  if (following) following.prev = previous;
  node.next = null;
  node.prev = null;
}

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


@dataclass
class DNode(Generic[T]):
    value: T
    next: DNode[T] | None = None
    prev: DNode[T] | None = None


def remove_node(node: DNode[T]) -> None:
    """Unlink a node you already hold. Each living neighbor is updated once."""
    previous = node.prev
    following = node.next
    if previous:
        previous.next = following
    if following:
        following.prev = previous
    node.next = None
    node.prev = None

Stacks

History

The stack was arrived at more than once, which is a reason not to assign it to one person. A 1947 account of the group around Alan Turing at the National Physical Laboratory describes reversion storage: return addresses kept so that the most recent subroutine is resumed first. Friedrich Bauer and Klaus Samelson developed the same discipline for formula translation, calling it a cellar, in 1955, and filed a patent in 1957. IPL, around 1956, used an explicit stack for list processing. The useful fact is the rule, not a single birth year.

Time complexity

Push

O(1)

Pop

O(1)

Peek

O(1)

Search

O(n)

Push, pop, and peek are O(1) if the backing store can grow at the end in amortized constant time. Searching the stack for an arbitrary value is O(n), and it is usually a sign that you wanted a different structure. Space is O(n) values. A recursive function is a stack whether you wrote one or not. The call stack has a fixed ceiling, and a skewed recursion can hit it while the same algorithm written with an explicit heap-allocated stack would only get slower.

Explanation

A stack is a list with a rule: the only item you may see or remove is the one most recently pushed. Last in, first out. The rule is the structure. The storage underneath is usually an array, or a singly linked list with the head as the top.

Use a stack for undo, for matching brackets, for depth-first search, for evaluating postfix expressions, and for any nested scope that must close in the reverse of the order it opened. Do not use a stack when the consumer needs the oldest item. That is a queue. Do not pop without checking emptiness if an empty pop is a bug rather than a normal end. pop on an empty JavaScript array returns undefined, and that value may also be a legitimate element. A separate size, or a result type, keeps those apart.

Compared with an array you are allowed to index, a stack is an array plus a refusal. The refusal is what makes the invariant easy to keep.

Diagram

Code

export class Stack<T> {
  private items: T[] = [];

  push(value: T): void {
    this.items.push(value);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items.at(-1);
  }

  get size(): number {
    return this.items.length;
  }
}

from typing import Generic, TypeVar

T = TypeVar("T")


class Stack(Generic[T]):
    def __init__(self) -> None:
        self._items: list[T] = []

    def push(self, value: T) -> None:
        self._items.append(value)

    def pop(self) -> T | None:
        if not self._items:
            return None
        return self._items.pop()

    def peek(self) -> T | None:
        if not self._items:
            return None
        return self._items[-1]

    @property
    def size(self) -> int:
        return len(self._items)

Queues

History

A queue is first in, first out. Knuth treats the queue as a basic form of the linear list, not as one person’s invention. The ring in this section is the textbook way to keep both ends cheap inside an array. Schedulers, buffers, and breadth-first search are why the rule never went away. Edward F. Moore’s maze algorithm, in the graphs section, uses that rule for fewest-edges search. It is not a claim that Moore invented the queue.

Time complexity

Enqueue

O(1)

Dequeue

O(1)

Front

O(1)

Enqueue and dequeue are O(1) while the ring is not full. A growing queue resizes the way an array does, and the same amortized bound applies if capacity grows geometrically. The bugs are off-by-one around the wrap, confusing a full ring with an empty one when both would have head === tail unless you also store a length, and dequeuing from an empty queue.

Explanation

The honest picture of a fixed queue is a ring. head is the next slot to read. The next write lands at (head + length) mod capacity. When the read moves forward, the slot it left becomes available at the other end of the index arithmetic, not by sliding every element down to index 0.

Use a queue for work in arrival order, for producer-consumer buffers, and for breadth-first search. A linked list with a tail pointer is the other classic implementation. It never fills, and it pays a pointer per element. The ring pays spare slots and a fixed capacity, or a resize.

Diagram

Code

export class RingQueue<T> {
  private slots: (T | undefined)[];
  private head = 0;
  length = 0;

  constructor(readonly capacity: number) {
    this.slots = Array.from({ length: capacity }, () => undefined);
  }

  enqueue(value: T): number {
    if (this.length === this.capacity) throw new Error('queue is full');
    const index = (this.head + this.length) % this.capacity;
    this.slots[index] = value;
    this.length += 1;
    return index;
  }

  dequeue(): T | undefined {
    if (this.length === 0) return undefined;
    const value = this.slots[this.head];
    this.slots[this.head] = undefined;
    this.head = (this.head + 1) % this.capacity;
    this.length -= 1;
    return value;
  }
}

from typing import Generic, TypeVar

T = TypeVar("T")


class RingQueue(Generic[T]):
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self._slots: list[T | None] = [None] * capacity
        self._head = 0
        self.length = 0

    def enqueue(self, value: T) -> int:
        if self.length == self.capacity:
            raise RuntimeError("queue is full")
        index = (self._head + self.length) % self.capacity
        self._slots[index] = value
        self.length += 1
        return index

    def dequeue(self) -> T | None:
        if self.length == 0:
            return None
        value = self._slots[self._head]
        self._slots[self._head] = None
        self._head = (self._head + 1) % self.capacity
        self.length -= 1
        return value

Deques

History

A deque, pronounced deck, allows insertion and removal at both ends and still not in the middle. Knuth treats it as the double-ended form of the same linear list. There is no inventor to assign it to. The interesting part is the index arithmetic that lets the front step backward without sliding the block.

Time complexity

Push front or back

O(1)

Pop front or back

O(1)

Middle edit

Not the point

All four end operations are O(1) on a ring that is not full. The failure mode is the same wrap arithmetic as the queue, with one more direction in which to be wrong.

Explanation

The ring can grow backward. pushFront steps head one slot the other way and writes there. popBack reads the slot just before the logical end. The middle of the deque is still an array problem. pushBack and popFront are the queue operations from the previous section, on the same ring.

A deque is the right tool for a sliding window, for a work-stealing scheduler, and for an undo history that can also drop the oldest entry. It is the wrong tool for priority, and it is the wrong tool if you only needed a stack.

Diagram

Code

export class Deque<T> {
  private slots: (T | undefined)[];
  private head = 0;
  length = 0;

  constructor(readonly capacity: number) {
    this.slots = Array.from({ length: capacity }, () => undefined);
  }

  pushBack(value: T): number {
    if (this.length === this.capacity) throw new Error('deque is full');
    const index = (this.head + this.length) % this.capacity;
    this.slots[index] = value;
    this.length += 1;
    return index;
  }

  pushFront(value: T): number {
    if (this.length === this.capacity) throw new Error('deque is full');
    this.head = (this.head - 1 + this.capacity) % this.capacity;
    this.slots[this.head] = value;
    this.length += 1;
    return this.head;
  }

  popFront(): T | undefined {
    if (this.length === 0) return undefined;
    const value = this.slots[this.head];
    this.slots[this.head] = undefined;
    this.head = (this.head + 1) % this.capacity;
    this.length -= 1;
    return value;
  }

  popBack(): T | undefined {
    if (this.length === 0) return undefined;
    const index = (this.head + this.length - 1) % this.capacity;
    const value = this.slots[index];
    this.slots[index] = undefined;
    this.length -= 1;
    return value;
  }
}

from typing import Generic, TypeVar

T = TypeVar("T")


class Deque(Generic[T]):
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self._slots: list[T | None] = [None] * capacity
        self._head = 0
        self.length = 0

    def push_back(self, value: T) -> int:
        if self.length == self.capacity:
            raise RuntimeError("deque is full")
        index = (self._head + self.length) % self.capacity
        self._slots[index] = value
        self.length += 1
        return index

    def push_front(self, value: T) -> int:
        if self.length == self.capacity:
            raise RuntimeError("deque is full")
        self._head = (self._head - 1 + self.capacity) % self.capacity
        self._slots[self._head] = value
        self.length += 1
        return self._head

    def pop_front(self) -> T | None:
        if self.length == 0:
            return None
        value = self._slots[self._head]
        self._slots[self._head] = None
        self._head = (self._head + 1) % self.capacity
        self.length -= 1
        return value

    def pop_back(self) -> T | None:
        if self.length == 0:
            return None
        index = (self._head + self.length - 1) % self.capacity
        value = self._slots[index]
        self._slots[index] = None
        self.length -= 1
        return value

Hash tables

History

Knuth’s historical notes put the idea in H. P. Luhn’s IBM memorandum of January 1953, which already suggested chaining, and in independent work by Gene Amdahl and colleagues on the IBM 701, who used open addressing with linear probing. The first published description Knuth records is Arnold I. Dumey’s, in Computers and Automation, December 1956, including division by a prime. W. W. Peterson’s 1957 paper is the first extended published analysis of open addressing, including the damage deletion does if you are not careful. The diagram here is chaining, because the collision stays visible as a list. It is not Peterson’s layout.

Time complexity

Lookup

Expected O(1)

Insert

Expected O(1)

Delete

Expected O(1)

Worst case

O(n)

With a hash that spreads keys, and a load factor kept under a constant such as 3/4, lookup, insert, and delete are expected O(1). The worst case is O(n), when every key falls in one chain. A resize that doubles the table and rehashes is O(n) once, and amortized O(1) per insert if you grow geometrically. Space is O(n) entries plus the empty buckets you keep so that chains stay short.

Explanation

A hash table turns a key into a bucket number, then looks only in that bucket. If two keys produce the same number, they collide, and the bucket has to hold both. In this note the bucket is a chain: a short linked list. Another family, open addressing, stores the collision in a different slot of the same array and probes until it finds a gap.

The hash in the diagram is deliberately weak, so you can check it by hand. Sum the character codes, then take the remainder modulo the number of buckets. For the ASCII keys in the diagram, Python ord and JavaScript charCodeAt agree. A production hash mixes bits. This one is a teaching instrument.

Two keys can still collide after a resize. Doubling the table separates keys whose hash sums differ by a multiple of the old capacity but not of the new one. “in” and “me” differ by 5. They share a bucket when there are 5 buckets, and they split when there are 10. A pair that differs by 10 would not split. That is why the hash function matters more than the doubling.

The rehashing flag matters. resize calls set to reinsert old keys. Without the flag, set would see a half-moved table and try to resize again.

Use a hash table for dictionaries, caches, object records, and joining two collections by key. Do not use one when you need a worst-case bound. Knuth’s warning still holds: a hash can be excellent on average and terrible on the one input you did not try. Real-time code, and any code an attacker can feed keys to, should prefer a balanced tree or a keyed hash that the attacker cannot predict. Do not use one when the order of keys is part of the answer. JavaScript’s Map remembers insertion order. The language specification requires that order. It does not require a hash table, even though engines often use one underneath. If your algorithm depends on order, say so, and do not pretend it came from the hash.

Open addressing saves the chain pointers and punishes you at high load, and deletion needs a tombstone or a rebuild so that a later probe does not stop early. Chaining makes deletion a list splice and spends memory on nodes. Neither one gives you sorted order.

Diagram

Code

export function hashKey(key: string, capacity: number): number {
  let sum = 0;
  for (const char of key) sum += char.charCodeAt(0);
  return sum % capacity;
}

export class HashMap<V> {
  private buckets: { key: string; value: V }[][];
  private rehashing = false;
  size = 0;

  constructor(private capacity = 5) {
    this.buckets = Array.from({ length: capacity }, () => []);
  }

  set(key: string, value: V): void {
    if (!this.rehashing && (this.size + 1) / this.capacity > 0.75 && !this.has(key)) {
      this.resize(this.capacity * 2);
    }
    const bucket = hashKey(key, this.capacity);
    const chain = this.buckets[bucket] ?? [];
    const existing = chain.find((entry) => entry.key === key);
    if (existing) {
      existing.value = value;
      return;
    }
    chain.push({ key, value });
    this.buckets[bucket] = chain;
    this.size += 1;
  }

  has(key: string): boolean {
    const chain = this.buckets[hashKey(key, this.capacity)] ?? [];
    return chain.some((entry) => entry.key === key);
  }

  delete(key: string): boolean {
    const bucket = hashKey(key, this.capacity);
    const chain = this.buckets[bucket] ?? [];
    const index = chain.findIndex((entry) => entry.key === key);
    if (index === -1) return false;
    chain.splice(index, 1);
    this.size -= 1;
    return true;
  }

  private resize(nextCapacity: number): void {
    const previous = this.buckets;
    this.capacity = nextCapacity;
    this.buckets = Array.from({ length: nextCapacity }, () => []);
    this.size = 0;
    this.rehashing = true;
    try {
      for (const chain of previous) {
        for (const entry of chain) this.set(entry.key, entry.value);
      }
    } finally {
      this.rehashing = false;
    }
  }
}

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

V = TypeVar("V")


def hash_key(key: str, capacity: int) -> int:
    return sum(ord(char) for char in key) % capacity


@dataclass
class _Entry(Generic[V]):
    key: str
    value: V


class HashMap(Generic[V]):
    def __init__(self, capacity: int = 5) -> None:
        self._capacity = capacity
        self._buckets: list[list[_Entry[V]]] = [[] for _ in range(capacity)]
        self._rehashing = False
        self.size = 0

    def set(self, key: str, value: V) -> None:
        if (
            not self._rehashing
            and (self.size + 1) / self._capacity > 0.75
            and not self.has(key)
        ):
            self._resize(self._capacity * 2)
        bucket = hash_key(key, self._capacity)
        chain = self._buckets[bucket]
        for entry in chain:
            if entry.key == key:
                entry.value = value
                return
        chain.append(_Entry(key, value))
        self.size += 1

    def has(self, key: str) -> bool:
        chain = self._buckets[hash_key(key, self._capacity)]
        return any(entry.key == key for entry in chain)

    def delete(self, key: str) -> bool:
        bucket = hash_key(key, self._capacity)
        chain = self._buckets[bucket]
        for index, entry in enumerate(chain):
            if entry.key == key:
                del chain[index]
                self.size -= 1
                return True
        return False

    def _resize(self, next_capacity: int) -> None:
        previous = self._buckets
        self._capacity = next_capacity
        self._buckets = [[] for _ in range(next_capacity)]
        self.size = 0
        self._rehashing = True
        try:
            for chain in previous:
                for entry in chain:
                    self.set(entry.key, entry.value)
        finally:
            self._rehashing = False

Sets

History

A set, as a mathematical object, is much older than a hash table. The structure in this section is the programming one: a hash table whose only payload is presence. JavaScript’s Set, specified in ECMA-262 and described on MDN, adds a contract the mathematical set does not have. Iteration follows insertion order. The language does not require the implementation to be a hash table.

Time complexity

Membership

Expected O(1)

Insert

Expected O(1)

Delete

Expected O(1)

Worst case

O(n)

Membership, insertion, and deletion have the same expected and worst-case bounds as the table underneath. Space is O(n) elements. Adding an element that is already present does nothing, so a duplicate insert does not grow the set.

Explanation

A set answers a smaller question than a map. Not “what value is stored under this key?” but “is this element here?” The implementation in this note is a hash table whose payload is the fact of presence. A second copy would be a bug.

The usual mistakes are using a list and calling includes inside a loop, which turns an O(n) filter into an O(n²) filter, and assuming that iteration order is part of the set. In the structure above, it is not. JavaScript’s Set is the right tool in application code, and it is a different contract from the mathematical set and from the hash set drawn here. If you need order, the language set is giving you something extra, and you should notice that you are depending on it.

A bitset is the other classic set, for a universe of small integers. Element i is bit i. Membership is O(1) and very tight, and the universe has to be known and modest. A hash set is what you use when the elements are strings, objects, or a universe you cannot index.

Compared with a map, a set refuses to store a payload. Compared with an array, a set refuses duplicates and refuses a meaningful index. If you need both order and uniqueness, you are choosing two structures, or one structure with a stronger invariant, such as a balanced tree of keys.

Diagram

Code

The class below is the map from the previous section, with true as the only payload.

export class HashSet {
  private map = new HashMap<true>(5);

  /** Returns false when the element was already present. */
  add(key: string): boolean {
    if (this.map.has(key)) return false;
    this.map.set(key, true);
    return true;
  }

  has(key: string): boolean {
    return this.map.has(key);
  }
}

class HashSet:
    def __init__(self) -> None:
        self._map: HashMap[bool] = HashMap(5)

    def add(self, key: str) -> bool:
        """Returns false when the element was already present."""
        if self._map.has(key):
            return False
        self._map.set(key, True)
        return True

    def has(self, key: str) -> bool:
        return self._map.has(key)

Binary trees

History

The binary tree, as a shape, is older than the papers that analyze search trees and heaps. This note does not assign the shape to one author. What it fixes is the contract: at most two children, and no promise about the order of the labels. Inorder, left then the node then right, is the walk the diagram runs.

Time complexity

Traversal

O(n)

Find a value

O(n)

Recursion depth

O(h)

A traversal visits each node once and looks at each edge a constant number of times, so it is O(n). The recursion depth is the height. A skewed tree is a linked list, and the call stack is n frames. An explicit stack, the one from the stack section, removes that ceiling. Nothing in the shape tells you where a value lives. Finding one is O(n) unless you add an order and maintain it.

Explanation

A tree here is a connected shape with no cycles, drawn with a root at the top and children underneath. A binary tree allows at most two children. That limit is what makes an array layout possible for heaps, and what makes the left and right of a search tree mean something different. On the tree in the diagram the labels are only names, so the inorder walk is D, B, E, A, F, C. If the same shape were a search tree, that walk would come out sorted. Here it is only a route.

Diagram

Code

export interface BinNode {
  label: string;
  left: BinNode | null;
  right: BinNode | null;
}

/** Left, then the node, then right. Labels are names, not sort keys. */
export function walkInorder(root: BinNode | null, into: string[] = []): string[] {
  if (!root) return into;
  walkInorder(root.left, into);
  into.push(root.label);
  walkInorder(root.right, into);
  return into;
}

/** The tree drawn in the diagram. Inorder is D, B, E, A, F, C. */
export const sampleBinaryTree: BinNode = {
  label: 'A',
  left: {
    label: 'B',
    left: { label: 'D', left: null, right: null },
    right: { label: 'E', left: null, right: null },
  },
  right: {
    label: 'C',
    left: { label: 'F', left: null, right: null },
    right: null,
  },
};

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class BinNode:
    label: str
    left: BinNode | None = None
    right: BinNode | None = None


def walk_inorder(root: BinNode | None, into: list[str] | None = None) -> list[str]:
    """Left, then the node, then right. Labels are names, not sort keys."""
    if into is None:
        into = []
    if root is None:
        return into
    walk_inorder(root.left, into)
    into.append(root.label)
    walk_inorder(root.right, into)
    return into


# The tree drawn in the diagram. Inorder is D, B, E, A, F, C.
sample_binary_tree = BinNode(
    "A",
    left=BinNode(
        "B",
        left=BinNode("D"),
        right=BinNode("E"),
    ),
    right=BinNode("C", left=BinNode("F")),
)

Binary search trees

History

Hibbard’s 1962 paper in the Journal of the ACM is an early analysis of insertion and deletion in exactly these trees, including how a random insertion order behaves and how deletion can be done by replacing a node with a descendant. The structure was already in use. The paper is a place to see the costs written down, not a claim that no one had drawn a search tree before it.

Time complexity

Search

O(h)

Insert

O(h)

Delete

O(h)

Worst height

h = n

Search, insert, and delete are O(h). If keys arrive in random order, h is about log n. If they arrive sorted, the tree is a linked list and h is n. A red-black tree or an AVL tree does extra work on the way back up from an insertion so that h stays logarithmic in the worst case. That work is the difference between “a binary search tree” and “a balanced binary search tree.” The code below is the plain one. It will skew.

Explanation

Every node stores a key. Every key in the left subtree is smaller. Every key in the right subtree is larger. The diagram inserts 8, then 3, then 10, then 1, then 6, and refuses to invent a second home for a key that is already present.

Use a search tree when you need order: the next key, the previous key, a range, or a sorted iteration that stays sorted as keys come and go. Use a hash table when you only need equality lookup and you can tolerate a rare long chain. Deletion in a plain tree has a real case split. A node with two children is usually replaced by its inorder successor, and getting that pointer dance wrong corrupts the order silently. Balancing rotations have the same character. Test them. Do not trust a diagram you have not stepped through.

Diagram

Code

export interface TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

export function bstInsert(root: TreeNode | null, value: number): TreeNode {
  if (!root) return { value, left: null, right: null };
  if (value < root.value) root.left = bstInsert(root.left, value);
  else if (value > root.value) root.right = bstInsert(root.right, value);
  return root;
}

export function inorder(root: TreeNode | null, into: number[] = []): number[] {
  if (!root) return into;
  inorder(root.left, into);
  into.push(root.value);
  inorder(root.right, into);
  return into;
}

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class TreeNode:
    value: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def bst_insert(root: TreeNode | None, value: int) -> TreeNode:
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = bst_insert(root.left, value)
    elif value > root.value:
        root.right = bst_insert(root.right, value)
    return root


def inorder(root: TreeNode | None, into: list[int] | None = None) -> list[int]:
    if into is None:
        into = []
    if root is None:
        return into
    inorder(root.left, into)
    into.append(root.value)
    inorder(root.right, into)
    return into

Heaps

History

J. W. J. Williams published heapsort in Communications of the ACM in 1964. The same procedures add an element and extract the current minimum. He noted that they fit replacement selection, and any setting where new items arrive and you repeatedly need the smallest of those currently stored. That is a priority queue. This section shows the shape. The priority-queue section shows the jobs.

Time complexity

Peek minimum

O(1)

Insert

O(log n)

Extract minimum

O(log n)

Find arbitrary

O(n)

Seeing the minimum is O(1). Inserting sifts up, which is O(log n). Extracting sifts down, also O(log n). Building a heap from n unsorted values can be done in O(n), by sifting down from the middle of the array rather than inserting one at a time. Finding an arbitrary value is O(n). Space is n slots and no pointers. The array is the tree.

Explanation

A binary heap is a complete binary tree, packed into an array, with one extra rule. In a min-heap, every parent is less than or equal to its children. The minimum is therefore the root, at index 0. The children of index i are 2i + 1 and 2i + 2. The parent of index i is floor((i - 1) / 2). There is no promise about the order of siblings. A heap is not a search tree, and treating it like one is the common mistake.

The diagram shows 3 landing at the end before it sifts. That moment is real. It is the push before the loop. If you stop there, the array is not a heap.

A heap is the right backing store for a priority queue and for heapsort. It is the wrong store for “find this id” or “list these in sorted order” without extracting all of them. Extracting all of them is a sort, O(n log n), and it destroys the heap.

Diagram

Code

export function heapPush(heap: number[], value: number): void {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);
    if (heap[index]! >= heap[parent]!) break;
    [heap[index], heap[parent]] = [heap[parent]!, heap[index]!];
    index = parent;
  }
}

export function heapPop(heap: number[]): number | undefined {
  if (heap.length === 0) return undefined;
  const min = heap[0];
  const last = heap.pop();
  if (heap.length === 0 || last === undefined) return min;
  heap[0] = last;
  let index = 0;
  for (;;) {
    const left = index * 2 + 1;
    const right = left + 1;
    let smallest = index;
    if (left < heap.length && heap[left]! < heap[smallest]!) smallest = left;
    if (right < heap.length && heap[right]! < heap[smallest]!) smallest = right;
    if (smallest === index) break;
    [heap[index], heap[smallest]] = [heap[smallest]!, heap[index]!];
    index = smallest;
  }
  return min;
}

def heap_push(heap: list[int], value: int) -> None:
    heap.append(value)
    index = len(heap) - 1
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] >= heap[parent]:
            break
        heap[index], heap[parent] = heap[parent], heap[index]
        index = parent


def heap_pop(heap: list[int]) -> int | None:
    if not heap:
        return None
    minimum = heap[0]
    last = heap.pop()
    if not heap:
        return minimum
    heap[0] = last
    index = 0
    while True:
        left = index * 2 + 1
        right = left + 1
        smallest = index
        if left < len(heap) and heap[left] < heap[smallest]:
            smallest = left
        if right < len(heap) and heap[right] < heap[smallest]:
            smallest = right
        if smallest == index:
            break
        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest
    return minimum

Tries

History

Edward Fredkin described trie memory in Communications of the ACM in September 1960, for storing and retrieving argument-value pairs when the arguments have different lengths and often share pieces. He also recorded the cost: a trie can spend nodes on paths that a packed table would not.

Time complexity

Lookup

Expected O(L)

Insert

Expected O(L)

Delete

Expected O(L)

Lookup, insert, and delete are proportional to the length of the key, not to the logarithm of the number of keys. With a hash map from character to child, each step is expected O(1), so the whole operation is expected O(L). With a sorted array of children, each step costs a logarithm of the alphabet size. The diagram’s cost is the length of “cat” and “car”, which is why “car” only allocates the final r.

Explanation

A trie stores keys along a path. Each edge is a character. Words that share a prefix share those nodes. A missing end mark is the other half of the structure. The node for “ca” exists once “cat” does, but “ca” is not a stored word unless that node says the word ends. Forgetting the mark makes every prefix look like a key. Marking a node and also failing to share the prefix wastes the only advantage the trie had.

Tries earn their memory in autocomplete, routing tables, dictionaries, and spellers, anywhere the prefix is itself a question. A hash set of the whole word is smaller and simpler when you never ask about prefixes. A ternary search tree or a radix tree compresses the long chains of single children that a naive trie leaves behind.

Diagram

Code

export interface TrieNode {
  children: Map<string, TrieNode>;
  terminal: boolean;
}

export function trieInsert(root: TrieNode, word: string): void {
  let node = root;
  for (const char of word) {
    let child = node.children.get(char);
    if (!child) {
      child = { children: new Map(), terminal: false };
      node.children.set(char, child);
    }
    node = child;
  }
  node.terminal = true;
}

export function trieHas(root: TrieNode, word: string): boolean {
  let node = root;
  for (const char of word) {
    const child = node.children.get(char);
    if (!child) return false;
    node = child;
  }
  return node.terminal;
}

from __future__ import annotations

from dataclasses import dataclass, field


@dataclass
class TrieNode:
    children: dict[str, TrieNode] = field(default_factory=dict)
    terminal: bool = False


def trie_insert(root: TrieNode, word: str) -> None:
    node = root
    for char in word:
        child = node.children.get(char)
        if child is None:
            child = TrieNode()
            node.children[char] = child
        node = child
    node.terminal = True


def trie_has(root: TrieNode, word: str) -> bool:
    node = root
    for char in word:
        child = node.children.get(char)
        if child is None:
            return False
        node = child
    return node.terminal

Graphs

History

Searching a graph is older than electronic computers, in the specific form of walking a maze. Alexander Schrijver’s history of the shortest-path problem traces depth-first maze search to Trémaux, as described by Lucas in 1882. Breadth-first search, as an algorithm for the fewest edges from A to B, is Edward F. Moore’s algorithm A from “The shortest path through a maze,” presented in 1957 and published in 1959. Dijkstra’s 1959 paper solves the weighted version, where each edge has a non-negative length. Robert Tarjan’s 1972 paper is the one that made depth-first search a systematic way to compute things about a directed graph, including strongly connected components, in time linear in the vertices and edges.

Time complexity

List neighbors

O(degree)

Add an edge

O(1)

Remove an edge

O(degree)

BFS or DFS

O(V + E)

Both searches are O(V + E) with adjacency lists, if you mark seen vertices and the queue removes in O(1). With a matrix, scanning the neighbors of one vertex is O(V), so a search becomes O(V²). Array.prototype.shift and list.pop(0) are O(n). The samples below are the clear version. A ring queue keeps each removal O(1), which is what the O(V + E) bound assumes.

Explanation

A graph is a set of vertices and a set of edges. This section uses an undirected graph stored as adjacency lists: each vertex names its neighbors. An adjacency matrix instead uses a V by V table. Lists win when the graph is sparse, which most interesting graphs are. A matrix wins when the graph is dense or you need to test one edge in O(1) and you can afford V² memory.

The two diagrams use one graph. Neighbors, in list order: A goes to B then C. B goes to A, D, then E. C goes to A then E. D goes to B. E goes to B then C.

Breadth-first search uses a queue. A vertex is marked seen when it is queued, not when it is later removed. If you mark it only on removal, a dense graph will queue the same vertex many times. The order from A is A, B, C, D, E. On an unweighted graph, the first time BFS reaches a vertex it has used the fewest edges. That is the property DFS does not have.

Depth-first search uses a stack. The recursive version uses the call stack. From A, with the neighbor order above, the visit order is A, B, D, E, C. The search finishes D before it tries E, and it reaches C from E rather than from A, because A tried B first and the walk had not returned. Change the neighbor order and you change the diagram. The order is part of the algorithm as you wrote it, not an intrinsic labeling of the graph.

Forgetting the seen set turns a graph with a cycle into a search that does not terminate. Recursing on a long path can overflow the call stack. An explicit stack has the same order if you push neighbors in reverse, so the leftmost neighbor is popped first.

Use a graph when the data is relationships: links, dependencies, roads, citations. Do not reach for a graph library when the relationship is a tree you already have, or a sequence. BFS for fewest hops. Dijkstra, with a priority queue, for non-negative weights. Do not run Dijkstra with a negative edge and expect the same proof. DFS when you need a finishing time, a cycle check in a directed graph, or a topological order.

Diagram

Breadth-first search. The queue is drawn as the frontier.

Depth-first search. The same graph, walked with a stack.

Code

export function bfs(adj: Record<string, readonly string[]>, start: string): string[] {
  const seen = new Set<string>([start]);
  const queue = [start];
  const order: string[] = [];
  while (queue.length > 0) {
    const node = queue.shift();
    if (node === undefined) break;
    order.push(node);
    for (const next of adj[node] ?? []) {
      if (seen.has(next)) continue;
      seen.add(next);
      queue.push(next);
    }
  }
  return order;
}

export function dfs(adj: Record<string, readonly string[]>, start: string): string[] {
  const seen = new Set<string>();
  const order: string[] = [];
  const visit = (node: string): void => {
    if (seen.has(node)) return;
    seen.add(node);
    order.push(node);
    for (const next of adj[node] ?? []) visit(next);
  };
  visit(start);
  return order;
}

def bfs(adj: dict[str, list[str]], start: str) -> list[str]:
    seen = {start}
    queue = [start]
    order: list[str] = []
    while queue:
        node = queue.pop(0)
        order.append(node)
        for nxt in adj.get(node, ()):
            if nxt in seen:
                continue
            seen.add(nxt)
            queue.append(nxt)
    return order


def dfs(adj: dict[str, list[str]], start: str) -> list[str]:
    seen: set[str] = set()
    order: list[str] = []

    def visit(node: str) -> None:
        if node in seen:
            return
        seen.add(node)
        order.append(node)
        for nxt in adj.get(node, ()):
            visit(nxt)

    visit(start)
    return order

Priority queues

History

A priority queue is the abstract request: insert an item with a priority, and remove the item with the best priority. Arrival order is irrelevant. The usual concrete structure is the binary heap. Williams’s 1964 heap procedures are this interface. Dijkstra’s algorithm needs it, because the next vertex to settle is the one with the smallest tentative distance, not the one discovered first.

Time complexity

Peek minimum

O(1)

Insert

O(log n)

Extract minimum

O(log n)

Find an arbitrary job

O(n)

Insert and extract-min are O(log n). Peeking at the minimum is O(1). Extracting an arbitrary job, if you have not stored its index, is O(n). If priorities change while the job sits in the heap, you need a handle to its index and a sift from there. Forgetting to sift after a priority change leaves the root lying. Space is O(n), packed in an array.

Explanation

The diagram uses a min-heap of jobs. A smaller number runs first. Mail arrives before page, and page still leaves first.

A sorted array would make extract-min O(1) and insert O(n). A sorted check-in line is that trade. The heap is the other one, and it is the one schedulers use. A Fibonacci heap improves the theoretical cost of decrease-key. The binary heap is the one to implement first. The constant factors and the code size are why it remains the default.

Do not use a priority queue as a FIFO queue. Equal priorities do not, in this heap, preserve arrival order. If fairness among equals matters, store a sequence number in the comparison.

Diagram

Code

Extract uses the same sift as the heap. The comparison reads priority instead of the number.

export interface Job {
  name: string;
  priority: number;
}

export function jobPush(heap: Job[], job: Job): void {
  heap.push(job);
  let index = heap.length - 1;
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);
    if (heap[index]!.priority >= heap[parent]!.priority) break;
    [heap[index], heap[parent]] = [heap[parent]!, heap[index]!];
    index = parent;
  }
}

export function jobPop(heap: Job[]): Job | undefined {
  if (heap.length === 0) return undefined;
  const min = heap[0];
  const last = heap.pop();
  if (heap.length === 0 || last === undefined) return min;
  heap[0] = last;
  let index = 0;
  for (;;) {
    const left = index * 2 + 1;
    const right = left + 1;
    let smallest = index;
    if (left < heap.length && heap[left]!.priority < heap[smallest]!.priority) smallest = left;
    if (right < heap.length && heap[right]!.priority < heap[smallest]!.priority) smallest = right;
    if (smallest === index) break;
    [heap[index], heap[smallest]] = [heap[smallest]!, heap[index]!];
    index = smallest;
  }
  return min;
}

from dataclasses import dataclass


@dataclass
class Job:
    name: str
    priority: int


def job_push(heap: list[Job], job: Job) -> None:
    heap.append(job)
    index = len(heap) - 1
    while index > 0:
        parent = (index - 1) // 2
        if heap[index].priority >= heap[parent].priority:
            break
        heap[index], heap[parent] = heap[parent], heap[index]
        index = parent


def job_pop(heap: list[Job]) -> Job | None:
    if not heap:
        return None
    minimum = heap[0]
    last = heap.pop()
    if not heap:
        return minimum
    heap[0] = last
    index = 0
    while True:
        left = index * 2 + 1
        right = left + 1
        smallest = index
        if left < len(heap) and heap[left].priority < heap[smallest].priority:
            smallest = left
        if right < len(heap) and heap[right].priority < heap[smallest].priority:
            smallest = right
        if smallest == index:
            break
        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest
    return minimum

Disjoint sets

History

Bernard Galler and Michael Fischer published the tree method in Communications of the ACM in May 1964, from work presented in 1963. Their problem was storage assignment for EQUIVALENCE declarations in languages such as FORTRAN: decide which names must share an address. The algorithm builds a tree for each class and was not yet the modern combination of union by rank and path compression. Later writers treat that paper as the origin of the compressed-tree representation. The near-constant bound is Robert Tarjan’s, in the Journal of the ACM in 1975: linking by rank together with path compression handles a sequence of m operations on n elements in O(m α(n)) time, where α is the inverse of the Ackermann function. α of any n that fits in a machine is at most 4. “Almost O(1)” is the honest gloss, and it is amortized across the sequence, not a separate promise for one unlucky find.

Time complexity

Find

Amortized almost O(1)

Union

Amortized almost O(1)

Without the heuristics

O(n) find

Without either heuristic, repeated unions can build a chain, and a find is O(n). Union by rank attaches the shorter tree under the taller one, and rank is an upper bound on height, not a count of members. Path compression points every node on a found path directly at the root. The set does not change. The next walk is shorter. The bound above needs both rank and compression, and it is amortized across the whole sequence.

Explanation

Disjoint-set union, or union-find, maintains a partition of elements. Each element starts in a set alone. union merges the sets that contain two elements. find tells you which set an element is in, by returning a representative. It does not list the members. If that is the question you have, this structure is almost unfairly good at it.

The diagram’s last step is the rewrite from compression: 3 pointed at 2, 2 pointed at 0, and after find(3) both point at 0. find during union already compresses. That is why the picture after joining 1 and 3 is not a single neat comb. 3 was compressed toward 2 before 2 was linked under 0, so 3 still names 2 until something finds it again.

Use union-find for connectivity in an undirected graph as edges arrive, for Kruskal’s minimum spanning tree, for merging accounts, and for any “have these two things already been joined?” question. It is a poor fit if you need to list the members of a set, split a set, or handle deletions. Those operations want a different structure, often a graph or an explicit set per component. The implementation below also assumes element ids are a dense range of integers. A hash table from key to id is the usual adapter for anything else.

Diagram

Code

export class UnionFind {
  readonly parent: number[];
  readonly rank: number[];

  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, index) => index);
    this.rank = Array.from({ length: size }, () => 0);
  }

  find(node: number): number {
    const parent = this.parent[node];
    if (parent === undefined) throw new RangeError('node out of range');
    if (parent !== node) this.parent[node] = this.find(parent);
    return this.parent[node]!;
  }

  union(left: number, right: number): void {
    let rootLeft = this.find(left);
    let rootRight = this.find(right);
    if (rootLeft === rootRight) return;
    if (this.rank[rootLeft]! < this.rank[rootRight]!) {
      [rootLeft, rootRight] = [rootRight, rootLeft];
    }
    this.parent[rootRight] = rootLeft;
    if (this.rank[rootLeft] === this.rank[rootRight]) {
      this.rank[rootLeft] = this.rank[rootLeft]! + 1;
    }
  }
}

class UnionFind:
    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, node: int) -> int:
        if node < 0 or node >= len(self.parent):
            raise IndexError("node out of range")
        parent = self.parent[node]
        if parent != node:
            self.parent[node] = self.find(parent)
        return self.parent[node]

    def union(self, left: int, right: int) -> None:
        root_left = self.find(left)
        root_right = self.find(right)
        if root_left == root_right:
            return
        if self.rank[root_left] < self.rank[root_right]:
            root_left, root_right = root_right, root_left
        self.parent[root_right] = root_left
        if self.rank[root_left] == self.rank[root_right]:
            self.rank[root_left] += 1

Which structure should I use?

Start from the question the code asks most often. Then look at the bound you are not allowed to miss, not only the bound you hope for.

• The i-th item, or a tight scan, or growth at the end. A dynamic array.
• Splice at a place you already hold, and you rarely index. A linked list. Doubly linked if you must delete from the node itself.
• The most recent item, nesting, undo, or backtracking. A stack.
• The oldest item, or fewest hops on an unweighted graph. A queue, and BFS.
• Both ends, still not the middle. A deque.
• The value for this key, average case, no order. A hash table. If an adversary picks the keys, or you need a ceiling, a balanced tree.
• Whether this element is present. A hash set, or a bitset when the universe is small integers.
• The next key, the previous key, or a range. A balanced binary search tree.
• The smallest priority so far. A binary heap.
• Keys by prefix. A trie, unless a hash set of whole keys is enough.
• Relationships, paths, cycles, dependencies. A graph. Adjacency lists unless the graph is dense.
• Have these two items been merged? Union-find with rank and path compression.
• n is tiny, and it stays tiny. An array. The constant factors of a clever structure will not pay you back, and the code will be harder to read.

Two structures often appear together. A hash map from key to heap index is how a priority queue learns to decrease a key. An adjacency list is a vector of vectors. A queue inside BFS is the queue from this note. The layout decision is local. The program is a stack of them.

Glossary

Amortized

A bound on the average cost across a sequence of operations. One call in the sequence may cost more. Geometric growth of an array is the standard example.

Load factor

The number of stored keys divided by the number of buckets. This note resizes a chaining table when the next insert would push that ratio above 3/4.

Collision

Two keys hashing to the same bucket. Chaining stores both in a list. Open addressing stores the second key in another slot and keeps probing.

Height

The number of edges on the longest path from the root to a leaf. Search-tree costs follow the height, not the number of nodes, unless the tree is kept balanced.

Heap property

In a min-heap, each parent is less than or equal to its children. Siblings are unordered. The minimum is the root.

Complete binary tree

Every level is full except possibly the last, which is filled from the left. That shape is what lets a heap live in an array without holes.

Terminal

A trie node that marks the end of a stored key. A node can be a prefix of other keys and a word in its own right.

Adjacency list

For each vertex, a list of its neighbors. Space is proportional to vertices plus edges.

Representative

The root returned by find. Two elements are in the same set when their representatives are equal. The representative is not a list of the members.

Path compression

During find, point each visited node at the root. Later finds on that path are shorter. The partition does not change.

Rank

In this union-find, an upper bound on the height of a tree, used to decide which root hangs under which. It is not the number of elements.

Inverse Ackermann

A function that grows slower than any familiar logarithm. Tarjan’s bound for union by rank plus path compression is stated with it. For practical n it is a small constant.

What the bounds assume

The bounds in the table are for the RAM model used by the textbooks in the bibliography. An index computation, a pointer follow, a comparison, and an arithmetic step on a word-sized integer are constant time. The word is large enough to hold an index into the structure you built. Recursion is charged as time, and it also consumes stack frames that a machine will eventually refuse.

Hash bounds are expected bounds under a hash that behaves like a random function, or under a family of hashes from which you pick at random. They are not worst-case bounds. The demo hash in this note is not that function. It exists so the bucket arithmetic is visible.

“Amortized O(1)” for append and for hash insert requires geometric growth. Adding a constant number of slots each time does not qualify.

A plain binary search tree is O(h), and h is n in the worst case. Saying “lookup is logarithmic” without the word balanced is how that bound gets misremembered.

Graph search is O(V + E) for adjacency lists when each vertex is enqueued at most once. The BFS sample that removes from the front of an array does not meet that bound. The ring queue does.

Union-find is amortized across the whole sequence, and only with both rank and compression. Either heuristic alone is much better than a naive chain and is not the inverse-Ackermann result.

The samples are illustrative of those models. The TypeScript is runnable as a module, and the diagrams follow it. The Python is the same control flow. JavaScript’s built-in array, Map, and Set have extra contracts, especially order, and their engines are free to change representation as long as the language semantics hold. When the contract matters, this note names it.

The bibliography below is the source trail for the history and the bounds. Where a date belonged to an internal memorandum or to a priority dispute, the section cites the published account that records it, usually Knuth, instead of inventing a cleaner story.