Data Structures & Algorithms

Every structure and algorithm a syllabus expects, with the complexities that get asked and the conditions under which the textbook answer is wrong.

If you remember nothing else

Big-O is an upper bound, Big-Omega a lower bound, Big-Theta a tight bound — worst case and Big-O are different axes, not synonyms.
Quicksort is O(n log n) average but O(n²) worst case; mergesort is O(n log n) always but needs O(n) extra space; heapsort is O(n log n) in place but unstable.
A hash table is O(1) average and O(n) worst case — the worst case is every key colliding.
Dijkstra fails on negative edge weights; Bellman-Ford handles them and detects negative cycles.
Dynamic programming applies when a problem has optimal substructure AND overlapping subproblems; without overlap, plain divide and conquer is the right tool.
Inorder traversal of a BST yields the keys in sorted order — that single fact answers a surprising number of questions.

11 chapters

1Complexity analysis
2Arrays, linked lists, stacks and queues
3Hashing
4Trees and binary search trees
5Balanced trees: AVL, red-black and B-trees
6Heaps and priority queues
7Graphs: representation and traversal
8Shortest paths, spanning trees and ordering
9Sorting
10Searching
11Algorithm design paradigms

Complexity analysis

Asymptotic notation describes how cost grows as input size grows, ignoring constants and lower-order terms. The point is to compare algorithms independently of machine speed.

Notation	Bound	Read as	Formally
$O (g (n))$	Upper	Grows no faster than $g$	$f (n) \leq c \cdot g (n)$ for some $c > 0$ and all $n \geq n_{0}$
$Ω (g (n))$	Lower	Grows at least as fast as $g$	$f (n) \geq c \cdot g (n)$ for some $c > 0$ and all $n \geq n_{0}$
$Θ (g (n))$	Tight	Grows exactly like $g$	Both $O (g)$ and $Ω (g)$ hold
$o (g (n))$	Strict upper	Grows strictly slower than $g$	Holds for every $c > 0$

The growth hierarchy

O (1) < O (lo g n) < O (n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)

Anything at or below n log n is generally practical; 2^n and n! are usable only for tiny inputs.

Amortised analysis

The average cost per operation across a worst-case sequence of operations. A dynamic array's push is O(n) when it must resize, but resizing doubles the capacity, so the O(n) copies are spread over n cheap pushes — the amortised cost is O(1). Note this is not the same as average-case analysis: amortised is a worst-case guarantee over a sequence, with no probability involved.

The master theorem

For a recurrence of the form $T (n) = a T (n / b) + f (n)$ with $a \geq 1$ , $b > 1$ — compare $f (n)$ against $n^{l o g_{b} a}$ :

Case	Condition	Result	Example
1	$f (n) = O (n^{l o g_{b} a - ϵ})$ — leaves dominate	$T (n) = Θ (n^{l o g_{b} a})$	Binary tree traversal: $T (n) = 2 T (n /2) + O (1) \Rightarrow Θ (n)$
2	$f (n) = Θ (n^{l o g_{b} a})$ — balanced	$T (n) = Θ (n^{l o g_{b} a} lo g n)$	Mergesort: $T (n) = 2 T (n /2) + O (n) \Rightarrow Θ (n lo g n)$
3	$f (n) = Ω (n^{l o g_{b} a + ϵ})$ and regularity holds — root dominates	$T (n) = Θ (f (n))$	$T (n) = 2 T (n /2) + n^{2} \Rightarrow Θ (n^{2})$

Arrays, linked lists, stacks and queues

Operation	Array	Dynamic array	Singly linked list	Doubly linked list
Access by index	O(1)	O(1)	O(n)	O(n)
Search (unsorted)	O(n)	O(n)	O(n)	O(n)
Insert at front	O(n)	O(n)	O(1)	O(1)
Insert at back	—	O(1) amortised	O(n), or O(1) with a tail pointer	O(1)
Delete a known node	O(n)	O(n)	O(n) — need the predecessor	O(1)
Memory overhead	None	Slack capacity	One pointer per node	Two pointers per node
Cache locality	Excellent	Excellent	Poor	Poor

