Topic domain
Data Structures
Layouts and invariants that make operations cheap.
- Articles
- 80
- Clusters
- 8
- Foundational
- 24
- Intermediate
- 32
- Advanced
- 24
Contiguous storage, dynamic arrays, and deque layouts.
- Row-Major Layout and the Address Arithmetic Behind Indexing
- Growth Policies in Dynamic Arrays and What the Allocator Does With Them
- What a Slice Descriptor Holds and Why It Is Three Words
- Array of Structs or Struct of Arrays
- Sequential Scans, Hardware Prefetch, and the Page Walk
- Ring Buffers and the Cost of Telling Full From Empty
Lists, intrusive chains, and pointer-based layouts.
- Singly Linked Lists: One Pointer per Node and the Cost of Unidirectional Traversal
- Doubly Linked Lists and the Sentinel Header That Removes the Null Checks
- Intrusive Linked Lists: Embedding the Link in the Payload
- Unrolled Linked Lists and the Cost of a Cache Miss per Node
- Index-Based Linked Lists for Relocatable and Persistent Storage
- XOR Linked Lists: One Link Field for Both Directions
Hash Tables
10Hashing, collision policy, and open addressing.
- Separate Chaining and the Load-Factor Threshold
- Open Addressing, Probe Sequences, and the Cost of Deletion
- Linear Probing and the Arithmetic of Primary Clustering
- Hash Functions for Table Indexing: Mixing, Avalanche, and Universal Families
- Double Hashing and Quadratic Probing Without Primary Clustering
- Incremental Rehashing: Spreading a Resize Across Operations
Rotations, height invariants, and ordered maps.
- Height Bounds and the Cost of a Degenerate Search Tree
- Rotations and the In-Order Sequence They Preserve
- Balance Factors, and Why AVL Deletion Cascades
- Red-Black Colouring as a Height Proxy
- B-Tree Node Occupancy, Splits, and the Minimum Degree
- Weight-Balanced Trees and the Ratio That Bounds Depth
Partial orders and efficient extraction.
- Array Layout and the Sift Invariant in Binary Heaps
- Bottom-Up Heap Construction in Linear Time
- Indexed Binary Heaps and the Cost of Decrease-Key
- d-Ary Heaps and How Branching Factor Changes Cost
- Leftist and Skew Heaps: Merging in Logarithmic Time
- Binomial Queues and the Carry Chain of Merges
Prefix sharing and compressed keys.
- Child Representation and the Branching Factor Problem in Tries
- Marking Key Boundaries in a Trie
- Lexicographic Enumeration and Range Scans over a Trie
- Path Compression and the Patricia Trie
- Radix Trees over Fixed-Width Integer Keys
- Adaptive Radix Tree Node Layouts
Disjoint sets, bitsets, and space-efficient indexes.
- Parent-Pointer Forests as the Representation of Disjoint Sets
- Union by Rank and Path Compression: Two Heuristics That Fix the Chain
- The Inverse Ackermann Bound and Why It Is Effectively Constant
- Cache Behaviour and Node Layout in Disjoint-Set Arrays
- Small-to-Large Merging and the DSU on Tree Technique
- Rollback Union-Find and Offline Dynamic Connectivity
Filters, sketches, and bounded-error membership.
- How a Bloom Filter Trades Bits for a False-Positive Rate
- Counting Bloom Filters and the Price of Supporting Deletion
- Cuckoo Filters: Fingerprint Placement and the Load-Factor Ceiling
- Deriving k Bloom Filter Probes from Two Hash Words
- Blocked and Partitioned Bloom Filters for Cache-Resident Probes
- HyperLogLog: Estimating Cardinality from a Register Array
All Data Structures articles
- Oct 23, 2026 Balance Factors, and Why AVL Deletion Cascades How two bits per node encode the AVL invariant, why an insertion repair stops at the first rotation while a deletion repair can climb to the root, and what the child balance factor decides.
- Oct 21, 2026 Singly Linked Lists: One Pointer per Node and the Cost of Unidirectional Traversal How a head pointer and a next field support O(1) splicing, why deletion needs the predecessor, and what pointer chasing costs on a modern cache hierarchy.
- Sep 22, 2026 Leftist and Skew Heaps: Merging in Logarithmic Time How a rank stored per node bounds the right spine, why skew heaps drop the rank and still amortise to logarithmic merge, and what the recursion costs.
- Sep 16, 2026 Multibit Tries and Longest-Prefix Matching for Address Lookups Walking one bit per level is too slow for router tables. Stride compression, prefix expansion, and stored prefix lengths trade table size against lookup depth under a fixed memory budget.
- Sep 11, 2026 Lock-Free Linked Lists and the Reclamation Problem Compare-and-swap can insert and delete on a singly linked list without locks, but freeing a removed node requires hazard pointers or epoch tracking to stop reuse.
- Sep 9, 2026 Fibonacci Heaps and the Amortised Case for Decrease-Key How deferred consolidation makes meld and decrease-key constant amortised, what the potential function measures, and why the theoretical win rarely survives contact with memory.
- Jul 31, 2026 Monotone Integer Keys: Bucket Queues and Radix Heaps When extracted keys never decrease, an array of buckets beats comparison-based heaps; how circular bucket arrays and radix heaps exploit integer bounds.
- Jul 9, 2026 Cache Behaviour and Node Layout in Disjoint-Set Arrays Why a find is a dependent-load chain, how index width and array splitting change the number of cache lines touched, and what key remapping costs before the first union.
- Jun 26, 2026 Bottom-Up Heap Construction in Linear Time Why sifting down from the middle of the array builds a heap in O(n) rather than O(n log n), and how the node-counting argument bounds the total work.
- Jun 21, 2026 Concurrent Readers on a Mutating Trie Lookups traverse many dependent loads, so per-node locking is untenable. How publish-then-swap, deferred reclamation, and path copying keep readers safe while nodes grow and split.
- Jun 11, 2026 Immutable Sequences and Structural Sharing in Radix-Balanced Vectors How a fixed branching factor turns an array into a shallow tree whose updates copy one path, and what the size table and tail slot buy the index.
- Jun 9, 2026 d-Ary Heaps and How Branching Factor Changes Cost Trading comparisons per level against levels per sift, why four children often beats two on real hardware, and where the arithmetic stops fitting in a register.
- Jun 8, 2026 Adaptive Radix Tree Node Layouts ART keeps fan-out high without paying a 256-way node per prefix: four node widths, a 256-entry indirection table, path compression inside the header, and lazy expansion of leaves.
- Jun 5, 2026 Erasing From the Middle: Compaction and the Order It Destroys Why removal from a contiguous array costs a shift, when swap-and-pop is the right substitute, and how tombstone markers defer the cost without hiding it.
- Jun 1, 2026 XOR Linked Lists: One Link Field for Both Directions Storing the difference of the two neighbour addresses halves link storage and forces traversal to carry two cursors, which breaks under debugging tools and section boundaries.
- May 20, 2026 Growing and Ageing a Filter Without Rebuilding It Scalable Bloom filters add slices with tightening error instead of rehashing, and decaying sketches replace deletion with a time constant that bounds the effective window.
- May 18, 2026 Open Addressing, Probe Sequences, and the Cost of Deletion Why open-addressed tables store keys in the slot array, how a probe sequence defines lookup, and why deletion requires tombstones or backward shifting.
- May 7, 2026 Radix Trees over Fixed-Width Integer Keys Indexing by bit fields instead of by bytes turns a trie into a fixed-height array of tables. Why integer radix trees need no rebalancing, how their height is computed, and where they lose to hash tables.
- May 1, 2026 Bitset Representation and Word-Level Rank and Select How a bitvector is stored as words, how popcount turns a prefix count into a handful of instructions, and what the two-level directories for rank and select cost in bits per element.
- Apr 22, 2026 Cuckoo Filters: Fingerprint Placement and the Load-Factor Ceiling How two-bucket cuckoo hashing with stored fingerprints supports deletion in less space than a counting Bloom filter, and why displacement fails near full occupancy.
- Apr 9, 2026 Incremental Rehashing: Spreading a Resize Across Operations How two tables and a migration cursor turn an O(n) resize pause into constant work per operation, and what lookups must do while both tables are live.
- Apr 8, 2026 Child Representation and the Branching Factor Problem in Tries A trie costs one child lookup per key byte, so the node layout decides memory and speed. Compares dense arrays, sorted and linked child lists, bitmaps with rank, and double-array layouts.
- Mar 25, 2026 From Suffix Trie to Suffix Array: Implicit Nodes and Intervals A suffix trie over a text is quadratic in nodes; a suffix tree keeps only branching positions; a suffix array replaces the nodes with sorted offsets plus an LCP array. What is gained and lost at each step.
- Jan 10, 2026 Indexed Binary Heaps and the Cost of Decrease-Key Why changing a key in place needs a handle from element to heap slot, how the position map is maintained through sifts, and what lazy deletion trades away.
- Jan 7, 2026 Separate Chaining and the Load-Factor Threshold How a bucket array with per-bucket lists produces expected constant-time lookup, what the load factor controls, and why chained tables keep working above a load of one.
- Dec 29, 2025 Counting Bloom Filters and the Price of Supporting Deletion Replacing bits with small saturating counters makes removal possible, but residue, overflow, and spurious decrements each introduce a distinct failure.
- Dec 11, 2025 Rollback Union-Find and Offline Dynamic Connectivity How to undo a union by recording only the parent slot it overwrote, and how a segment tree over time turns edge insertions and deletions into a stack of reversible merges.
- Dec 2, 2025 Subtree Deduplication and the DAWG Two trie nodes with identical subtrees are indistinguishable, so one of them is redundant. Bottom-up merging turns a trie into a DAG whose size depends on the number of distinct suffixes, not prefixes.
- Dec 2, 2025 Union by Rank and Path Compression: Two Heuristics That Fix the Chain How attaching the smaller tree under the larger bounds forest height, how rewriting parent links during a find flattens future traversals, and why the two heuristics must be analysed together.
- Oct 15, 2025 Free Lists: Threading Reuse Through the Blocks an Allocator Has Released How an allocator stores its free list inside the freed memory itself, why coalescing needs boundary tags, and what size-class segregation does to fragmentation.
- Oct 10, 2025 Array Layout and the Sift Invariant in Binary Heaps How a complete binary tree maps onto a flat array with no pointers, why the heap property is a partial order, and what sift-up and sift-down actually cost.
- Sep 25, 2025 Blocked and Partitioned Bloom Filters for Cache-Resident Probes Confining the k probes of a filter to one cache line, or to one slice of the array, changes the error rate by a measurable factor and the memory behaviour by an order of magnitude.
- Sep 18, 2025 Array of Structs or Struct of Arrays How element stride decides which fields a scan pulls into cache, when splitting a record into parallel columns pays, and what the split costs elsewhere.
- Aug 31, 2025 Cuckoo Hashing and the Guarantee of Two Probes How two hash functions and a displacement rule give worst-case constant lookup, why insertion can cycle, and how a stash or a larger bucket count makes it succeed.
- Aug 28, 2025 Deque Layouts and the Cost of Push at Both Ends Why a double-ended queue cannot be a plain growable array, how an array of fixed blocks gives O(1) at both ends, and what the extra indirection costs an index.
- Aug 25, 2025 How a Bloom Filter Trades Bits for a False-Positive Rate The bit-array layout behind Bloom filters, the derivation of the false-positive probability, and how the bits-per-key budget fixes the achievable error.
- Aug 13, 2025 Row-Major Layout and the Address Arithmetic Behind Indexing How a pair of subscripts becomes one byte offset, why the last subscript varies fastest, and what traversal order does to cache-line consumption.
- Jul 29, 2025 Hash Functions for Table Indexing: Mixing, Avalanche, and Universal Families What a table hash must satisfy beyond producing an integer, why identity hashing fails on power-of-two tables, and how multiply-shift and finalizers repair weak input bits.
- Jul 15, 2025 Wavelet Trees and Range Queries on Sequences How recursive bitvector partitioning answers range counting, quantile, and rank queries on a static sequence, and why the space is n log σ bits rather than an index per value.
- Jun 29, 2025 SwissTable Control Bytes and Group-Wise Probing How a one-byte tag per slot lets a lookup reject fifteen candidates with one SIMD comparison, and why metadata separate from keys changes the memory hierarchy.
- Jun 10, 2025 Path Compression and the Patricia Trie Single-child chains inflate a trie by one node per byte. Patricia compression stores only branching nodes plus a skip value, changing lookup, insertion, and deletion in specific ways.
- May 29, 2025 Skip Lists: Express Lanes over a Sorted Chain Layered forward pointers turn a linear scan into an expected O(log n) search, and the geometric level distribution is what makes the expected bound hold without rebalancing.
- May 23, 2025 B-Tree Node Occupancy, Splits, and the Minimum Degree Why a B-tree fixes node size rather than height, how a split propagates to the root, and what the minimum degree buys in depth versus split frequency.
- May 12, 2025 Index-Based Linked Lists for Relocatable and Persistent Storage Replacing pointers with offsets makes a linked structure relocatable, mmap-safe, and serialisable, and forces explicit handling of free slots and stale indices.
- Apr 24, 2025 Bit-Packed Integer Arrays and Vectorized Decoding How fixed-width packing puts k-bit integers into words, why decoding costs more than encoding, and how SIMD shuffles make unpacking cheap.
- Apr 22, 2025 Marking Key Boundaries in a Trie A trie node must distinguish a prefix from a stored key. The terminal marker costs one bit, one child slot, or one pointer depending on layout, and each choice changes lookup and iteration.
- Apr 22, 2025 Move-to-Front Lists and the Working-Set Bound on Sequential Search Reordering a list on every access costs one splice and buys a factor-two competitive bound against any static ordering, with a cost that depends on the access distribution.
- Apr 5, 2025 Parent-Pointer Forests as the Representation of Disjoint Sets How a partition of n elements is stored as a single array of parent indices, what find and union do to that array, and which questions the representation cannot answer.
- Feb 24, 2025 HyperLogLog: Estimating Cardinality from a Register Array How stochastic averaging over harmonic means turns a fixed array of small registers into a cardinality estimate with roughly 1.04/sqrt(m) relative error.
- Feb 24, 2025 Lexicographic Enumeration and Range Scans over a Trie A trie yields keys in sorted order without a sort step. How depth-first traversal, ordered child storage, and iterator state interact, and why range scans cost what they cost.
- Feb 22, 2025 Composing Probabilistic Checks: Why Error Budgets Do Not Add Chaining filters and sketches multiplies false positives instead of summing them, correlation between stages breaks the union bound, and the pipeline error is dominated by the weakest stage.
- Dec 10, 2024 Count-Min Sketches and the Bias of Always Rounding Up A fixed grid of counters answers frequency queries with a one-sided error bounded by the stream length, and conservative updates cut the excess without changing the guarantee.
- Nov 29, 2024 Rotations and the In-Order Sequence They Preserve How a single rotation rewires three pointers while keeping key order, why some violations need two rotations, and what a rotation cannot repair.
- Oct 23, 2024 Small-to-Large Merging and the DSU on Tree Technique Why merging the smaller container into the larger bounds total moves to n log n, and how the same accounting answers subtree queries by reusing one mutable structure.
- Oct 7, 2024 Red-Black Colouring as a Height Proxy How one bit per node encodes a 2-3-4 tree, why the colour rules make insertion repair terminate early, and where the two-to-one height constant comes from.
- Oct 2, 2024 Robin Hood Hashing and the Distribution of Probe Lengths How equalizing displacement from the home slot bounds the worst probe sequence, why the variance collapses, and what early termination buys on lookups.
- Sep 11, 2024 Order-Statistic Augmentation and Rank Queries How a subtree count maintained through every rotation answers rank and select in logarithmic time, and why the aggregate must be recomputable from children alone.
- Aug 19, 2024 Splaying: Amortized Restructuring Without Stored Balance How a splay step moves an accessed node to the root, why zig-zig pairing matters, and how a potential function yields O(log n) amortized access with zero metadata.
- Aug 1, 2024 Growth Policies in Dynamic Arrays and What the Allocator Does With Them Why doubling beats incremental growth, how realloc can extend a buffer in place, and which costs a growth policy actually controls.
- Jul 31, 2024 Linear Probing and the Arithmetic of Primary Clustering Why probing consecutive slots produces runs of occupied cells, how those runs change the expected probe count, and how backward-shift deletion repairs a probe chain.
- Jun 16, 2024 Hash Flooding and the Case for Keyed Hash Functions Why a predictable hash lets an attacker collapse a table to a linked list, how SipHash and per-process seeding restore the expected bound, and what the defence costs.
- Jun 9, 2024 Balanced Parentheses and Succinct Tree Navigation How a tree becomes a 2n-bit parentheses string, which rank and select combinations recover the parent and subtree boundaries, and what the extra index buys.
- Jun 5, 2024 Unrolled Linked Lists and the Cost of a Cache Miss per Node Packing several elements per node cuts pointer chases by the node capacity, and the block size that minimises total cost follows from a cache line and a word.
- Jun 3, 2024 The Inverse Ackermann Bound and Why It Is Effectively Constant How the α(n) function is defined, why the amortized cost of a disjoint-set sequence lands there, and what the matching lower bound says about improving it.
- May 14, 2024 Path Copying and the Cost of Persistence in Balanced Trees Why an update to an immutable balanced tree rewrites one path, how the sharing structure changes the balance invariants, and where the allocation cost actually goes.
- Mar 26, 2024 Ring Buffers and the Cost of Telling Full From Empty Why a fixed-size queue needs one extra slot, how the monotonic counter variant trades a mask for a free bit, and where each breaks under concurrency.
- Mar 20, 2024 Doubly Linked Lists and the Sentinel Header That Removes the Null Checks Why two pointers buy constant-time removal from a node alone, how a circular sentinel collapses the special cases, and what the extra word per node costs.
- Mar 19, 2024 Elias-Fano Encoding for Monotone Integer Sequences How splitting each value into a high and a low part turns a sorted sequence into one bitvector plus a packed array, and why this beats a plain array for prefix queries.
- Dec 29, 2023 Sequential Scans, Hardware Prefetch, and the Page Walk What happens between a linear loop over an array and the memory it reads, why huge pages change the cost, and where a scan stops being sequential.
- Dec 8, 2023 Height Bounds and the Cost of a Degenerate Search Tree Why the worst-case depth of a binary search tree, not its average depth, sets lookup cost, and what a balance invariant has to constrain to fix it.
- Dec 7, 2023 Weight-Balanced Trees and the Ratio That Bounds Depth Why subtree size is a usable balance weight, how the size ratio is chosen, and why size balance makes join and split the natural primitives.
- Oct 19, 2023 Deriving k Bloom Filter Probes from Two Hash Words Why the h1 + i·h2 construction preserves the false-positive bound, where the independence assumption breaks, and what enhanced double hashing repairs.
- Oct 19, 2023 Treaps: Priorities, Expected Depth, and Rotation-Only Updates How assigning a random priority per key turns a binary search tree into a heap-ordered structure with a probabilistic height bound, and what deletion by rotation costs.
- Oct 12, 2023 What a Slice Descriptor Holds and Why It Is Three Words The pointer, length and capacity triple that makes a slice cheap to pass, how subslicing shares storage, and where the shared-buffer aliasing shows up.
- Aug 18, 2023 Double Hashing and Quadratic Probing Without Primary Clustering How per-key strides and triangular offsets break the runs that linear probing creates, what each costs in arithmetic, and why the table size must cooperate.
- Apr 27, 2023 Intrusive Linked Lists: Embedding the Link in the Payload How intrusive chains eliminate per-element allocation and let one object sit on several lists at once, at the cost of type knowledge and ownership rules.
- Apr 23, 2023 Merging Probabilistic Sketches Across Shards Union and sum are the only safe merge operations, they require identical parameters and hash seeds, and the error of a merged estimate grows in a way single-sketch sizing hides.
- Mar 31, 2023 Binomial Queues and the Carry Chain of Merges Why storing trees of size 2^k makes merge look like binary addition, how extract-min decomposes the forest, and what the lazy structure costs in pointers.
- Jan 10, 2023 Min-Max Heaps and Double-Ended Extraction How alternating min and max levels let one array serve both ends of a priority queue, why sift-down needs two directions, and what the layout gives up.
- Nov 18, 2022 Pairing Heaps and the Two-Pass Merge How a self-adjusting heap replaces rank bookkeeping with a left-to-right then right-to-left merge, why melding is constant time, and what the amortised bounds actually are.