Data Structure Complexity
The full time/space table for every structure you reach for — average and worst case, at a glance. The interview reference.
Linear structures (avg / worst)
- Array (static)
- access
O(1)· searchO(n)· insert/deleteO(n)· spaceO(n) - Dynamic array
- access
O(1)· appendO(1)amortized · insert/deleteO(n) - Singly linked list
- access/search
O(n)· insert/delete at headO(1) - Doubly linked list
- same, plus
O(1)delete given the node - Stack / Queue
- push/pop/enqueue/dequeue
O(1)
Hash & trees
- Hash table
- search/insert/delete
O(1)avg ·O(n)worst (bad hashing) - Binary search tree
O(log n)avg ·O(n)worst (degenerate/unbalanced)- Balanced BST (AVL / red-black)
- search/insert/delete
O(log n)worst — guaranteed - B-tree
O(log n)· high fan-out → few disk reads (DB indexes)- Binary heap
- peek
O(1)· push/popO(log n)· buildO(n) - Trie
- search/insert
O(L)in key length L (not n)
Probabilistic & specialized
- Skip list
- search/insert/delete
O(log n)expected · spaceO(n) - Bloom filter
- add/query
O(k)hashes · space sublinear · false positives, no false negatives - Fenwick / segment tree
- point update + range query
O(log n) - Union-Find
- near
O(1)amortized (inverse-Ackermann) with path compression + rank - LRU cache
- get/put
O(1)— hash map + doubly linked list
Rules of thumb
- Need ordering?
- Balanced BST / skip list —
O(log n)with sorted traversal. - Need only membership/lookup?
- Hash table —
O(1), no order. - Need min/max repeatedly?
- Heap —
O(log n)push/pop. - Worst case matters (latency SLA)?
- Avoid plain hash/BST; use balanced trees or bounded structures.