Stacks and queues

	Stack	Queue	Deque	Priority queue
Discipline	LIFO	FIFO	Both ends	By priority
Operations	`push`, `pop`, `peek`	`enqueue`, `dequeue`, `front`	`pushFront/Back`, `popFront/Back`	`insert`, `extractMin`
All O(1)?	Yes	Yes	Yes	No — O(log n) via a heap
Classic uses	Call stack, expression evaluation, DFS, undo, bracket matching	BFS, scheduling, buffering, producer-consumer	Sliding-window maximum, work stealing	Dijkstra, Huffman coding, task scheduling

CTwo questions that come up constantly

// 1. Detect a cycle in a linked list - Floyd's tortoise and hare, O(n) time O(1) space
int hasCycle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;          // one step
        fast = fast->next->next;    // two steps
        if (slow == fast) return 1; // they can only meet inside a cycle
    }
    return 0;
}

// 2. Reverse a singly linked list, iteratively
Node *reverse(Node *head) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;   // prev is the new head
}

Hashing

A hash table maps a key to a bucket index via a hash function, giving O(1) average lookup. Everything interesting is about what happens when two keys land in the same bucket.

Collision strategy	How it works	Trade-off
Separate chaining	Each bucket holds a linked list (or tree) of entries	Simple, degrades gracefully, tolerates load factor > 1; costs pointers and loses locality
Linear probing	On collision try the next slot, wrapping around	Excellent cache locality; suffers primary clustering — runs of full slots grow and merge
Quadratic probing	Try $i^{2}$ slots away	Breaks primary clustering; introduces secondary clustering and may not probe every slot
Double hashing	Step size is itself a second hash of the key	Best distribution of the open-addressing schemes; two hash computations per probe

Operation	Average	Worst case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

The worst case is every key hashing to one bucket. Java 8 mitigates it by converting a bucket to a red-black tree past eight entries, capping the worst case at O(log n).

Trees and binary search trees

Height of a node — longest path down to a leaf, in edges. Depth — path up to the root. A single node has height 0; an empty tree has height −1.
Full binary tree — every node has 0 or 2 children. Complete — every level filled except possibly the last, which fills left to right. Perfect — all leaves at the same depth, every internal node has 2 children.
A perfect binary tree of height $h$ has $2^{h + 1} - 1$ nodes and $2^{h}$ leaves.
A binary tree with $n$ nodes has height at least $⌊ lo g_{2} n ⌋$ and at most $n - 1$ .

Traversals

Traversal	Order	Yields	Typical use
Inorder	Left, Node, Right	For a BST: sorted order	Retrieve sorted keys; validate a BST
Preorder	Node, Left, Right	Root first	Copy or serialise a tree; prefix expressions
Postorder	Left, Right, Node	Children before parent	Delete a tree; evaluate an expression tree; postfix
Level order	Breadth-first, by depth	Level by level	Print by level; find shortest path in an unweighted tree

The first three are depth-first and naturally recursive (O(h) stack). Level order needs an explicit queue.

BST operation	Balanced	Degenerate (sorted insertion)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Inserting already-sorted keys into a plain BST produces a linked list. This is exactly why balanced trees exist.

BST deletion — the three cases

Leaf node
Remove it and null the parent's pointer.
One child
Splice the child into the deleted node's position.
Two children
Replace the node's key with its inorder successor (the leftmost node of the right subtree) or its inorder predecessor, then delete that successor — which by construction has at most one child, reducing to an earlier case.

Balanced trees: AVL, red-black and B-trees

	AVL tree	Red-black tree	B-tree / B+ tree
Balance rule	Height of the two subtrees differs by at most 1	Five colour rules; no red node has a red child	All leaves at the same depth; each node holds between $⌈ m /2 ⌉ - 1$ and $m - 1$ keys
Height bound	$\approx 1.44 lo g n$ — more rigidly balanced	$\leq 2 lo g (n + 1)$	$lo g_{m} n$ — very shallow for large $m$
Lookup	Faster (shorter tree)	Slightly slower	Few node visits, but each is a disk block
Insert/delete	More rotations	At most 2 rotations for insert, 3 for delete	Splits and merges
Best for	Read-heavy in-memory workloads	Mixed read/write; the general-purpose default	Disk-resident indexes
Used by	Some in-memory databases	`std::map`, Java `TreeMap`, Linux CFS scheduler	Database indexes, filesystems (NTFS, ext4)

