Data Structures

Fixed-size, contiguous memory
[1][2][3][4][5]

Access: O(1)
Insert/Delete at end: O(1)
Insert/Delete at start/middle: O(n)
Search (unsorted): O(n)
Search (sorted): O(log n) with binary search

Nodes with data + pointer to next
[1]→[2]→[3]→[4]→null

Access: O(n)
Insert/Delete at start: O(1)
Insert/Delete at end: O(n) (O(1) if tail pointer)
Insert/Delete in middle: O(n) to find, O(1) to modify
Search: O(n)

Variants:
- Singly linked (→)
- Doubly linked (←→)
- Circular (last points to first)

    ┌───┐
    │ 3 │ ← top
    ├───┤
    │ 2 │
    ├───┤
    │ 1 │
    └───┘

Operations:
- push(x): Add to top - O(1)
- pop(): Remove from top - O(1)
- peek(): View top - O(1)

Use cases: Function calls, undo/redo, parentheses matching

Front                    Back
  ↓                        ↓
[1]→[2]→[3]→[4]
  ↑             ↑
dequeue      enqueue

Operations:
- enqueue(x): Add to back - O(1)
- dequeue(): Remove from front - O(1)
- peek(): View front - O(1)

Use cases: Task scheduling, BFS, request handling

Can add/remove from both ends
[1]⟷[2]⟷[3]⟷[4]
 ↑              ↑
Both ends     Both ends

All operations: O(1)

      1
     / \
    2   3
   / \
  4   5

Each node has ≤2 children
Height: h (levels)
Max nodes: 2^h - 1

      5
     / \
    3   8
   / \   \
  1   4   9

Left < Parent < Right

Search/Insert/Delete: O(log n) average, O(n) worst
Balanced BST: O(log n) guaranteed

Max-Heap:
      9
     / \
    7   5
   / \
  3   1

Parent ≥ Children (max-heap)
Parent ≤ Children (min-heap)

Insert: O(log n)
Extract max/min: O(log n)
Peek max/min: O(1)

Use cases: Priority queues, heap sort

       root
      /  |  \
     c   d   t
    /    |    \
   a     o     o
  /      |      \
 t       g       p
(cat)  (dog)   (top)

Insert/Search: O(m) where m = string length
Space: O(ALPHABET_SIZE × m × n)

Use cases: Autocomplete, spell check, IP routing

Key → Hash Function → Index → Value

hash("alice") → 3 → [3] = {age: 30}

Average case:
- Insert: O(1)
- Delete: O(1)
- Search: O(1)

Worst case (collisions): O(n)

Collision handling:
- Chaining (linked lists)
- Open addressing (probing)

Same as hash table but only stores keys (no values)

Contains/Add/Remove: O(1) average

Use cases: Unique elements, membership testing

Adjacency List:
A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

Adjacency Matrix:
    A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]

Types:
- Directed vs Undirected
- Weighted vs Unweighted
- Cyclic vs Acyclic (DAG)

Traversal:
- BFS: O(V + E) using queue
- DFS: O(V + E) using stack/recursion

Guarantees O(log n) for all operations
Height difference between subtrees ≤ 1
Rebalances via rotations

Another self-balancing BST
Slightly more relaxed than AVL
Used in: Java TreeMap, C++ map

Multi-way tree (more than 2 children)
Used in: Databases, filesystems
Optimized for disk reads

For range queries (sum, min, max)
Build: O(n)
Query: O(log n)
Update: O(log n)

Tracks set membership
Union: O(α(n)) ≈ O(1)
Find: O(α(n)) ≈ O(1)
α(n) = inverse Ackermann (extremely slow growing)

Use cases: Connected components, Kruskal's algorithm