More Data Structures
Lists, hashing, balanced trees, string structures and range-query structures. Arrays, linked lists, stacks, queues, hash tables, binary trees, BSTs and heaps have their own pages earlier in this subject.
This is an overview — pick a sub-topic below.
Sub-topics (21)
Strings as a Data Structure
Sequences of characters — arrays with special operations (search, compare, substring).
Singly Linked Lists
Each node points to the next; the list ends with null.
Doubly Linked Lists
Nodes point both forward and backward.
Circular Linked Lists
The last node points back to the first.
Deques
Double-ended queues: insert and remove at both ends in $O(1)$.
Hash Maps
Key → value storage with average $O(1)$ lookup using a hash function.
Sets
Collections of unique elements with fast membership tests.
AVL Trees
Self-balancing BSTs where subtree heights differ by at most 1, restored by rotations.
Red-Black Trees
Self-balancing BSTs with node colours and rules ensuring height ≤ $2\log_2(n+1)$.
B-Trees
Balanced trees with many keys per node, designed for disks and databases.
B+ Trees
B-trees that store all values in linked leaves, with internal nodes only for routing.
Tries
Prefix trees storing strings character by character.
Suffix Trees
A compressed trie of all suffixes of a string.
Suffix Arrays
All suffixes of a string sorted, stored as starting indices — a compact alternative to suffix trees.
Segment Trees
A tree over an array that answers range queries (sum, min, max) and point updates in $O(\log n)$.
Fenwick Trees
Binary Indexed Trees: prefix sums with point updates in $O(\log n)$ using low-bit tricks.
Sparse Tables
Precomputed answers for power-of-two ranges giving $O(1)$ range-minimum queries on static arrays.
Disjoint-Set Union
Union-Find: track which elements are in the same group, with near-$O(1)$ union and find.
Graph Representations
Adjacency matrix ($O(V^2)$ space, $O(1)$ edge check) vs adjacency list ($O(V+E)$ space, fast neighbour iteration).
Bloom Filters
A compact probabilistic set: "definitely not present" or "probably present".
LRU Cache
A fixed-size cache that evicts the Least Recently Used item.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.