Data Structures: Quick Notes#
Complexity summary (typical)#
Many structures have good average performance but bad worst-case. Interviews often want both.
| Data Structure | Access | Search | Insert | Delete | Space | Notes |
|---|---|---|---|---|---|---|
| Array | O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
insert/delete in middle shifts |
| Dynamic Array (vector/list) | O(1) |
O(n) |
amort. O(1) append |
O(n) |
O(n) |
occasional resize |
| Stack | top O(1) |
O(n) |
O(1) |
O(1) |
O(n) |
LIFO |
| Queue / Deque | front/back O(1) |
O(n) |
O(1) |
O(1) |
O(n) |
FIFO / double-ended |
| Singly Linked List | O(n) |
O(n) |
O(1)* |
O(1)* |
O(n) |
*if pointer to node/prev is known |
| Doubly Linked List | O(n) |
O(n) |
O(1)* |
O(1)* |
O(n) |
easy delete given node |
| Hash Table / Hash Map | N/A | avg O(1), worst O(n) |
avg O(1), worst O(n) |
avg O(1), worst O(n) |
O(n) |
depends on hashing + resizing |
| BST (unbalanced) | O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
can degrade to linked list |
| AVL / Red-Black Tree | O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
guaranteed height O(log n) |
| B-Tree / B+Tree | O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
great for disks/DBs |
| Binary Heap | peek O(1) |
O(n) |
O(log n) |
O(log n) |
O(n) |
priority queue |
| Trie | O(L) |
O(L) |
O(L) |
O(L) |
large | L = key length |
| Fenwick Tree (BIT) | N/A | range sum O(log n) |
update O(log n) |
N/A | O(n) |
prefix sums |
| Segment Tree | N/A | query O(log n) |
update O(log n) |
N/A | O(n) |
flexible aggregates |
Linked List#
- Linear collection of nodes; each node points to next (and possibly prev).
- Good for:
- frequent inserts/deletes when you already have a node reference,
- building other structures (LRU list).
- Bad for:
- random access,
- cache locality.
Variants:
- Singly-linked:
next - Doubly-linked:
prev,next - Circular: last points to first
Stack#
- Operations:
push,pop,peek - LIFO (last in, first out)
- Use cases:
- recursion simulation, DFS
- parentheses matching
- monotonic stack (next greater element, histogram)
Queue / Deque#
- Queue: enqueue at back, dequeue at front (FIFO).
- Deque: insert/delete at both ends.
- Use cases:
- BFS (queue)
- sliding window max (deque)
Tree (graph view)#
A tree is an undirected, connected, acyclic graph.
- For
nnodes: exactlyn-1edges. - Unique simple path between any two nodes.
Binary Tree#
- Each node has ≤ 2 children: left/right.
- Common types:
- Full: each node has 0 or 2 children
- Perfect: all internal nodes have 2 children; all leaves same depth
- Complete: all levels filled except possibly last; last is left-packed
Binary Search Tree (BST)#
Invariant:
- left subtree values ≤ node ≤ right subtree values (or strict
<depending on definition)
Operations are O(h) where h is height.
- Balanced BST:
h = O(log n) - Worst case:
h = O(n)(sorted insertion)
Balanced BSTs (AVL / Red-Black)#
- Guarantee
O(log n)search/insert/delete. - AVL: stricter balance (faster lookups, more rotations).
- Red-Black: looser balance (fewer rotations; widely used).
Trie (Prefix Tree)#
- Stores strings by shared prefixes.
- Search/insert/delete:
O(L)whereLis key length. - Great for:
- prefix queries (“startsWith”),
- autocomplete,
- dictionary word checks.
- Space heavy: optimize with compact tries / ternary search trees.
Heap (Priority Queue)#
- Min-heap / max-heap
- Operations:
peek:O(1)push:O(log n)pop:O(log n)
- Use cases:
- Dijkstra / Prim
- scheduling, top-k
- streaming median (two heaps)
Hash Map (Hash Table)#
Average O(1) search/insert/delete; worst O(n) (pathological collisions). Collision resolution:
- Separate chaining (buckets are lists/trees)
- Open addressing (linear/quadratic probing, double hashing)
Pitfalls:
- need good hash function,
- load factor + resizing affects performance,
- iteration order usually not sorted.
Fenwick Tree (Binary Indexed Tree)#
Supports:
- point update
- prefix sum query Both in
O(log n).
Common trick:
- range sum
[l..r] = prefix(r) - prefix(l-1)
- Suggested reading: Wiki
Segment Tree#
Supports range queries + point/range updates in O(log n).
- More flexible than Fenwick (min/max/gcd, lazy propagation for range updates).
- Typical memory:
~4n.
- Suggested reading: Wiki
Graph#
Representations:
- Adjacency list: good for sparse graphs (
O(V+E)memory) - Adjacency matrix: good for dense graphs (
O(V^2)memory)
