Every algorithm leans on a data structure. Pick one — watch it grow, shrink, balance, and break. Edit the input, scrub the timeline, and see exactly what each operation costs.
New to this section? Work through these in order — each builds on the previous.
Contiguous storage with constant-time index access. The catch is that anything which changes the length — insert in the middle, delete from the front — pays an O(n) shift cost because the rest of the array has to move over. Swap, on the other hand, is two reads and two writes. The shift cost is exactly why we reach for linked lists, deques, or hash maps when a workload is insert-heavy in the middle.
A chain of nodes where each one knows where the next one lives. The structure is defined by the pointers — not the order memory addresses happen to fall in. Insert and delete are O(1) once you have a handle on the right spot, but finding that spot is O(n) because you can only walk forward from the head. Reverse is the classic interview question: with three pointers (prev/curr/nxt) you can flip every arrow in a single linear pass.
Two linear structures that differ only in WHERE removal happens. A stack is LIFO — push adds to the top, pop removes the most recent value. A queue is FIFO — enqueue adds to the back, dequeue removes the oldest. The visualization is one strip of cells: stacks treat the right end as the top; queues treat the left end as the front and the right as the back. Both push/enqueue and pop/dequeue run in amortized O(1).
A binary heap is a complete binary tree packed into an array — index 0 is the root, and the children of index i live at 2i+1 and 2i+2. The min-heap property says every parent is ≤ its children, which makes the smallest value always available at the root in O(1). Insert appends at the end and 'sifts up'; extract-min swaps the root with the last leaf and 'sifts down'. Both run in O(log n).
A binary tree with the invariant 'every left descendant is smaller than the node, every right descendant is larger.' Search, insert, and delete all walk down from the root following the same compare-and-descend rule, taking O(log n) on average. The famous trick is deleting a node with two children: copy in the in-order successor's value, then delete the successor (which always has at most one child).
A binary tree where every node owns a contiguous range. Leaves are single array positions; each internal node aggregates its two children (sum, min, max, etc.). Build once in O(n). Point updates walk one root-to-leaf path, then bubble the new aggregate back up — O(log n). Range queries split the asked range across two subtrees at each level, hitting at most O(log n) nodes total. The trick is recognising that any range [l, r] can be assembled from at most O(log n) of these pre-aggregated chunks.
A 1-indexed array where each slot stores a partial sum over a power-of-two range determined by its lowest set bit. To compute prefix-sum(i), walk i → i − (i & −i) and accumulate. To update index i by delta, walk i → i + (i & −i), adding delta to each slot along the way. Both walks visit at most O(log n) slots, so Fenwick trees give the same O(log n) point-update / prefix-sum performance as segment trees with about half the code and a quarter the memory.
Each element starts in its own set. union(x, y) merges the two sets; find(x) names the set (its root). Union by rank attaches the shallower tree to the deeper one so the worst-case tree stays balanced; path compression flattens chains during find so subsequent queries are nearly O(1). Together they give an effectively constant-time amortized union-find — the inverse Ackermann function bound. Used everywhere: Kruskal's MST, cycle detection in undirected graphs, network connectivity, image segmentation.
A tree where every edge is a character. To insert a word, walk character by character, creating any missing child along the way, then mark the last node as 'end of word.' Search and prefix-search walk the same path; the difference is whether the final node has the end-of-word flag set. Tries front-load all the work into the structure, so lookups are O(length-of-key) regardless of how many keys are stored — perfect for autocomplete, spell-check, and longest-common-prefix problems.