Data Structures
Algorithms and structures for organizing data for efficient access.
Data structure entries describe core containers and the operations that make algorithms faster or simpler.
Hash Table
Stores key-value pairs in buckets chosen by a hash function for fast average-case lookup.
Binary Search Tree
Stores ordered keys in a tree where left descendants are smaller and right descendants are larger.
Heap
Maintains a partial order so the minimum or maximum item can be found quickly.
Trie
Stores strings by sharing prefixes along paths through a tree.
B-Tree
Stores sorted keys in wide balanced nodes for efficient disk or page access.
Bloom Filter
Tests set membership with a compact bit array that allows false positives but not false negatives.
Fenwick Tree
Maintains prefix aggregates in an array using index ranges encoded by low bits.
Red-Black Tree
Maintains a balanced binary search tree with color rules.
Segment Tree
Maintains aggregate values over intervals by storing summaries in a binary tree.
Union-Find
Maintains disjoint sets with near-constant-time find and union operations.
Quadtree
Indexes 2D space by recursively subdividing regions into four quadrants.
Octree
Indexes 3D space by recursively subdividing regions into eight octants.
k-d Tree
Indexes points by recursively splitting space along coordinate axes.
R-Tree
Indexes rectangles or spatial objects with nested bounding boxes.
Spatial Hash
Maps spatial positions into grid cells stored in a hash table.
Sparse Table
Precomputes overlapping power-of-two ranges for fast static range queries.
Rope
Stores long strings as a tree of smaller chunks for efficient edits and concatenation.
Circular Buffer
Stores a fixed-size queue by wrapping read and write positions around an array.
Deque
Stores items so insertion and removal are efficient at both the front and the back.
Priority Queue
Stores items so the highest- or lowest-priority item can be removed efficiently.
Graph Adjacency List
Represents a graph by storing each node with the neighbors reachable from it.
Graph Adjacency Matrix
Represents graph edges with a matrix indexed by source and destination nodes.
Directed Acyclic Graph
Represents directed dependencies with no cycle following edge directions.
AVL Tree
Maintains a binary search tree with strict height balance after updates.
Splay Tree
Moves recently accessed nodes to the root using rotations.
Treap
Combines binary search tree ordering with random heap priorities.
Skip List
Maintains sorted items with multiple randomized forward-pointer levels.
LRU Cache
Evicts the least recently used item when capacity is exceeded.
Persistent Segment Tree
Keeps previous segment tree versions by copying only nodes along update paths.
Wavelet Tree
Indexes sequences so rank, select, and range queries can be answered compactly.
Suffix Tree
Stores all suffixes of a string in a compressed trie for fast substring queries.
Suffix Array
Stores suffix starting positions in lexicographic order for compact string indexing.
Cartesian Tree
Cartesian Tree organizes data around a query, update, ordering, or approximation invariant.
Interval Tree
Interval Tree organizes data around a query, update, ordering, or approximation invariant.
Order Statistic Tree
Order Statistic Tree organizes data around a query, update, ordering, or approximation invariant.
Van Emde Boas Tree
Van Emde Boas Tree organizes data around a query, update, ordering, or approximation invariant.
Radix Tree
Radix Tree organizes data around a query, update, ordering, or approximation invariant.
Patricia Trie
Patricia Trie organizes data around a query, update, ordering, or approximation invariant.
Merkle Patricia Trie
Merkle Patricia Trie organizes data around a query, update, ordering, or approximation invariant.
Count-Min Sketch
Count-Min Sketch organizes data around a query, update, ordering, or approximation invariant.
HyperLogLog
HyperLogLog organizes data around a query, update, ordering, or approximation invariant.
Cuckoo Hash Table
Cuckoo Hash Table organizes data around a query, update, ordering, or approximation invariant.
Robin Hood Hashing
Robin Hood Hashing organizes data around a query, update, ordering, or approximation invariant.
Min-Max Heap
Min-Max Heap organizes data around a query, update, ordering, or approximation invariant.
Fibonacci Heap
Fibonacci Heap organizes data around a query, update, ordering, or approximation invariant.
Pairing Heap
Pairing Heap organizes data around a query, update, ordering, or approximation invariant.
Cuckoo Hashing
Resolves hash collisions by moving keys between multiple candidate buckets.
X-Fast Trie
X-Fast Trie addresses predecessor queries by hashing binary trie prefixes to search integer keys by level.
Y-Fast Trie
Y-Fast Trie addresses predecessor queries by combining x-fast trie representatives with balanced buckets.
Judy Array
Judy Array addresses sparse array storage by using adaptive trie nodes tuned for sparse integer keys.
Cover Tree
Cover Tree addresses nearest-neighbor search by organizing points in nested metric covers across distance scales.
BK-Tree
Indexes metric-space items by storing children at discrete distances from each node.
Binomial Heap
Maintains a mergeable priority queue as a forest of binomial trees.
Compressed Sparse Row
Stores a sparse matrix by keeping nonzero values, column indices, and row offsets.
Edge List Representation
Represents a graph as a list of edges, optionally with weights or other edge data.
Bitset Operations
Represents dense sets as machine-word bits so membership and set operations run in word-sized chunks.
Persistent Union-Find
Persistent Union-Find addresses versioned connectivity by recording parent and rank changes so older connectivity states remain queryable.
Balanced KD-Tree Construction
Builds a k-d tree by recursively splitting points near the median along alternating dimensions.
Approximate KD-Tree Search
Approximate KD-Tree Search addresses approximate nearest-neighbor search by pruning tree branches using distance bounds and an approximation tolerance.
Leftist Heap
Maintains a mergeable heap by keeping the shortest null path on the right spine.
Skew Heap
Maintains a self-adjusting mergeable heap by swapping children during every meld.
Euler Tour Tree
Euler Tour Tree addresses dynamic forest connectivity by representing each tree as a sequence maintained by a balanced tree.
Link-Cut Tree
Link-Cut Tree addresses dynamic tree path queries by using splay trees to expose and update root-to-node paths.
Range Tree
Supports orthogonal range queries with a layered balanced-tree structure.