Static Array
Store a fixed number of elements in contiguous memory with constant-time indexing.
Tag
Data-Structures
101 notes
Array Alignment
Place array elements at memory addresses that satisfy hardware and type alignment requirements.
Array Bounds Checking
Validate array indices before access to prevent invalid reads and writes.
Array Union
Combine elements from two arrays into one collection without duplicates.
Array Intersection
Compute the common elements between two arrays.
Difference Array
Represent range updates compactly by storing changes between adjacent values.
Prefix Sum Array
Precompute cumulative sums to answer range sum queries in constant time.
Array Padding
Insert unused space between array elements or groups to control alignment and reduce interference.
Array Vectorization
Process multiple array elements per instruction using SIMD-friendly layout and loops.
Array Tiling
Process multidimensional arrays in small rectangular regions to improve locality.
Array Blocking
Process an array in fixed-size blocks to improve cache locality and batch behavior.
Array Stride Access
Access array elements at regular intervals and understand the effect on locality.
Array Index Mapping
Map logical array positions to physical storage positions.
Array Buffering
Use temporary array storage to stage data before writing it to its final location.
Array Copying
Copy array elements into a new storage block using shallow or deep copy semantics.
Array Memory Layout
Understand how arrays are stored in memory and how layout affects performance.
Array Merge
Merge two sorted arrays into a single sorted array.
Array Deduplication
Remove duplicate values from an array while keeping one representative of each value.
Array Compaction
Remove elements in-place based on a predicate while preserving the remaining elements.
Array Scan
Traverse an array sequentially to compute an aggregate or apply a function.
Array Shuffle
Generate a uniform random permutation of an array in-place.
Array Reversal
Reverse the order of elements in an array in-place using symmetric swaps.
Stable Partition
Partition an array while preserving the relative order of elements inside each group.
Array Partition
Rearrange elements so that those satisfying a predicate appear before others.
Amortized Analysis
Analyze the average cost per operation over a sequence of dynamic array operations.
Capacity Reservation
Preallocate array capacity to reduce reallocations and copying during growth.
Bit-Packed Array
Store small integers or booleans using compact bit-level representation.
Sparse Array
Store only non-default values from a large logical array.
Sliding Window Array
Maintain a contiguous window over an array while moving its left and right boundaries.
Array Rotation
Rotate elements of an array by a given offset in-place or using auxiliary space.
Array Slicing
Represent a contiguous subrange of an array as either a view or a copied array.
Jagged Array
Store rows of different lengths as an array of arrays.
3.7 Probabilistic Data Structures
Bloom filters, cuckoo filters, count-min sketch, HyperLogLog, MinHash, reservoir sampling, skip lists, and treaps as probabilistic structures.
2.7 Order Statistic Structures
Balanced trees augmented with subtree sizes, implicit treaps, wavelet-based order statistics, skip lists, median maintenance, and rank-select structures.
3.6 External-Memory and Database Structures
B-tree indexes, LSM trees, SSTables, write-ahead logs, compaction strategies, cache-oblivious structures, inverted indexes, and external sort/merge.
2.6 Tries and Prefix Structures
Trie variants including compressed, Patricia, ternary, XOR, suffix trees, Aho-Corasick, DAWG, HAMT, and concurrent prefix structures.
3.5 Concurrent and Lock-Free Structures
Mutex-protected structures, lock-free stacks, queues, hash tables, skip lists, CAS primitives, hazard pointers, epoch reclamation, and RCU.
2.5 Disjoint Set Union Variants
Union-find with path compression and union by rank, rollback, parity, weighted, offline, and concurrent DSU designs.
3.4 Geometric Data Structures
KD-trees, R-trees, quadtrees, octrees, Delaunay triangulation, Voronoi diagrams, HNSW, range trees, and sweep line structures.
1.4 Queues and Deques
Array and linked queues, deques, monotonic queues, priority buckets, delay queues, and concurrent queue designs.
3.3 Succinct and Compressed Structures
Bit vectors, rank-select, succinct trees, FM-index, wavelet trees, Huffman and arithmetic coding, roaring bitmaps, and compressed range queries.
3. Specialized, Persistent, Concurrent, and External Structures
Persistence, functional structures, succinct and compressed encodings, geometric indexing, concurrent and lock-free designs, external-memory structures, and probabilistic data structures.
1.3 Stacks
Array and linked stack implementations covering push, pop, monotonic stacks, expression evaluation, and thread-safe variants.
3.2 Functional Data Structures
Immutable lists, stacks, queues, heaps, HAMTs, functional BSTs, lazy evaluation, structural sharing, and deforestation.
2. Advanced Data Structures and Operations
Augmented and self-balancing trees, range query structures, Fenwick and segment tree variants, union-find, tries, and order statistic structures.
1.2 Linked Lists
Singly, doubly, and circular linked lists with operations for insertion, reversal, cycle detection, sorting, and memory pooling.
02. Data Structures
Three-book reference covering core, advanced, and specialized data structures from arrays to concurrent and persistent designs.
3.1 Persistent Data Structures
Path copying, fat nodes, persistent arrays, segment trees, treaps, heaps, union-find, functional queues, and distributed persistence models.
1.1 Arrays and Dynamic Arrays
Fixed and dynamic arrays, resizing strategies, memory layout, cache effects, vectorization, and in-place operations.
1. Core Data Structures and Operations
Memory layout, invariants, and implementation details for arrays, linked lists, stacks, queues, heaps, hash tables, binary search trees, and traversal operations.
1.8 Basic Tree Traversals and Operations
General tree traversal patterns including DFS, BFS, level-order, zigzag, boundary traversal, LCA, serialization, and iterative approaches.
1.7 Binary Search Trees
BST operations, traversals, augmentation, interval trees, order statistics, persistence, and thread-safe BST designs.
1.6 Hash Tables and Sets
Hash functions, collision resolution strategies, open addressing, chaining, dynamic resizing, perfect hashing, concurrent maps, and probabilistic filters.
1.5 Heaps and Priority Queues
Binary, d-ary, Fibonacci, pairing, soft heaps, double-ended structures, tournament trees, and concurrent priority queue designs.
2.4 Segment Tree Variants
Segment tree construction, lazy propagation, beats, 2D variants, persistent and dynamic trees, and hybrid structures combining multiple techniques.
2.3 Fenwick Tree Variants
Fenwick tree construction, point and range updates, multidimensional extensions, order statistics, inversion counting, and persistent variants.
2.2 Range Query Structures
Sparse tables, sqrt decomposition, Mo's algorithm, wavelet trees, merge sort trees, 2D range trees, and offline range query techniques.
2.1 Balanced Search Trees
AVL, red-black, splay, scapegoat, B-tree families, treaps, finger trees, persistent balanced trees, and cache-oblivious layouts.
Multidimensional Array
Store values indexed by two or more dimensions using a linear memory layout.
Circular Array
Array that wraps indices modulo capacity to support efficient cyclic access.
Dynamic Array
Resizable array that grows and shrinks automatically while preserving contiguous storage.
4. Tree and Indexed Search
Tree-based and indexed search: BST, self-balancing trees, tries, suffix structures, segment and range trees, and spatial trees.
Order Maintenance Sort
Maintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.
Fractional Cascading Search
Speed up repeated binary searches across related sorted lists by linking sampled elements between lists.
5.22 Hybrid Hash Structures
Combine hash tables with other data structures to handle skewed distributions, heavy deletions, and mixed workloads.
5.16 Hash-Based Deduplication
Remove duplicate entries from a dataset or stream efficiently using hash sets for membership tracking.
5.13 Count-Min Sketch
Approximate frequency counting for large key streams using a compact probabilistic data structure with bounded error.
5.12 Bloom Filters
Test set membership approximately using a compact bit array and multiple hash functions, with no false negatives and bounded false positives.
5.9 Grouping Keys
Partition a collection into groups by key using a hash map that accumulates values into per-key lists or sets.
5.7 Maps
Build a hash-based map that associates keys with values and supports insert, lookup, delete, and update in expected constant time.
5.6 Sets
Implement a hash-based set for fast membership testing, insertion, and deletion without associated values.
5.3 Collision Handling
Resolve hash collisions using separate chaining or open addressing, with trade-offs in memory, locality, and load tolerance.
5.1 Hash Tables
A data structure that supports fast insertion, lookup, and deletion by mapping keys to bucket positions via a hash function.
3.25 Case Studies
This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms.
3.24 Complexity Analysis
Linked list algorithms are dominated by pointer traversal and constant-time link updates.
3.23 Testing Pointer Code
Pointer code should be tested by checking structure, not only values.
3.22 Edge Cases
Edge cases are inputs that sit near the boundary of an algorithm's assumptions.
3.21 LRU Cache Structure
An LRU cache stores a fixed number of key-value entries and removes the least recently used entry when capacity is exceeded.
3.20 Queue via List
A queue is a first-in, first-out structure.
3.19 Stack via List
A stack is a last-in, first-out (LIFO) structure.
3.18 Iterators
An iterator is an object or procedure that visits the nodes of a linked list one at a time.
3.17 Memory Ownership
Memory ownership describes which part of a program is responsible for creating, linking, unlinking, and destroying a node.
3.16 Intrusive Lists
An intrusive list stores the linkage fields inside the objects being linked.
3.15 Skip Lists
A skip list augments a sorted linked list with multiple levels of forward pointers.
3.14 Persistent Lists
A persistent list is a list that preserves older versions after an update.
3.13 Pointer Aliasing
Pointer aliasing occurs when two or more references point to the same node.
3.12 Dummy Heads (Dummy Nodes)
A dummy head is a fixed node placed before the real head of a singly linked list.
3.11 Insertion Patterns
Insertion adds nodes into a linked list by creating new links while preserving reachability of all existing nodes.
3.10 Deletion Patterns
Deletion removes one or more nodes from a linked list by changing links around them.
3.9 Merge Patterns
Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants.
3.8 Split Patterns
Splitting a linked list means cutting one list into two or more lists while preserving the original nodes.
3.7 Merge Two Sorted Lists
Merging combines two sorted singly linked lists into one sorted list by relinking nodes.
3.6 Fast and Slow Pointers
Fast and slow pointers are two references that traverse the same linked structure at different speeds.
3.5 Cycle Detection
A cycle exists in a linked list when some node’s `next` pointer eventually leads back to a previously visited node.
3.4 Reversal
Reversal transforms a linked list so that the direction of all edges is flipped.
3.3 Sentinel Nodes
A sentinel node is an artificial node placed at the boundary of a linked list.
3.2 Doubly Linked Lists
A doubly linked list is a sequence of nodes where each node stores a value, a reference to the next node, and a reference to the previous node.
3.1 Singly Linked Lists
A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.
Chapter 3. Linked Lists and Pointers
Linked lists are the first data structure in this book where the shape of the data matters as much as the values stored inside it.
Chapter 6. Sorting
Sorting algorithms from fundamental contracts through comparison-based, linear-time, and specialized variants, with selection, external sorting, and correctness analysis.
Chapter 5. Hashing and Maps
Hash tables, hash functions, collision handling, probabilistic structures, and practical design for constant-time key-value access.