Rust DSA: Complete Roadmap
118 Topics · 4-Month Plan · Data Structures & Algorithms in Rust
Master every fundamental data structure and algorithm implemented in Rust. 118 topics across 4 months — one per day. From Vec and Linked Lists to Segment Trees, Dijkstra's, Dynamic Programming, and Aho-Corasick. End goal: build a Redis-compatible Key-Value store using all 40 data structures you implemented.
Foundations
Build every core data structure from scratch in Rust. Linear structures force you to master Box<T> and ownership. Hash structures teach you to fuse data structures for O(1) operations. Trees introduce recursive enums and Rc<RefCell<T>>. Every implementation fights the borrow checker — and that's the point.
Week-by-Week Plan
Linear Structures
Array/Slice (indexing, bounds checking, stack memory layout), Dynamic Array/Vec (heap allocation, 2x growth factor, capacity vs length), Singly Linked List (Box<T>, ownership transfer, node traversal), Doubly Linked List (Rc<RefCell<T>>, interior mutability, borrow checker), Stack (LIFO, push/pop, call stack simulation, overflow detection), Queue (FIFO, front/rear pointers, circular array version), Deque/VecDeque (amortized O(1) both ends, circular buffer technique). Build: implement all 7 from scratch with Display and Iterator trait impls. Key insight: fighting the borrow checker teaches Rust faster than any tutorial.
Hash & Cache Structures
Circular Buffer (ring buffer, modulo indexing, fixed-size stream processing), HashMap (hashing fn, bucket arrays, load factor, rehashing), HashSet (uniqueness guarantee, set ops: union/intersection/diff), Hash Table from scratch (collision handling: chaining vs open addressing), LRU Cache (HashMap + Doubly Linked List fusion, O(1) get/put). Capstone: LRU Cache combines every ownership trick from Days 1–11. Implement the full O(1) version — this exact pattern appears in system design interviews.
Tree Structures
Binary Tree (recursive enum, Box<T>, pre/in/post-order traversals), BST (ordering invariant, insert/delete/search, O(h) ops), AVL Tree (balance factor, LL/RR/LR/RL rotations, guaranteed O(log n)), Red-Black Tree (5 color rules, rebalancing cases — this is BTreeMap internally), Segment Tree (range queries, lazy propagation, point updates), Fenwick Tree/BIT (prefix sums, lowbit trick, O(log n) updates), Trie/Prefix Tree (autocomplete, word validation, string storage), Suffix Tree (Ukkonen's algorithm, all substrings, O(n) build), B-Tree (disk-friendly, multi-key nodes, database pages), B+ Tree (leaf linking, all data in leaves, range scans). Build each with insert/search/delete. Implement Display for every tree.
Heaps & Graph Representations
Heap Min/Max (heapify up/down, BinaryHeap<T>, priority queue abstraction), Fibonacci Heap (lazy merging, decrease-key O(1) amortized, used in Dijkstra's), Treap (BST + heap priority combined, randomized balancing), Splay Tree (self-adjusting, recently accessed nodes rise to root), K-D Tree (spatial partitioning, k-nearest neighbor search). Graph representations: Adjacency Matrix (2D Vec, O(1) edge lookup, dense graphs), Adjacency List (Vec<Vec<usize>>, sparse memory-efficient, preferred), Weighted Graph (edge structs with weights, cost modeling), Directed Graph/Digraph (in/out degree tracking, cycle detection, DAG representation). Build: create a graph library crate with all 4 representations behind a unified trait.
Resources4
Primary reference for ownership, Box<T>, Rc<RefCell<T>>, and trait patterns used in every structure.
Canonical resource explaining why linked lists in Rust require Rc<RefCell<T>>. Read alongside Days 3–4.
Step-by-step animations for every structure in Month 1. Watch the animation before implementing.
After implementing each structure, read the standard library source. BTreeMap uses Red-Black Tree. VecDeque is a circular buffer.
Trees & Graphs
Advanced tree variants and the full suite of graph algorithms. From Union-Find to max-flow, Kruskal to Tarjan's SCC. Every algorithm here powers real-world systems: databases, maps, compilers, network routers. Implement them in Rust and build a unified graph library crate.
Week-by-Week Plan
Advanced & Specialized Structures
Union-Find/DSU (path compression, union by rank, O(α) amortized — you will use this in Kruskal's), Bloom Filter (probabilistic membership, bit arrays, false positives tradeoff), Skip List (probabilistic O(log n) search, Redis sorted sets use this), Sparse Table (immutable RMQ, O(n log n) build, O(1) query), Disjoint Sparse Table (overlap-friendly RMQ, cache efficient), Rope (split/merge tree for string manipulation, editor buffer data structure), Persistent Segment Tree (immutable versioned history, functional updates), Van Emde Boas Tree (O(log log U) integer set operations), Radix Tree/Patricia Trie (compressed trie, IP routing tables, key-value stores). Build: implement Union-Find perfectly — it's a building block for Kruskal's MST in Week 2 of this phase.
Sorting Algorithms
All 12 sorts: Bubble Sort (adjacent swapping, O(n²), best case O(n)), Selection Sort (min-finding per pass, minimal writes), Insertion Sort (shifting, O(n²), best for nearly sorted data), Merge Sort (O(n log n), stable, divide & conquer, extra O(n) space), Quick Sort (partitioning, pivot selection strategies, O(n log n) average), Heap Sort (heapify then extract, O(n log n), in-place), Counting Sort (O(n+k), integer keys only, non-comparison), Radix Sort (digit-by-digit, LSD vs MSD, O(nk)), Bucket Sort (distribution-based, O(n) average, uniform float input), Tim Sort (Rust's actual .sort() — merge + insertion hybrid, real-world optimized), Shell Sort (gap sequences, improved insertion, O(n^1.3) average), Cycle Sort (minimum memory writes, O(n²), in-place). Build: benchmark all 12 on the same Vec<i32>. Measure cache effects, branch mispredictions, and compare against Rust's built-in .sort().
Searching Algorithms
Linear Search (O(n) brute force, unsorted arrays), Binary Search (O(log n), sorted requirement, iterative vs recursive — compare with std::slice::binary_search_by), Ternary Search (unimodal functions, two midpoints, O(log₃ n)), Exponential Search (unbounded/infinite arrays, find range then binary search), Interpolation Search (O(log log n) for uniformly distributed data), Jump Search (O(√n) block skipping then linear). Build: implement binary search without any off-by-one errors — write property-based tests with proptest to verify correctness on 10,000 random sorted arrays.
Graph Algorithms
BFS (level-order traversal, shortest path unweighted, visited set), DFS (recursion vs explicit stack, pre/post-order, backtracking), Dijkstra's (priority queue, single-source shortest path, no negative weights), Bellman-Ford (handles negative weights, detects negative cycles in O(VE)), Floyd-Warshall (all-pairs shortest path, DP on intermediate nodes), A* Search (heuristic + cost, admissible heuristics, grid pathfinding), Kruskal's MST (sort edges + Union-Find, greedy), Prim's MST (greedy vertex growing, priority queue, better for dense graphs), Topological Sort (DAG ordering, Kahn's BFS algorithm, cycle detection), Tarjan's SCC (strongly connected components, low-link values), Kosaraju's SCC (two-pass DFS, transpose graph approach), Articulation Points (bridges and cut vertices, DFS discovery times), Bipartite Check (2-coloring via BFS/DFS, odd-cycle detection), Ford-Fulkerson (max flow, augmenting paths, residual graph), Edmonds-Karp (BFS-based max flow, O(VE²) guaranteed), Johnson's Algorithm (reweighting + Dijkstra, all-pairs with negative weights). Build: a full graph library crate exposing all algorithms via a clean API.
Resources3
Best free reference for graph algorithms. Tarjan's SCC, Floyd-Warshall, Max Flow — all explained with worked examples and complexity proofs.
Read petgraph's source code after implementing your own graphs. See how Rust experts handle ownership in real graph structures.
Animate Dijkstra's, Bellman-Ford, Floyd-Warshall, and MST algorithms step-by-step before implementing.
DP & Problem Solving
Dynamic programming, greedy algorithms, and backtracking — the three problem-solving paradigms that separate competitive programmers from everyone else. DP is the hardest conceptual shift: learning to see overlapping subproblems where others see recursion. By the end you'll recognize DP patterns in new problems and know when greedy beats DP.
Week-by-Week Plan
DP Fundamentals
Fibonacci memoized (top-down HashMap memo vs bottom-up Vec — measure the difference), 0/1 Knapsack (2D DP table, capacity constraint, tabulation + traceback for item selection), LCS — Longest Common Subsequence (2D table construction, O(nm), full string reconstruction), LIS — Longest Increasing Subsequence (O(n²) naive then O(n log n) with patience sort/binary search), Edit Distance/Levenshtein (insert/delete/replace cost matrix, practical for spell checking and diff tools). Build: implement all 5 in both top-down (HashMap memo) and bottom-up (Vec) forms. Write unit tests that run both variants on identical inputs and assert equal outputs.
Advanced Dynamic Programming
Matrix Chain Multiplication (interval DP, optimal parenthesization, O(n³)), Coin Change (unbounded knapsack variant — both minimum coins AND count of ways), Rod Cutting (revenue maximization, recursive + memoized vs bottom-up), Egg Drop Problem (min/max DP, binary search optimization to O(n log n)), Subset Sum (boolean DP table, NP-complete exploration), Palindrome Partition (interval DP, precompute palindrome table, minimum cuts), Burst Balloons (interval DP — think about the LAST balloon, not the first — this reversal is the key insight), Word Break (string segmentation DP + trie optimization), Wildcard Matching (2D DP, handle * as zero-or-more chars and ? as exactly one). Pattern drill: before coding, write the recurrence relation and state definition in comments.
Greedy Algorithms
Activity Selection (interval scheduling maximization, sort by end time, proof of greedy optimality), Huffman Coding (variable-length prefix codes, min-heap construction with BinaryHeap<T> — implement full compression + decompression), Fractional Knapsack (sort by value/weight ratio, split items allowed, O(n log n)), Job Sequencing with Deadlines (maximize profit, greedy slot assignment using Union-Find), Egyptian Fraction (greedy decomposition: always take largest unit fraction ≤ remainder). Build: compress a text file using Huffman — measure compression ratio and compare with gzip.
Backtracking
N-Queens (constraint satisfaction, pruning by row/column/diagonal — implement for n=1..15 and benchmark how pruning reduces nodes explored vs brute force), Sudoku Solver (constraint propagation: eliminate, naked singles, hidden singles, then backtrack only when stuck), Permutations (swap-based generation and lexicographic generation, Heap's algorithm, O(n!)), Combinations/Subsets (power set via include/exclude, k-choose-r with pruning), Rat in a Maze (grid backtracking, 4-directional DFS, visited matrix to avoid cycles), Word Search (DFS on 2D grid, in-place cell marking for O(1) visited check, 4-directional and 8-directional variants). Optimization focus: reduce allocations — prefer iterators and in-place mutation over creating new Vec at each recursion level.
Resources3
Solve 2–3 problems per DP pattern after implementing the core algorithm. Focus on Easy/Medium until patterns click.
Rigorous DP explanations with recurrence proofs. Essential for interval DP (Matrix Chain, Burst Balloons).
Chapter 8 (Dynamic Programming) is the clearest printed explanation of DP. Chapter 7 covers combinatorial search and backtracking.
Advanced Mastery
String algorithms, number theory, bit manipulation, and divide & conquer. The final stretch before the capstone. After Day 118 you hold the complete toolkit: 40 data structures and 78 algorithms — enough to build a production-grade Redis-compatible KV store or a database engine in Rust from scratch.
Week-by-Week Plan
String Algorithms
KMP Search (failure function / LPS array construction, O(n+m) guaranteed, zero backtracking in the text), Rabin-Karp (rolling polynomial hash, O(n+m) average, natural extension to multi-pattern search), Boyer-Moore (bad character table + good suffix table, fastest practical algorithm for large alphabets), Z-Algorithm (Z-array: Z[i] = length of longest substring starting at i that matches a prefix, simpler than KMP), Manacher's Algorithm (longest palindromic substring in O(n) — the center expansion trick with stored radii), Aho-Corasick (build a trie, add BFS failure links → simultaneous multi-pattern search in O(n+m+z), used in grep and antivirus), Suffix Array (sort all suffixes lexicographically, build LCP array, O(n log n) construction — replaces suffix tree in most practical applications). Build: a mini grep utility in Rust using Aho-Corasick for multi-pattern search across files.
Math & Bit Manipulation
Sieve of Eratosthenes (prime generation O(n log log n), bitset optimization halves memory), GCD/LCM Euclidean (number theory fundamentals, extended Euclidean for modular inverse), Fast Exponentiation (binary exponentiation O(log n), modular version: a^b mod m), Modular Arithmetic (mod inverse, Fermat's little theorem, Chinese Remainder Theorem — used in competitive programming), FFT — Fast Fourier Transform (polynomial multiplication O(n log n), convolution applications), Bit Manipulation Tricks (masks, XOR swap, SWAR techniques, popcount, bit reversal), Power of Two Checks (x & (x-1) sets lowest set bit to 0, O(1) power-of-two detection), Count Set Bits (Brian Kernighan's algorithm iterates only set bits, compare with Rust's u64::count_ones()). Build: implement Karatsuba multiplication for big integers — benchmark versus naive O(n²) multiplication.
Backtracking (Advanced)
Deep dive into the backtracking problems from Phase 3 with a performance focus. N-Queens: benchmark n=1..15, plot nodes explored with and without pruning. Sudoku Solver: implement the dancing links (Algorithm X) version — compare speed vs simple backtracking. Permutations: implement Heap's algorithm and verify it generates exactly n! permutations with no repeats using a HashSet check. Combinations/Subsets: generate the power set for n=20 using bit manipulation instead of recursion — compare performance. Rat in a Maze: add 8-directional movement with weighted paths. Word Search: optimize with early termination when remaining characters can't possibly match. Profile every solution and eliminate unnecessary heap allocations.
Divide & Conquer + Final Boss
Binary Search recursive (master theorem: T(n) = T(n/2) + O(1), so T(n) = O(log n) — prove it from first principles), Strassen's Matrix Multiplication (7 recursive multiplications instead of 8, O(n^2.807), implement and verify numerically), Closest Pair of Points (geometric D&C — split by median x, recurse, then check 2δ-wide strip in O(n) total: O(n log n)), Karatsuba Multiplication (split n-digit integers into two n/2-digit halves, 3 multiplications not 4, O(n^1.585)). Final Boss: build a Redis-compatible Key-Value store in Rust — HashMap for the main store, Skip List for ZSET sorted sets, Bloom Filter for fast membership checks before disk lookup, Trie for key prefix autocomplete, LRU Cache for the most-recently-used eviction policy. Write a full benchmark suite comparing your impl vs BTreeMap and HashMap on 1M operations.
Resources4
KMP, Z-Algorithm, Aho-Corasick, Suffix Arrays — all explained with complexity proofs and worked examples. Essential for Days 94–100.
Complete DSA exercises in Month 4 to get mentor feedback on your Rust idioms, performance choices, and idiomatic patterns.
Profile every Final Boss data structure. Learn to use flamegraph, criterion, and DHAT heap profiler to find real bottlenecks.
After implementing from scratch: petgraph for graph validation, bitvec for Bloom Filters, num for big integers, rand for randomized algorithms.