📊 Data Structures Cheatsheet

Know your tools before you build. This is your Big O reference for coding interviews.

The Big Picture

🎯 Quick Reference Card

Structure	Access	Search	Insert	Delete	Space	Best For
Array	O(1)	O(n)	O(n)	O(n)	O(n)	Random access
Linked List	O(n)	O(n)	O(1)*	O(1)*	O(n)	Frequent insert/delete
Stack	O(n)	O(n)	O(1)	O(1)	O(n)	LIFO, backtracking
Queue	O(n)	O(n)	O(1)	O(1)	O(n)	FIFO, BFS
HashMap	-	O(1)*	O(1)*	O(1)*	O(n)	Key-value lookup
HashSet	-	O(1)*	O(1)*	O(1)*	O(n)	Unique elements
BST	O(log n)*	O(log n)*	O(log n)*	O(log n)*	O(n)	Sorted data
Heap	O(1) top	O(n)	O(log n)	O(log n)	O(n)	Priority queue
Trie	-	O(k)	O(k)	O(k)	O(n×k)	Prefix search

* = average case, assuming balanced/good hash

1. Arrays

The workhorse of coding interviews.

┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │  ← Contiguous memory
└───┴───┴───┴───┴───┘
  0   1   2   3   4    ← Index (O(1) access)

Operations:

# Access: O(1)
arr[i]

# Insert at end: O(1) amortized (dynamic array)
arr.append(x)

# Insert at index: O(n) - shift elements
arr.insert(i, x)

# Delete: O(n) - shift elements
arr.pop(i)

# Search: O(n) unsorted, O(log n) sorted

Interview Pattern

Sorted array? → Think Binary Search or Two Pointers

---

2. Linked Lists

Pointers all the way down.

┌───┬───┐    ┌───┬───┐    ┌───┬───┐
│ 1 │ ●─┼───►│ 2 │ ●─┼───►│ 3 │ ∅ │
└───┴───┘    └───┴───┘    └───┴───┘
head                        tail

Types:

• Singly Linked: Forward only
• Doubly Linked: Forward + backward
• Circular: Tail points to head

Operations:

# Access: O(n) - must traverse
# Insert at head: O(1)
# Insert at tail: O(1) if tail pointer, else O(n)
# Delete: O(1) if at node, O(n) to find

Interview Patterns:

• Two pointers (fast/slow) for cycle detection
• Dummy head for easier edge cases
• Reverse is VERY common

---

3. Stack

LIFO - Last In, First Out (like a stack of plates)

     ┌───┐
     │ 3 │ ← top (pop/push here)
     ├───┤
     │ 2 │
     ├───┤
     │ 1 │
     └───┘

Operations (all O(1)):

stack.push(x)   # Add to top
stack.pop()     # Remove from top
stack.peek()    # View top
stack.isEmpty() # Check empty

Interview Patterns:

Pattern	Example Problems
Matching pairs	Valid Parentheses
Monotonic stack	Next Greater Element
Backtracking	DFS path
Undo mechanism	Calculator

Interview Pattern

See nested structures or matching pairs? → Think Stack

---

4. Queue

FIFO - First In, First Out (like a checkout line)

     front              back
       ↓                  ↓
     ┌───┬───┬───┬───┬───┐
     │ 1 │ 2 │ 3 │ 4 │ 5 │
     └───┴───┴───┴───┴───┘
       ↑                  ↑
    dequeue           enqueue

Operations (all O(1)):

queue.enqueue(x)  # Add to back
queue.dequeue()   # Remove from front
queue.peek()      # View front

Variants:

• Deque: Double-ended (insert/remove both ends)
• Priority Queue: By priority (see Heap)

Interview Patterns:

Pattern	Example Problems
BFS	Level order, shortest path
Sliding window	Max in window
Task scheduling	Task Scheduler

---

5. HashMap / HashSet

O(1) lookup magic.

