Data Structures

DSA

Array

• Access: O(1)

• Insert/delete: O(n)

• Space: O(n)

• Contiguous memory

• Best for: fast indexing

• Bad for: resizing / inserting in middle

Dynamic Array

• Access: O(1)

• Append: O(1) amortized

• Insert/delete: O(n)

• Resizes by doubling

• Best for: flexible arrays

• Key idea: amortized cost

Linked List

• Insert/delete: O(1)

• Search: O(n)

• No random access

• Best for: frequent insert/delete

• Worst for: searching

Stack / Queue / Deque

• Push/pop: O(1)

• Search: O(n)

• Stack = LIFO

• Queue = FIFO

• Deque = both ends

• Used in: DFS (stack), BFS (queue)

Binary Search Tree (BST)

Back:

• Search/insert/delete: O(n) worst

• Sorted structure

• Left < root < right

• Can become skewed (linked list)

• Used for: ordered data

Balanced BST (AVL / Red-Black)

• Operations: O(log n)

• Self-balancing

• AVL = stricter balance

• RB = used in Java/Linux

• Used when: need sorted + fast ops

Heap / Priority Queue

• Insert: O(log n)

• Remove min/max: O(log n)

• Peek: O(1)

• NOT sorted

• Used in: Dijkstra

• Key idea: parent ≤ children (min heap)

Hash Table

• Insert/search/delete: O(1) expected

• Worst: O(n) (collisions)

• Uses hashing + buckets

• No ordering

• Best for: fast lookup by key

• Collision handling:

  • chaining

  • open addressing

Adjacency List

• Space: O(n + m)

• Good for sparse graphs

• Used in:

  • DFS

  • BFS

  • Dijkstra

• Stores neighbors

Adjacency Matrix

• Space: O(n²)

• Fast edge lookup: O(1)

• Bad for sparse graphs

• Good for dense graphs

Union-Find (Disjoint Set)

• Find/union: O(α(n)) ≈ O(1)

• Tracks connected components

• Used in: Kruskal

• Prevents cycles

• Structure = parent array

Skip List

• Search/insert/delete: O(log n) expected

• Randomized

• Sorted structure

• Alternative to BST

Bloom Filter

• Insert/lookup: O(1)

• Space: very compact

• ❌ No deletion

• ❌ False positives possible

• ✅ No false negatives

• Used for: membership check

Cuckoo Filter

• Insert/lookup/delete: O(1) expected

• Supports deletion (unlike Bloom)

• False positives possible

• Used for: fast membership w/ deletion

B-Tree

• Operations: O(log n)

• Disk-based structure

• Used in databases

• Multi-way tree

LSM Tree

• Write: O(1) (append)

• Read: O(log n)

• Optimized for disk + heavy writes

• Used in:

  • databases

  • versioned systems