Data structures — layout, invariant, cost

How each one works

• Array — one contiguous block: base + i·stride ⇒ O(1) index. Sequential scans ride the hardware prefetcher; a cache line (64 B x86, 128 B Apple silicon) brings 8–16 Ints per miss. Insert/delete in the middle shifts O(n). Swift grows geometrically (2×).
• Linked list — one heap allocation per node + next (and prev) pointers. Wins only for O(1) splice at a held node (LRU, free lists) and stable node addresses. Finding the node is O(n).
• Stack LIFO (calls, DFS, undo) · queue FIFO (BFS, scheduling) · deque both ends O(1) (sliding window, work stealing). Array queue with removeFirst() is O(n) per dequeue → ring buffer (head index) or two stacks.
• Hash table — hash(key) mod m → bucket. Load α= n/m. Chaining: bucket = list/tree, tolerates α>1, pointer-heavy. Open addressing: entries inline, probe on collision (linear/quadratic/double), cache-friendly, needs α<1 and tombstones. Resize = rehash every entry, O(n) once.
• BST — left < node < right; all ops O(h). Sorted inserts make a list: h = n. AVL: subtree heights differ ≤1, h ≤ 1.44 log n → faster reads, more rotations. Red-black: no red–red, equal black height, h ≤ 2 log(n+1), ≤2 rotations per insert, ≤3 per delete → cheaper writes (std::map, Java TreeMap). Disk/DB: B-tree, fan-out ∼100s, one node = one page.
• Binary heap — complete tree in an array, parent ≤ children. peek O(1), push = append + sift-up O(log n), pop = move last to root + sift-down O(log n), heapify O(n). Priority queues, Dijkstra, top-k.
• Trie — node per prefix, children by character, isEnd flag. O(L) per op, independent of key count; prefix queries a hash set can’t do.
• Graph — adjacency list O(V+E) space, neighbours in O(deg): sparse graphs (almost all). Matrix V×V bits/weights, O(1) “edge u–v?”: dense graphs, Floyd–Warshall.
• Union-find — parent array + path compression + union by rank → O(α(n)) ≈ O(1): components, Kruskal.

Example — a queue that is really O(1)

struct Queue<T> {               // amortised O(1), no Deque needed
  private var items: [T?] = []; private var head = 0
  mutating func enqueue(_ x: T) { items.append(x) }
  mutating func dequeue() -> T? {
    guard head < items.count, let x = items[head] else { return nil }
    items[head] = nil; head += 1           // O(1): no shifting
    if head > 64 && head * 2 > items.count {   // compact now and then
      items.removeFirst(head); head = 0 }
    return x }
}

Picture — one graph, two layouts

Big-O — average (worst)

Swift mapping

Interview traps

• “Linked lists insert faster” — only once you hold the node; the O(n) walk and cache misses usually lose to Array’s memmove.
• Hash O(1) is average, amortised: O(n) on collisions/flooding, one insert can rehash O(n), and hashing a long string is O(length).
• A heap is not sorted: no binary search, in-order isn’t ordered, “contains” is O(n).
• Dictionary order and hashValue change per launch (seeded hasher) — never persist them or assert on them in a test.
• Swift class list: a 1M-node chain frees recursively on deinit → stack overflow; unlink iteratively. Make prev weak/unowned or a doubly linked list is a retain cycle.
• Amortised ≠ worst case: a resize inside a 16 ms frame or audio callback still hitches — pre-size or use a fixed ring buffer.
• String is not Int-indexable (grapheme clusters) — Array(s) once if you need random access.

Remember

Layout decides speed, invariant decides big-O. Contiguous by default; pointers only when you must splice.

Likely questions

1. Why is append amortised O(1)? — doubling: total copies <2n.
2. Chaining vs open addressing? — pointers & α>1 vs inline & probing.
3. AVL or red-black? — reads vs writes; RB rotates less.
4. Heapify cost? — O(n): most nodes are near the leaves.
5. Sparse graph storage? — adjacency list, O(V+E).
6. Ordered map in Swift? — none built in: sorted keys + binary search, or a tree.
7. Why is a DB index a B-tree, not a BST? — fan-out: few page reads per lookup.