The Ultimate Data Structures Cheat Sheet

Scenario context

Data structures are tools. Picking the right one depends on what operation you do most: lookup, insert, delete, ordered traversal, top-k, prefix search, or graph navigation. Start from operation frequency, not from habit.

A senior engineer traced a 400ms latency spike on Airbnb's search service to a single line of code: a membership check against a Python list. The service was calling if item in results in…

This walkthrough focuses on Why Structure Choice Beats Algorithm Cleverness.

Before making a design choice, clarify:

• A senior engineer traced a 400ms latency spike on Airbnb's search service to a single line of code: a membership check against a Python list .
• The service was calling if item in results inside a hot path, and with tens of thousands of items, each check was O(n) — scanning every element in the list.
• Replacing the list with a set dropped the check to O(1) and cut latency by 400ms overnight.

Concepts in play: tree-data-structures, sorting-and-searching-algorithms, stack-and-queue-data-structures, database-indexing

Stage 1 — Big-O Reference: The Foundation of Every Choice

• 📊 Operation Cost Groupings: O(1), O(log N), and O(N) This diagram groups common data structure operations into three cost tiers — O(1), O(log N), and O(N) — making it easy to see which tier a given operation belongs to.
• The O(1) group holds array index access, HashMap get, and stack push/pop; the O(log N) group holds BST search, binary search, and heap insert; and the O(N) group holds linear array search, linked list traversal, and ful…
• When evaluating a structure for a hot-path operation, identify its tier here first — a single tier crossing (from O(log N) to O(N) under high call frequency) is typically the root cause of performance regressions.

flowchart LR
    subgraph O1
        A[Array Access]
        B[HashMap Get]
        C[Stack Push/Pop]
    end
    subgraph OlogN
        D[BST Search]
        E[Binary Search]
        F[Heap Insert]
    end
    subgraph ON
        G[Array Search]
        H[Linked List]
        I[Tree Traversal]
    end

Observable outcome: When evaluating a structure for a hot-path operation, identify its tier here first — a single tier crossing (from O(log N) to O(N) under high call frequency) is typically the root cause of performance regressions.

Stage 2 — The Structure-Selection Workflow

• Follow this process before picking any data structure: The four questions to ask: 1.
• What do I do most: read, write, search, sort, or traverse?
• Do I need ordering guarantees?
• Is access by index, key, prefix, or relationship?

flowchart TD
    A[Define Problem] --> B[List Critical Operations]
    B --> C[Estimate Operation Frequency]
    C --> D[Shortlist Candidate Structures]
    D --> E[Check Constraints: ordering, memory, concurrency]
    E --> F[Prototype with sample workload]
    F --> G[Choose and document trade-offs]

Observable outcome: Is access by index, key, prefix, or relationship?

Stage 3 — Deep Dive: How Hash Maps Handle Collisions

• A hash map converts each key to a bucket index via a hash function.
• When two keys hash to the same bucket — a collision — most implementations use separate chaining (a linked list per bucket) or open addressing (probe to the next empty slot).
• Performance degrades as the load factor (entries ÷ buckets) rises; most implementations rehash at ~0.75, copying all entries into a larger array.

Observable outcome: Performance degrades as the load factor (entries ÷ buckets) rises; most implementations rehash at ~0.75, copying all entries into a larger array.

Stage 4 — Hidden Costs Beginners Miss

• The Big-O table shows asymptotic behavior — but real performance includes constant factors, cache misses, and allocation overhead.

# Pre-size a dict to avoid rehash pauses
from sys import getsizeof
d = {}
d.update({i: i for i in range(10_000)})  # triggers multiple rehashes

# Better: pre-size if you know the approximate count
d = dict.fromkeys(range(10_000))         # allocates once

Observable outcome: The Big-O table shows asymptotic behavior — but real performance includes constant factors, cache misses, and allocation overhead.

Stage 5 — What to Learn Next

• • Mastering Binary Tree Traversal - Tree Data Structure Explained - System Design Core Concepts

Observable outcome: - Mastering Binary Tree Traversal - Tree Data Structure Explained - System Design Core Concepts

Stage 6 — Spot the Wrong Structure

• The most common cause of sluggish code is not a bad algorithm — it is a mismatched data structure.
• Here are four high-frequency selection mistakes and the fix for each.
• Before-and-after gut check: if you find yourself scanning a list inside a hot loop just to test membership, that list should be a set.
• If you are sorting a collection just to peek at the smallest element, that collection should be a heap.

Observable outcome: If you are sorting a collection just to peek at the smallest element, that collection should be a heap.

End-to-end outcome

A senior engineer traced a 400ms latency spike on Airbnb's search service to a single line of code: a membership check against a Python list .

Alternatives considered

Linear vs. Non-Linear: How Data Shapes Access Patterns

Every data structure belongs to one of two broad families, and recognising which family you are in is the first filter before consulting any Big-O table.

Decision Guide: Structure Decision Guide at a Glance

Decision Guide: Structure Decision Guide at a Glance

Failure and degraded modes

Trade-offs & Failure Modes: Production Constraints That Override Big-O

• Detection: Measure p95/p99 latency, not just average.
• User or operator impact: Measure p95/p99 latency, not just average.