RavnaryA Knowledge Platform
Colour theme
RavnaryA Knowledge Platform

Cheatsheet

Data Structures

Every data structure in the subject on one page: what each one is for, what its operations cost, and how to choose.

ravnary.com/cheatsheets/data-structures

  • 14 entries
  • 4 groups
FromData Structures
Share

Scope

The structures the subject builds, and the LRU cache built from two of them; Big O, complexity and recursion appear only as costs and mistakes.

The rule

Sequences keep items in a line; stacks, queues and heaps decide which item comes out next; lookup structures find by key; graph structures record joins.

Choosing

11 choices

  1. When Things are joined in pairs and you ask what each one is joined to

    , choose

    Adjacency List

  2. When You merge groups and ask whether two items share one, and never split a group

    , choose

    Union-Find

  3. When Keys are strings and you ask prefix questions

    , choose

    Trie

  4. When You keep a fixed number of recent results and drop the least recently used

    , choose

    LRU Cache

  5. When The item added last must leave first

    , choose

    Stack

  6. When The item that has waited longest must leave first

    , choose

    Queue

  7. When You repeatedly remove the smallest or largest item while new items arrive

    , choose

    Heap

  8. When You ask ordered questions, such as the next key or a range, while keys change

    , choose

    Binary Search Tree

  9. When You look up, add or remove by key, and order does not matter

    , choose

    Hash Table

  10. When You insert or remove in the middle at a node you hold, or at both ends

    , choose

    Doubly Linked List

  11. When You read by position, append at the end and scan in order

    , choose

    Dynamic Array

Sequences

3 entries

Keep items in a line, each cheap to change at a different place.

  • Dynamic Array

    Keeps items side by side, doubling its block when full.

    Use when

    You read by position, append at the end, or scan in order.

    Facts

    Read by position
    O(1)
    worst case
    Append
    O(1)
    amortised; a growing one is O(n)
    Insert at index i
    O(n)
    worst case, at the front

    Watch for

    Judging append by the one call that copies every element.

    Judging Append by Its Slowest Call

  • Linked List

    Chains nodes, each holding a reference to the next.

    Use when

    You add and remove at the front, or insert after a node you already hold.

    Facts

    Insert at front
    O(1)
    worst case
    Append
    O(1)
    worst case, with a tail
    Read at position i
    O(n)
    worst case

    Watch for

    Deleting the last node and leaving the tail pointing at it.

    Forgetting to Update the Tail

  • Doubly Linked List

    Links each node to the node before it and the one after.

    Use when

    You remove a node you already hold, or add and remove at both ends.

    Facts

    Delete a held node
    O(1)
    worst case
    Delete last
    O(1)
    worst case, with a tail
    Search
    O(n)
    worst case

    Watch for

    Expecting the back reference to speed up search; finding a value still walks the list.

Stacks, queues and heaps

4 entries

Decide which item comes out next: the newest, the oldest, or the one with the highest priority.

  • Stack

    Hands back the item added most recently: last in, first out.

    Use when

    The item added last must leave first.

    Facts

    Push, pop, peek
    O(1)
    amortised on an array
    Empty check
    O(1)
    worst case

    Watch for

    Popping an empty stack, which throws in Python and Java and returns undefined in TypeScript.

  • Queue

    Hands back the item that has waited longest: first in, first out.

    Use when

    The item that has waited longest must leave first.

    Facts

    Enqueue, dequeue
    O(1)
    worst case, list or ring
    Dequeue
    O(n)
    every case, plain array

    Watch for

    Dequeuing from the front of a plain array, which shifts every other item.

    Dequeuing From the Front of an Array

  • Ring Buffer

    Runs a queue in a fixed array that wraps round to slot 0.

    Use when

    The queue has a known maximum length, or the oldest items may be overwritten.

    Facts

    Every operation
    O(1)
    worst case
    Capacity
    Fixed
    when full, refuse or overwrite

    Watch for

    Head equals tail both when full and when empty, so keep a count.

  • Heap

    Keeps the top priority item at the root of an array tree.

    Use when

    You repeatedly remove the smallest or largest item while new items arrive.

    Facts

    Peek
    O(1)
    worst case
    Push, pop
    O(log n)
    worst case
    Build from n items
    O(n)
    worst case, bottom-up

    Watch for

    Building with n pushes, O(n log n), when building bottom-up is O(n).

    Building a Heap With n Pushes

