Growth rate · how cost scales with n
Drag the slider — bars use √-scaling so the small orders stay visible.
10.1 · Array, Stack & Queue
Contiguous memory · LIFO push/pop · FIFO enqueue/dequeue
idle
| Operation | Time | Space |
|---|---|---|
| push / pop (end) | O(1) | O(1) |
| enqueue (end) | O(1) | O(1) |
| dequeue (shift) | O(n) | O(1) |
| whole structure | — | O(n) |
An array is one contiguous block: the address of A[i] is base + i·size, so indexing is a single multiplication — O(1). Removing from the front forces every element to slide left, which is why a real queue uses a ring buffer (two indices) to keep dequeue at O(1).
10.2 · Linked List
Nodes scattered in memory, joined by pointers
idle
| Operation | Time | Space |
|---|---|---|
| insert at head | O(1) | O(1) |
| insert at tail | O(n) | O(1) |
| search / access i | O(n) | O(1) |
| store n elements | — | O(n) + pointers |
A linked list trades random access for cheap splicing. Because nodes are not contiguous you cannot jump to the i-th element — you must follow next pointers one at a time, giving O(n) traversal. The extra memory per node (one pointer) is the price of that flexibility.
11 · Hash Table (chaining)
h(k) = k mod 7 · collisions are chained in a linked list per bucket
idle
| Operation | Average | Worst |
|---|---|---|
| insert | O(1) | O(n) |
| search | O(1) | O(n) |
| delete | O(1) | O(n) |
| space | O(n + m) — keys + buckets | |
A direct-address table is O(1) but wastes space when the universe U is huge. A hash table compresses U into m slots. With load factor α = n/m the expected chain length is α, so an unsuccessful search scans α elements — O(1+α). A bad hash function collapses everything into one bucket and you are back to O(n).
12 · Binary Search Tree
left < node < right · every level halves the search space
idle
| Operation | Average | Worst |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
| in-order walk | O(n) — visits every node | |
The bound is written O(h) where h is the height. A balanced tree has h ≈ log₂n; a degenerate chain (insert 1,2,3,4,5…) has h = n. Try inserting sorted values here and watch the tree become a linked list — that is exactly the failure mode red-black trees fix.
13 · Red-Black Tree · rotations
Recolouring + rotation keeps height ≤ 2·log₂(n+1) — guaranteed O(log n)
press play
| Operation | Time | Space |
|---|---|---|
| search | O(log n) | O(1) |
| insert / delete | O(log n) | O(1) |
| rotation | O(1) | O(1) |
| tree storage | — | O(n) + 1 bit |
Five properties keep the tree shallow. After inserting a RED node, a red-red violation is repaired by looking at the uncle: if it is red → recolor and move up (O(log n) total); if it is black → one or two rotations, each a pure pointer shuffle costing O(1). Total insert is O(log n) time and O(1) extra space.