Data Structures cheat sheet

A scannable Data Structures reference: 13 short snippets across 7 topics, each linking back to the lesson it came from.

At a glance

Quick snippets

Amortised analysis: what operations really cost

Why doubling makes append constant

# geometric growth: capacity doubles
# appends   1..8, cost of the copy
# push 1  -> allocate 1, copy 0
# push 2  -> allocate 2, copy 1
# push 3  -> allocate 4, copy 2
# push 5  -> allocate 8, copy 4
# push 9  -> allocate 16, copy 8

total copy cost after n pushes = n-1 (a geometric series)
amortised cost per push = O(1)

Big-O hides the constant, and the constant is often the answer

// Two ways to sum an array.
// A: sequential — one cache line per 16 ints
for (int i = 0; i < n; i++) sum += a[i];

// B: strided — a new cache line for almost every element
for (int i = 0; i < n; i += 16) sum += a[i];

// Same O(n). B can be several times slower in wall-clock time.

Full lesson: Amortised analysis: what operations really cost →

Sets, maps and the abstract data type view

Ordered or not — the decision that changes everything

from collections import OrderedDict

d = {"b": 2, "a": 1}          # dict preserves insertion order (3.7+)
sorted_items = sorted(d.items())        # explicit sort when you need key order

# Python's dict is insertion-ordered; many languages' maps are not.
# Rust:      HashMap unordered, BTreeMap ordered
# Java:      HashMap unordered, LinkedHashMap insertion, TreeMap sorted
# JavaScript: Map insertion-ordered, plain object mostly so

Ordered or not — the decision that changes everything

Map<String, Integer> hash  = new HashMap<>();      // O(1) expected, no order
Map<String, Integer> ins   = new LinkedHashMap<>(); // insertion order
Map<String, Integer> sorted = new TreeMap<>();      // sorted by key, O(log n)

// range queries only exist on the sorted implementation
SortedMap<String, Integer> tail = ((TreeMap<String, Integer>) sorted).tailMap("m");

Sets, and the cost of what they promise

seen = set()
for row in stream:
    key = (row["tenant"], row["id"])
    if key in seen:              # O(1) expected
        continue
    seen.add(key)

Full lesson: Sets, maps and the abstract data type view →

Heaps and priority queues

A tree stored in an array

index:   0   1   2   3   4   5   6
value:  [1,  3,  2,  7,  4,  5,  9]

            1
          /   \
         3     2
        / \   / \
       7   4 5   9

parent(i) = (i - 1) / 2
left(i)   = 2i + 1
right(i)  = 2i + 2

Top-k and scheduling

# Top-k: keep a bounded min-heap of size k
def top_k(stream, k):
    heap = []
    for score, item in stream:
        if len(heap) < k:
            heapq.heappush(heap, (score, item))
        elif score > heap[0][0]:
            heapq.heapreplace(heap, (score, item))   # pop + push in one step
    return sorted(heap, reverse=True)

Full lesson: Heaps and priority queues →

Balanced trees: AVL, red-black and B-trees

Balance is the difference between O(log n) and O(n)

insert 1,2,3,4,5 in order

1                3
 \              / \
  2            2   4
   \            \   \
    3            1   5
     \
      4            balanced
       \
        5        height log2(5) ~ 3
         height 5

Full lesson: Balanced trees: AVL, red-black and B-trees →

Tries and prefix trees

The memory bill

# collect all completions under a prefix
def completions(node, prefix, out, limit=10):
    if len(out) >= limit:
        return
    if node.is_word:
        out.append(prefix)
    for ch, child in sorted(node.children.items()):
        completions(child, prefix + ch, out, limit)
        if len(out) >= limit:
            return

Full lesson: Tries and prefix trees →

Union-Find and disjoint sets

Why it is effectively constant

# counting groups after a series of unions
groups = len({find(i) for i in range(n)})

# largest component size
from collections import Counter
sizes = Counter(find(i) for i in range(n))
largest = max(sizes.values())

What you build with it

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])       # by weight
    return [e for e in edges if union(e[0], e[1])]

Full lesson: Union-Find and disjoint sets →

Probabilistic structures: Bloom filters and skip lists

Counting and the alternatives

# typical use: skip a disk lookup for keys that definitely do not exist
# query path
if key not in bloom:        # definitely absent — never a false negative
    return None
value = store.get(key)      # maybe present; false positives land here

Skip lists: expected O(log n) without rotations

level 2:  1 ----------------------> 9
level 1:  1 -------> 4 -----------> 9
level 0:  1 -> 2 -> 4 -> 6 -> 7 -> 9

search 7: level 2 -> 9 is too far, drop
          level 1 -> 4, then 9 is too far, drop
          level 0 -> 6 -> 7 found

Full lesson: Probabilistic structures: Bloom filters and skip lists →

FAQ

Related cheat sheets

Algorithms Computer Networks Operating Systems Character Encodings Hashing & Checksums Data Formats

Last refreshed 2026-09-27.