Indexed storage, range summaries, and growth costs. Work through the operation contract, runnable case, and cost before selecting the structure for a real workload.
Lessons
- Resizable arrays: account for growth and shifting
- Prefix sums: trade one scan for constant-time ranges
Practice and next steps
- Project: choose structures for a dispatch board
- Project: audit depot connectivity and daily ranges
- Linear and hash structure decisions
- Tree, graph, and range structure decisions
- DSA Tutorial
Sorting alongside arrays
Piece tables: edit text through source spans
Generational slots: reject stale handles after reuse
Reservoir sampling: keep a uniform fixed-size sample
Gap buffers: pay when the edit cursor crosses text
Segmented arrays: locate blocks through cumulative lengths
Checkpoint arenas: reclaim a region by lifetime
Free spans: first-fit allocation and adjacent coalescing
Eytzinger arrays: store a search tree in breadth-first order
Piecewise interpolation indexes: predict a bounded rank window
Persistent radix vectors: copy one indexed path per revision
Disjoint interval unions: maintain covered maintenance time
Gap labels: compare dispatch order across middle inserts
Alias tables: constant-work draws from fixed dispatch weights
Exponential histograms: estimate failures in a recent event window
Bit-sliced indexes: filter and sum fixed-width sensor readings