Key: "apple"  →  hash("apple") % size  →  Index: 3
                                              ↓
                    ┌───┬───┬───┬───┬───┐
                    │   │   │   │ 🍎│   │
                    └───┴───┴───┴───┴───┘
                      0   1   2   3   4

HashMap Operations (average O(1)):

map[key] = value   # Insert/Update
map[key]           # Access
del map[key]       # Delete
key in map         # Search

HashSet: HashMap but only keys (no values)

Collision Handling:

• Chaining: Linked list at each bucket
• Open Addressing: Find next empty slot

Interview Patterns:

Pattern	Example Problems
Two Sum style	Two Sum, Subarray Sum
Frequency count	Valid Anagram, Top K
Seen/visited	Contains Duplicate
Group by key	Group Anagrams

Interview Pattern

Need O(1) lookup or counting frequency? → Think HashMap

---

6. Binary Search Tree (BST)

Sorted structure with O(log n) operations.

        8          ← Root
       / \
      3   10       ← Left < Parent < Right
     / \    \
    1   6    14
       / \   /
      4   7 13

Properties:

• Left subtree < Node < Right subtree
• In-order traversal = sorted

Operations (balanced):

# Search: O(log n)
# Insert: O(log n)
# Delete: O(log n)
# Min/Max: O(log n) - go left/right

Interview Patterns:

Pattern	Example Problems
Validate BST	In-order check
LCA	Lowest Common Ancestor
Kth smallest	In-order with count

Watch Out

Unbalanced BST degrades to O(n). That's why we have AVL, Red-Black trees.

---

7. Heap / Priority Queue

Get min/max in O(1), insert in O(log n).

Min-Heap:
           1           ← Min at root
         /   \
        2     3
       / \   /
      4   5 6

Array: [1, 2, 3, 4, 5, 6]
       Parent of i: (i-1)/2
       Children: 2i+1, 2i+2

Operations:

heappush(heap, x)  # Insert: O(log n)
heappop(heap)      # Extract min: O(log n)
heap[0]            # Peek min: O(1)
heapify(arr)       # Build heap: O(n)

Interview Patterns:

Pattern	Example Problems
Top K	Kth Largest, Top K Frequent
Merge K	Merge K Sorted Lists
Stream median	Running Median
Task scheduling	Meeting Rooms II

Interview Pattern

See "K largest" or "K smallest"? → Think Heap

---

8. Trie (Prefix Tree)

For string prefix operations.

         root
        / | \
       a  b  c
      /    \
     p      a
    / \      \
   p   e      t
  /     \
 l       n
 e

Operations (k = word length):

# Insert: O(k)
# Search: O(k)
# StartsWith: O(k)

Interview Patterns:

• Autocomplete
• Word search
• Prefix matching

---

9. Graph

Nodes + edges.

Adjacency List:           Adjacency Matrix:
1 → [2, 3]                    1  2  3  4
2 → [4]                    1 [0, 1, 1, 0]
3 → [4]                    2 [0, 0, 0, 1]
4 → []                     3 [0, 0, 0, 1]
                           4 [0, 0, 0, 0]

Representation	Space	Edge Check	Neighbors
Adjacency List	O(V+E)	O(degree)	O(degree)
Adjacency Matrix	O(V²)	O(1)	O(V)

Use List: Sparse graphs (most cases) Use Matrix: Dense graphs, need fast edge check

Interview Patterns:

Pattern	Algorithm
Traversal	BFS, DFS
Shortest path	BFS (unweighted), Dijkstra
Cycle detection	DFS with colors
Connected components	Union-Find, DFS
Topological sort	Kahn's, DFS

---

When to Use What?

Memory Tricks 🧠

Structure	Mnemonic
Stack	Pancakes - last one on top, first one eaten
Queue	Movie line - first person in line, first served
Heap	Tournament - winner bubbles to top
BST	Phonebook - split in half each lookup
HashMap	Library card catalog - instant lookup by ID
Trie	Autocomplete dropdown - share prefixes

---

---

Next: Big O Notation → - Understand time and space complexity.