A data structure defines which operations are cheap, which are costly, and which invariants must stay true after mutation. Start with the workload: indexed reads, ordered updates, keyed lookup, priority selection, connectivity, or repeated range queries. Then compare time, memory, and failure behavior rather than choosing by name alone.
Arrays
Indexed storage, range summaries, and growth costs.
- Resizable arrays: account for growth and shifting
- Prefix sums: trade one scan for constant-time ranges
- Arrays
Linked Lists
Pointer changes, traversal, and node ownership.
- Singly linked lists: preserve head and tail invariants
- Doubly linked lists: relink known nodes safely
- Linked Lists
Stacks and Queues
Ordering contracts for undo, buffering, and scheduling.
- Stacks: last-in-first-out for reversible edits
- Queues: preserve arrival order without front shifts
- Ring buffers: make capacity and overwrite rules explicit
- Stacks and Queues
Hashing
Keyed lookup, collisions, and membership.
- Hash maps: keyed lookup with collision and load costs
- Hash sets: fast membership without an order promise
- Hashing
Trees and Heaps
Hierarchical search and priority order.
- Binary search trees: preserve order through every branch
- Binary heaps: select the next priority with a tie rule
- Tries: make prefix search distinct from complete-key lookup
- Trees and Heaps
Graphs
Adjacency, traversal, and connectivity.
- Graphs: adjacency lists and breadth-first reachability
- Disjoint sets: merge connectivity without tracing every path
- Graphs
Range Queries
Point updates and repeated interval queries.
- Fenwick trees: update points and query prefix totals
- Segment trees: combine child ranges after updates
- Range Queries
Projects
Combine structures under an operation contract.
- Project: choose structures for a dispatch board
- Project: audit depot connectivity and daily ranges
- Projects
Quizzes
Check invariants and cost claims.
LRU caches: couple keyed lookup to recency order
AVL trees: restore height balance after insertion
CSR graphs: pack sparse neighbors for repeated scans
Sparse tables: precompute immutable range minima
Bloom filters: reject absent keys without claiming exact membership
Sparse sets: constant-time membership for bounded integer IDs
Skip lists: randomized levels over an ordered bottom chain
B+ leaf pages: split full pages and keep range order
Persistent segment trees: retain old range-sum versions
Monotonic deques: maintain a sliding minimum in linear time
Project: design a versioned warehouse index
Red-black trees: audit color and black-height invariants
B-trees: split full pages during ordered insertion
Interval trees: prune overlap search with subtree maximums
Compressed tries: split shared edge labels at the divergence
Bounded thread queues: separate FIFO removal from task completion
Project: own a maintenance index and work queue
Red-black insertion: rotate and recolor an ordered index
B+ trees: propagate leaf splits through multiple levels
Balanced interval indexes: rotate height and maximum metadata together
Compressed tries: delete exact keys and merge unused edges
Project: test mutation invariants across four indexes
Mutation and versioning contracts
B+ deletion: borrow, merge, and repair separators
Indexed binary heaps: decrease a queued priority
Open-addressed hash tables: tombstones and rebuilds
Dependency graphs: topological order and cycle rejection
Project: release a warehouse plan after indexed mutations
Deletion, priority, and dependency checks
Red-black deletion: move color before removing a key
AVL interval deletion: repair balance and maximum endpoints
Disjoint-set rollback: restore an earlier connectivity checkpoint
Shortest routes: skip stale min-heap entries
Project: test depot rollback, routes, and ordered deletion
Tree deletion, rollback, and route checks
Offline connectivity: edge lifetimes and rollback unions
Bounded queues: close, wake waiters, and drain accepted work
Index snapshots: publish related maps as one in-memory version
Page journals: replay committed index changes
Project: plan a reversible depot release
Offline connectivity, queue, snapshot, and recovery checks
Online connectivity: answer after each edge change
Persistent ordered indexes: copy search paths, share subtrees
Framed journals: detect a torn tail before replay
CAS queue protocol: link, help, and reclaim safely
Project: audit a live depot index and recovery path
Online routes, persistent roots, journals, and CAS checks
Failure-linked tries: find overlapping alert terms in one scan
Suffix arrays: indexed substring search and adjacent LCP
K-d trees: exact nearest depot with plane pruning
Count-min sketches: bounded-memory event estimates
Project: search incident text and count event pressure
Pattern, spatial, and frequency index checks
Circular linked lists: keep one tail and a valid cycle
Binary-tree traversals: four orders without recursion
Dense graph bitsets: adjacency and common neighbors
AVL order statistics: maintain subtree sizes for rank and select
Project: audit dispatch order and dense depot links
Circular lists, traversal, bitsets, and rank checks
Sparse coordinate segment tree: allocate only visited paths
Wavelet tree: subarray counts and order statistics
Parity disjoint set: maintain same-or-different constraints
Implicit treap: edit positions and reverse a range
Project: audit sparse readings and task constraints
Sparse sums, quantiles, parity, and sequence edits
Bitvector rank and select: count and locate set bits
Heavy-light decomposition: sum weights along a tree path
Sorted runs and tombstones: model an LSM read path
Project: audit incident flags, depot paths, and sorted runs
Bit rank, depot paths, and sorted-run contracts
Lazy segment tree: add to a range and query its minimum
Binary lifting: ancestors and common managers
Two-dimensional Fenwick tree: update cells and sum rectangles
Robin Hood hashing: probe distance and backward-shift deletion
Project: audit capacity ranges and warehouse indexes
Lazy ranges, ancestors, grids, and hash probes
Link-cut forests: change tree edges and sum a path
Suffix automata: index substrings as text arrives
Piece tables: edit text through source spans
Project: audit a depot forest and incident notes
Forest paths, online substrings, and text pieces
Cuckoo hashing: relocate keys and recover from cycles
Packed R-tree: search intersecting depot rectangles
Binary tries: choose a maximum-XOR fingerprint
Project: audit asset IDs and depot zones
Cuckoo slots, spatial boxes, and bit trie paths
Two Fenwick trees: add across ranges and query sums
Merkle trees: verify an indexed scan record
Two heaps: maintain an exact running median
Project: audit capacity, medians, and scan integrity
Range corrections, hash proofs, and median heaps
Square-root blocks: update one capacity and sum a range
Merge-sort trees: count readings below a threshold in one interval
Disjoint sparse tables: immutable sums with constant-time queries
Li Chao trees: minimum linear tariff at a chosen quantity
Project: audit four range-query workloads
Block, threshold, disjoint, and line index contracts
Coordinate compression: preserve order with dense integer ranks
Fenwick frequency index: select the kth stored key
Mo ordering: count distinct scan codes across an offline query batch
Two-dimensional prefixes: constant-time static rectangle sums
Project: audit ranks, windows, and grid reports
Coordinate ranks, order selection, offline windows, and grid sums
Inverted indexes: intersect sorted incident postings
Positional postings: find exact token phrases
Trigram indexes: filter and verify substring candidates
Front-coded lexicons: store shared prefixes within sorted term blocks
Project: audit incident text index contracts
Postings, positions, trigrams, and lexicon contracts
LFU caches: evict by frequency, then recency
Expiry heaps: invalidate stale TTL records on replacement
Generational slots: reject stale handles after reuse
D-ary heaps: trade shallower ascent for wider extraction
Project: audit incident retention and dispatch
Eviction, expiry, handles, and heap contracts
Misra–Gries: find frequent-item candidates in one pass
Space-Saving: ranked candidates with count bounds
HyperLogLog: estimate unique IDs with fixed registers
Reservoir sampling: keep a uniform fixed-size sample
Project: audit four bounded stream views
Frequent items, distinct counts, and stream samples
Counting Bloom filters: delete only a known insertion
Scalable Bloom filters: grow without discarding old members
Blocked Bloom filters: localize probes and watch skew
Cuckoo filters: relocate compact fingerprints safely
Project: audit approximate-membership mutations
Approximate membership under mutation
Pairing heaps: meld roots and pair children on removal
Binomial heaps: carry equal-degree trees during merge
Radix heaps: queue nondecreasing integer priorities
Double-ended queues: reconcile min and max heaps
Project: audit four priority-queue contracts
Priority-queue merge, monotonicity, and extremes
Spatial hash grids: move points between occupied cells
Point-region quadtrees: subdivide crowded cells
Bounding-volume hierarchies: prune box overlap searches
Morton ordering: decompose a grid window into code ranges
Project: audit moving points and static spatial boxes
Spatial grids, quadtrees, boxes, and code ranges
Gap buffers: pay when the edit cursor crosses text
Ropes: share text chunks across immutable revisions
Unrolled lists: link small blocks instead of single items
Segmented arrays: locate blocks through cumulative lengths
Project: audit text edits and blocked sequence lookups
Gap buffers, ropes, and blocked sequences
Elias–Fano: split sorted IDs into low parts and high bits
Chunked integer sets: switch sparse arrays to dense bitmaps
Gap-encoded postings: add checkpoints to bytewise seeks
Level-order unary degree tries: encode child runs as bits
Project: audit compact alert and document indexes
Compact integer sets, postings, and tries
Checkpoint arenas: reclaim a region by lifetime
Free spans: first-fit allocation and adjacent coalescing
Buddy blocks: split powers of two and reunite partners
Slab slots: reuse fixed-size pages with generation checks
Project: audit four reusable storage contracts
Arenas, free spans, buddies, and slab slots
Bitmap hash tries: copy paths for immutable alert maps
Ternary search trees: branch by character and continue prefixes
Binary radix routing: choose the longest matching prefix
Extendible hashing: split buckets through a shared directory
Project: audit four keyed-lookup structures
Hash tries, term trees, routes, and directories
CLOCK caches: revisit pages through reference bits
Segmented LRU: separate probation from protected reuse
Frequency admission: compare an arrival with an eviction victim
Hashed timing wheels: bucket incident expiries by tick
Project: audit eviction, admission, and expiry
CLOCK, segmented LRU, admission, and timer wheels
Splay Trees: Access Rotations and Join Invariants
Resident LRU-K: Evict by the Kth Recent Reference
Project: Audit Adaptive Search and Cache History
Splay trees and resident history eviction
Eytzinger arrays: store a search tree in breadth-first order
Cartesian trees: preserve sequence order under a heap minimum
Leftist heaps: keep the right spine short for meld
Potential disjoint sets: preserve numeric differences across merges
Two-dimensional range trees: count a static rectangle
Van Emde Boas trees: successor in a bounded integer universe
Scapegoat trees: rebuild a deep insertion subtree
Static XOR filters: peel a fingerprint membership index
Project: audit search layouts, range roots, melds, and numeric constraints
Check search layouts, range roots, melds, and numeric constraints
Project: audit spatial counts, bounded successors, rebuilds, and filter membership
Check spatial counts, bounded successors, rebuilds, and filter membership
Palindromic trees: index distinct palindromes as text arrives
Segment tree beats: cap a range while retaining its sum
Wavelet matrices: count frequencies and find subarray quantiles
Two-stack window aggregation: keep FIFO order under a monoid
Linear hashing: split one bucket at a time as a table grows
Compressed 2D Fenwick trees: toggle known points and count rectangles
Persistent two-list queues: fork FIFO dispatch history
Balanced-parentheses trees: encode an ordered hierarchy
Project: audit streaming palindromes, range caps, quantiles, and window order
Check streaming palindromes, range caps, quantiles, and window order
Project: audit hash splits, spatial toggles, queue versions, and tree intervals
Check hash splits, spatial toggles, queue versions, and tree intervals
BK-trees: search incident labels within edit distance
Vantage-point trees: nearest depots by a metric radius
Centroid decomposition: nearest marked depot on a fixed tree
Two-level perfect hashing: exact static case membership
FM-index backward search: narrow a suffix interval by character
Block-max postings: skip safe document-score regions
Piecewise interpolation indexes: predict a bounded rank window
Euler-tour RMQ: answer static common ancestors in constant query time
Project: audit metric searches, marked depots, and static membership
Check metric searches, marked depots, and static membership
Project: audit text intervals, score bounds, rank models, and ancestor tours
Check text intervals, score bounds, rank models, and ancestor tours
X-fast trie: predecessor and successor in a fixed integer universe
Persistent radix vectors: copy one indexed path per revision
Compressed suffix trees: locate patterns across a frozen text
Disjoint interval unions: maintain covered maintenance time
CSR delta overlays: stage road edits before compaction
Reachability bitsets: precompute directed paths for a fixed graph
Gap labels: compare dispatch order across middle inserts
Skew heaps: meld priorities by swapping child paths
Project: audit predecessor, revision, substring, and coverage snapshots
Check predecessor, revision, substring, and coverage snapshots
Project: audit graph overlays, path bits, labels, and heap ownership
Check graph overlays, path bits, labels, and heap ownership
Fibonacci heaps: cut on decrease and consolidate on removal
Tournament trees: merge sorted runs through one winner path
Priority search trees: report events in a three-sided region
Reduced ordered decision diagrams: share identical rule branches
LZ78 phrase tries: emit dictionary index and next symbol
Segment-tree stabbing indexes: list intervals active at one point
Huffman trees: assign prefix codes from symbol frequencies
Condensation DAGs: compress directed cycles before path queries
Project: audit heap repairs, run winners, spatial pruning, and rules
Check heap repairs, run winners, spatial pruning, and rules
Project: audit phrase codes, active intervals, prefix bits, and routes
Check phrase codes, active intervals, prefix bits, and routes
Ordered treaps: split, join, and select depot keys
Span skip lists: rank and select without a full scan
Two-dimensional segment trees: correct sensors and sum rectangles
Range-majority indexes: verify a candidate before returning it
Alias tables: constant-work draws from fixed dispatch weights
MinHash bands: retrieve incident candidates, then check exact overlap
Run-length bitmaps: union, intersect, and subtract alert spans
Project: audit ordered ranks, grid corrections, and majority windows
Check ordered ranks, grid corrections, and majority windows
Project: audit weighted draws, incident candidates, and alert spans
Check weighted draws, incident candidates, and alert spans
Moveable disjoint sets: transfer one shipment without splitting its old tree
Block-cut indexes: separate articulation depots from cyclic road blocks
Kruskal reconstruction trees: answer route bottlenecks through merge ancestors
Zero-suppressed diagrams: share sparse dispatch set families
Count Sketch: estimate signed incident frequencies with row medians
Exponential histograms: estimate failures in a recent event window
Range-mode indexes: combine complete-block modes with fringe candidates
Project: audit member moves, cut depots, bottlenecks, and set families
Check member moves, cut depots, bottlenecks, and set families
Project: audit signed sketches, recent windows, and exact range modes
Check signed sketches, recent windows, and exact range modes
Double-array tries: static incident-code transitions with BASE and CHECK
Hopscotch hashing: keep each shipment near its home bucket
Invertible Bloom tables: peel differences between replica ID sets
De Bruijn graphs: compact non-branching k-mer routes into unitigs
Project: audit static prefixes, neighborhood placement, replica differences, and unitigs
Check prefix, neighborhood, replica, and unitig contracts
Adaptive radix trees: grow byte-edge nodes as incident codes branch
Bit-sliced indexes: filter and sum fixed-width sensor readings
SimHash bands: find near-duplicate incident fingerprints
Minimal acyclic dictionaries: merge equivalent word suffix states
Project: audit adaptive nodes, bit slices, fingerprint bands, and shared word states
Check adaptive nodes, bit slices, SimHash, and acyclic word states
Persistent range MEX: search last occurrences in prefix versions
Range XOR bases: merge linear spans in a segment tree
Affine lazy segment trees: compose range calibration before summing
Min-max heaps: remove either end of one dispatch priority array
Project: audit range MEX, XOR spans, calibration sums, and priority ends
Check range MEX, XOR spans, affine updates, and priority ends
Persistent subarray ranks: subtract prefix frequency trees
Maximum-subarray segment trees: preserve the crossing burst
Li Chao interval offers: limit each line to its valid minutes
All-one frequency buckets: increment, decrement, and read both extremes
Patricia binary routing: compress chains without losing prefix matches
Project: audit ranks, bursts, tariffs, count extremes, and routes
Check persistent ranks, fault bursts, tariff offers, counts, and routes
Successor disjoint sets: skip permanently retired slots
Persistent range-distinct counts: keep only the latest position active
Editable substring fingerprints: join hashes in a segment tree
Sliding medians: expire heap entries by event identity
Ball trees: prune exact nearest-depot search with radius bounds
Project: audit slot, distinct, text, median, and ball indexes