Core abstractions of computer science — algorithms, motivations, and real-world applications, ordered by increasing complexity
O(1) access
▦
Array
Contiguous block of elements addressable by index. The foundation of nearly all other structures.
Access O(1)
Search O(n)
Insert O(n)
Delete O(n)
O(1) insert
⬡
Linked List
Nodes connected by pointers. Constant-time insertion/deletion at known positions without shifting.
Access O(n)
Search O(n)
Insert O(1)
Delete O(1)
LIFO
⬆
Stack
Last-in, first-out discipline. Push and pop from one end only. Models function call frames and undo history.
Push O(1)
Pop O(1)
Peek O(1)
FIFO
⇒
Queue
First-in, first-out discipline. Enqueue at the back, dequeue from the front. Natural model for waiting lines and BFS.
Enqueue O(1)
Dequeue O(1)
Peek O(1)
O(log n) avg
🌲
Binary Search Tree
Ordered binary tree where left < parent < right. Fast search, insert, and delete on average-case data.
Search O(log n)
Insert O(log n)
Delete O(log n)
Worst O(n)
O(log n) worst
⚖
Balanced BST (AVL / Red-Black)
Self-balancing trees that guarantee O(log n) in the worst case by maintaining height invariants via rotations.
Search O(log n)
Insert O(log n)
Delete O(log n)
O(log n) push/pop
△
Heap (Priority Queue)
Complete binary tree satisfying the heap property. O(1) access to the min or max element; O(log n) insertion.
Peek O(1)
Push O(log n)
Pop O(log n)
Build O(n)
O(k) per op
✦
Trie (Prefix Tree)
Tree where each edge is a character. Lookup time is proportional to key length, not corpus size. Ideal for autocomplete.
Insert O(k)
Search O(k)
Prefix O(k)
O(1) avg
#
Hash Table
Maps keys to array indices via a hash function. Expected O(1) insert, lookup, and delete — the workhorse of fast lookup.
Insert O(1) avg
Lookup O(1) avg
Delete O(1) avg
Worst O(n)
V + E
◎
Graph
Vertices connected by edges. Directed or undirected, weighted or unweighted. Models relationships, networks, and dependencies.
BFS O(V+E)
DFS O(V+E)
Dijkstra O((V+E)log V)
≈ O(α(n))
∪
Disjoint Set (Union-Find)
Tracks a partition of elements into disjoint groups. Near-constant amortised time with union-by-rank and path compression.
Find O(α(n))
Union O(α(n))
O(k) · no FN
~
Bloom Filter
Probabilistic set membership test. Space-efficient: no false negatives; small, tunable false-positive rate.
Insert O(k)
Query O(k)
Space O(m bits)
O(log n) expected
≡
Skip List
Randomised multi-level linked list. Provides sorted access with O(log n) expected operations — no rotations needed.
Search O(log n)
Insert O(log n)
Delete O(log n)
Click any card to explore the full algorithm, motivation, and real-world application examples.