AVL rotations — four cases. Left-Left needs one right rotation; Right-Right one left rotation; Left-Right a left then a right; Right-Left a right then a left.
Red-black rules — every node is red or black; the root is black; all leaves (NIL) are black; a red node has only black children; every root-to-leaf path contains the same number of black nodes.
The last two rules together force the longest path to be at most twice the shortest, which is where the $2 lo g (n + 1)$ bound comes from.

Heaps and priority queues

Operation	Complexity	Mechanism
Find min/max	O(1)	It is the root
Insert	O(log n)	Append at the end, then sift up
Extract min/max	O(log n)	Swap root with last, shrink, then sift down
Decrease key	O(log n)	Lower the value, sift up
Build heap from n items	O(n)	Sift down from the last internal node backwards
Search arbitrary key	O(n)	No ordering between siblings

Graphs: representation and traversal

	Adjacency matrix	Adjacency list
Space	$O (V^{2})$	$O (V + E)$
Edge exists?	O(1)	$O (de g (v))$
Enumerate neighbours	$O (V)$	$O (de g (v))$
Add an edge	O(1)	O(1)
Best for	Dense graphs; algorithms needing fast edge lookup	Sparse graphs — nearly all real ones

	BFS	DFS
Data structure	Queue	Stack (or recursion)
Order	Level by level from the source	As deep as possible, then backtrack
Complexity	$O (V + E)$	$O (V + E)$
Space	$O (V)$ — can be the whole frontier	$O (h)$ — the current path depth
Finds	Shortest path in an unweighted graph	Cycles, topological order, connected components, bridges and articulation points
Also used for	Bipartiteness checking, web crawling by level	Maze solving, backtracking, strongly connected components

PythonCycle detection differs by graph type

# Undirected: any visited neighbour that is not the parent closes a cycle.
def has_cycle_undirected(g, u, parent, seen):
    seen.add(u)
    for v in g[u]:
        if v not in seen:
            if has_cycle_undirected(g, v, u, seen): return True
        elif v != parent:
            return True                 # back edge
    return False

# Directed: needs three colours. A grey neighbour means a back edge; a black
# one is merely a cross edge to a finished subtree and is NOT a cycle.
WHITE, GREY, BLACK = 0, 1, 2
def has_cycle_directed(g, u, colour):
    colour[u] = GREY
    for v in g[u]:
        if colour[v] == GREY: return True
        if colour[v] == WHITE and has_cycle_directed(g, v, colour): return True
    colour[u] = BLACK
    return False

Shortest paths, spanning trees and ordering

Algorithm	Solves	Complexity	Negative weights?
Dijkstra	Single-source shortest path	$O ((V + E) lo g V)$ with a binary heap	No — fails silently
Bellman-Ford	Single-source shortest path	$O (V E)$	Yes, and detects negative cycles
Floyd-Warshall	All-pairs shortest paths	$O (V^{3})$	Yes (no negative cycles)
Kruskal	Minimum spanning tree	$O (E lo g E)$	Yes — weights may be negative
Prim	Minimum spanning tree	$O (E lo g V)$ with a heap	Yes
Topological sort	Linear order of a DAG	$O (V + E)$	N/A — unweighted