Lookup by key

4 entries

Find an item by its key; the hash table keeps no order, and the others each keep one.

  • Hash Table

    Turns each key into a slot number, and keeps no order.

    Use when

    You look up, add or remove by key, and order does not matter.

    Facts

    Look up, delete
    O(1)
    expected
    Insert
    O(1)
    amortised, expected
    Look up
    O(n)
    worst case, one bucket

    Watch for

    A key that changes after insertion, or compares by identity.

    A Key Whose Hash or Equality Can Change

  • Binary Search Tree

    Keeps smaller keys left of each node and larger right.

    Use when

    You ask ordered questions, such as the next key or a range, while keys change.

    Facts

    Search, insert, delete
    O(log n)
    average
    Search, insert, delete
    O(n)
    worst case, sorted input
    In-order visit
    O(n)
    every case

    Watch for

    Checking each node only against its children, not against its whole subtree.

    Checking Only Each Node's Children

  • Trie

    Stores words one node per letter, sharing prefixes.

    Use when

    Keys are strings and you ask prefix questions, such as every word that starts with ca.

    Facts

    Insert, search
    O(L)
    worst case, L letters
    List by prefix
    O(L + m)
    worst case, m nodes below

    Watch for

    Leaving out the end-of-word mark, so every prefix looks like a stored word.

    A Trie Without an End-of-Word Mark

  • LRU Cache

    Keeps recent results, dropping the least recently used.

    Use when

    You keep a fixed number of recent results and drop the one unused for longest.

    Facts

    Get, evict
    O(1)
    expected
    Built from
    Map and list
    hash map, doubly linked list

    Watch for

    Updating one structure and not the other.

    Updating One Structure but Not Its Partner

Graphs and groups

3 entries

Record which items are joined, each answering a different question fastest.

  • Adjacency List

    Keeps, for each vertex, a list of the vertices it is joined to.

    Use when

    The graph is sparse, or you mostly ask what each vertex is joined to.

    Facts

    Memory
    O(V + E)
    any graph
    Neighbours of v
    O(degree of v)
    worst case
    Edge check
    O(degree of u)
    worst case

    Watch for

    Storing an undirected edge under only one of its two ends.

    Storing an Undirected Edge Only Once

  • Adjacency Matrix

    Keeps a V by V grid with one cell for every pair of vertices.

    Use when

    The graph is dense, or you mostly ask whether two given vertices are joined.

    Facts

    Edge check
    O(1)
    any pair
    Neighbours
    O(V)
    every case
    Memory
    O(V²)
    any graph

    Watch for

    A sparse graph still takes V² cells: a thousand vertices take a million cells.

  • Union-Find

    Tracks groups that merge but never split.

    Use when

    You merge groups and ask whether two items share one, and never split a group.

    Facts

    find, union
    O(α(n))
    amortised, rank and compression
    find, union
    O(n)
    worst case, unoptimised
    Memory
    O(n)
    every case

    Watch for

    Linking the named nodes instead of their roots, which splits a group.

    Linking the Nodes Instead of Their Roots

Common mistakes

5 mistakes

  1. Reading Big O as the worst case, when a best case has a Big O too.

    Reading Big O as the Worst Case

  2. Calling every pair of nested loops quadratic, whatever the inner loop does.

    Calling Every Pair of Nested Loops O(n²)

  3. Counting a slice, a membership test with in, or a string grown in a loop as one step.

    A Linear Cost Hidden Inside a Built-In Call

  4. Choosing a structure out of habit, instead of from the operations the program performs.

    Choosing a Structure Out of Habit

  5. Expecting Python's heapq to pop the largest item; it always pops the smallest, so negate the keys.

    Treating Python's heapq as a Max-Heap

Learn it

10 topics