Bellman-Ford relaxes every edge $V - 1$ times. If a $V$ -th pass still improves a distance, a negative cycle is reachable.
Topological sort exists iff the graph is a DAG. Two methods: repeatedly remove a vertex of in-degree 0 (Kahn's algorithm), or reverse the DFS finish order.
Union-find with path compression and union by rank gives near-constant $O (α (n))$ per operation, where $α$ is the inverse Ackermann function — at most 4 for any practical input.
A minimum spanning tree is unique if all edge weights are distinct. It always has exactly $V - 1$ edges.

Sorting

Algorithm	Best	Average	Worst	Space	Stable	Method
Bubble	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes	Exchange
Selection	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	No	Selection
Insertion	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes	Insertion
Merge	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	Yes	Divide & conquer
Quick	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g n)$	No	Divide & conquer
Heap	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	No	Selection
Counting	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (k)$	Yes	Non-comparison
Radix	$O (d (n + k))$	$O (d (n + k))$	$O (d (n + k))$	$O (n + k)$	Yes	Non-comparison

Quicksort's worst case is an already-sorted array with a first-element pivot — every partition splits 1 and n−1.
Insertion sort is O(n) on nearly-sorted data and beats everything for n below roughly 10–20, which is why hybrid sorts fall back to it.
Mergesort is the standard choice for linked lists (no random access needed, and it can be done with O(1) extra space) and for external sorting of data too large for memory.
Timsort (Python, Java objects) is a stable hybrid of mergesort and insertion sort that detects existing runs — O(n) on already-sorted input.

Searching

Technique	Requires	Complexity	Note
Linear search	Nothing	O(n)	The only option on unsorted data
Binary search	Sorted, random access	O(log n)	Halves the range each step
Jump search	Sorted array	$O (n)$	Fixed-size jumps then a linear scan
Interpolation search	Sorted and uniformly distributed	$O (lo g lo g n)$ average, O(n) worst	Estimates position from the value
Exponential search	Sorted, unbounded	O(log n)	Find a range by doubling, then binary search
Hash lookup	A hash table	O(1) average	No ordering, so no range queries

CBinary search, including the overflow bug

int binary_search(int a[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        // NOT (lo + hi) / 2 - that overflows once lo + hi exceeds INT_MAX.
        // This bug sat undetected in the JDK for nine years.
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] <  key) lo = mid + 1;
        else               hi = mid - 1;
    }
    return -1;
}

Algorithm design paradigms

Paradigm	Idea	Applies when	Examples
Divide & conquer	Split into independent subproblems, solve, combine	Subproblems do not overlap	Mergesort, quicksort, binary search, Strassen
Greedy	Take the locally best choice and never reconsider	The greedy-choice property and optimal substructure both hold	Dijkstra, Kruskal, Prim, Huffman, activity selection
Dynamic programming	Solve each overlapping subproblem once and store the result	Optimal substructure and overlapping subproblems	Knapsack, LCS, edit distance, matrix chain, Floyd-Warshall
Backtracking	Build candidates incrementally, abandon a branch as soon as it cannot work	Constraint satisfaction over a search tree	N-queens, sudoku, subset sum, graph colouring
Branch & bound	Backtracking plus a bound that prunes provably worse branches	Optimisation over a large search space	0/1 knapsack, travelling salesman

Classic DP problem	State	Complexity
0/1 knapsack	`dp[i][w]` = best value using first i items within weight w	$O (nW)$ — pseudo-polynomial
Longest common subsequence	`dp[i][j]` = LCS of the two prefixes	$O (mn)$
Edit distance	`dp[i][j]` = edits to turn prefix i into prefix j	$O (mn)$
Matrix chain multiplication	`dp[i][j]` = min cost to multiply matrices i..j	$O (n^{3})$
Coin change (min coins)	`dp[a]` = fewest coins summing to a	$O (n \cdot amount)$
Longest increasing subsequence	`dp[i]` = LIS ending at i	$O (n^{2})$ , or $O (n lo g n)$ with binary search

Data Structures & Algorithms

If you remember nothing else

1Complexity analysis

The growth hierarchy

Amortised analysis

The master theorem

2Arrays, linked lists, stacks and queues

Stacks and queues

3Hashing

4Trees and binary search trees

Traversals

BST deletion — the three cases

5Balanced trees: AVL, red-black and B-trees

6Heaps and priority queues

7Graphs: representation and traversal

8Shortest paths, spanning trees and ordering

9Sorting

10Searching

11Algorithm design paradigms