Data Structures

Reading `arr[1000000]` takes the same amount of time as reading `arr[0]`, because an array's contiguous memory layout lets the runtime compute the address of any element with a single multiplication. That single property is what makes **Arrays & Strings** the workhorse data structure of nearly every program you will ever write. This lesson walks through array declaration and indexing in JavaScript and Python, the cost of inserts and deletes that force shifting, slicing and subarray patterns, and the basic string operations every interview problem assumes you know. You will also see why strings behave as immutable character arrays in both languages and what that means for performance when you build strings inside a loop. In **How to Read Code (JS & Python)**, you practiced tracing programs line by line; that habit is exactly how you will reason about loop indices and slice boundaries here. **Big-O Notation (Upper Bound)** gave you the language to express scaling behavior, and arrays are where you will first see `O(1)` access sit next to `O(n)` insertion in the same data structure. Once array fundamentals are second nature, **Matrix/Grid Fundamentals** extends the same indexing intuition into two dimensions, where row and column traversal patterns power BFS, DFS, and dynamic programming on grids.

A modern hard drive reads about 100 MB per second sequentially, but a single random seek still costs around 10 milliseconds; that gap is roughly seven orders of magnitude. A binary tree of a billion keys has 30 levels, which means 30 random seeks per lookup. **B-Trees and B+ Trees** keep each node fat enough to fill a disk page, branch into hundreds of children, and answer the same lookup in three or four seeks. That is why every relational database you have used relies on this family for its indexes. This lesson covers the B-Tree minimum-degree parameter `t` and the resulting key-and-child counts at every node, the proactive split during insert that keeps the height bounded by `O(log_t n)`, the merge-or-redistribute logic for delete, and the B+ Tree refinement that pushes all data to the leaf level and links those leaves together so range queries become a sequential scan after a single descent. In **Binary Search Tree (BST)**, every node held a single key and at most two children; that geometry is fine for memory but disastrous for disk because each comparison forces a separate I/O. B-Trees flip the design: keep every node wide so a single I/O resolves many comparisons at once. Next, **Splay Tree** explores a third self-balancing strategy in which the tree reshapes itself around access patterns rather than maintaining strict structural invariants.

Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with `O(n)` search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree back into shape, which is exactly what a **Balanced BST** does. AVL and Red-Black trees are the two most influential designs in this family. This lesson covers the balance factor (height of left subtree minus height of right subtree), AVL's strict `|bf| <= 1` invariant enforced by the four rotation cases (LL, RR, LR, RL), and Red-Black trees' five color and structural invariants enforced by recoloring plus rotations. You will trace insertions through both schemes, see why Red-Black trees do fewer rotations on average and so are preferred by C++ `std::map` and Java `TreeMap`, and analyze the height bound (`<= 2 log n`) that gives both their worst-case `O(log n)` guarantee. In **Binary Search Tree (BST)**, you implemented search, insert, and delete that respected the ordering invariant but said nothing about shape; the resulting `O(n)` worst case is precisely what self-balancing solves by maintaining a height invariant in addition to the ordering invariant. Next, **B-Trees and B+ Trees** generalize the same balanced-tree idea to nodes that hold many keys at once, an essential design choice for disk-resident data.

Run an inorder traversal on a **Binary Search Tree (BST)** of any size and the keys come out sorted, in `O(n)` time and `O(h)` space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's `TreeMap`, C++ `std::map`, and the conceptual model behind every database index. This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive `node.left.val < node.val` check is wrong. You will also analyze the gap between the balanced `O(log n)` and the degenerate `O(n)` chain that motivates the next lesson. In **Trees: Binary Tree Fundamentals**, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free. Next, **Balanced BST (AVL / Red-Black)** addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.

Every web page you load is a tree (the DOM), every directory you `cd` into is a tree, every JSON document with nested objects is a tree, and every arithmetic expression a compiler parses is a tree. **Binary Tree Fundamentals** turns that ubiquitous shape into a precise data structure where each node has at most two children, named `left` and `right`. This lesson covers the vocabulary you need for the rest of the curriculum (root, leaf, parent, child, sibling, depth, height), the four common shape categories (full, complete, perfect, balanced) and the degenerate case that collapses to a chain, all four canonical traversals (preorder, inorder, postorder, and level-order BFS), and both recursive and iterative implementations of each. You will also analyze why traversals are `O(n)` time but only `O(h)` space when written recursively. In **Queue & Deque**, you saw that a FIFO queue processes items in arrival order; level-order traversal is exactly that pattern applied to tree nodes. In **Hash Map (Dictionary) Basics**, the bucket-by-key idea reappears here when you store parent-pointer mappings or memoize subtree results during a traversal. With binary trees in your toolkit, **Binary Search Tree (BST)** layers an ordering invariant on top to turn the same shape into a logarithmic-time search structure.

An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last' means 'back to the first'. A **Circular Linked List** encodes that shape directly, with the last node's `next` pointer wired to the head instead of `null`. This lesson covers the circular singly linked list and its doubly linked variant, the stop condition for traversal (return to the starting node rather than waiting for `null`), insertion at the head and at the tail in `O(1)` when a tail pointer is maintained, and deletion that correctly handles the wrap-around. You will also compare circular structures with the standard linear forms so you know when bending the list back on itself is the right call and when it just complicates traversal. In **Linked Lists (Singly)**, traversal terminated when you reached a `null` next pointer; here, the same loop must compare against the starting node instead, a small change that exposes the distinction between cycle detection and cycle definition (Floyd's tortoise-and-hare reuses this idea later). With all three linked-list shapes covered, the curriculum next pivots to tree-based and array-based structures with stronger time guarantees.

Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is `O(n)`. Add a `prev` pointer to every node and the same delete becomes four pointer rewires in `O(1)`, which is exactly the upgrade that powers LRU caches and the browser back-forward stack. This lesson covers the **Doubly Linked List** node layout (`value`, `next`, `prev`), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks. In **Linked Lists (Singly)**, head insertion was already `O(1)` but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping. Next, **Circular Linked List** keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.

A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the enormous class of problems that need exactly that, a **Fenwick Tree** (also called a Binary Indexed Tree, or BIT) is the right answer. This lesson covers the dynamic prefix-sum problem (static prefix sums are `O(1)` query and `O(n)` update; you want both in `O(log n)`), the `i & -i` lowbit trick that isolates the lowest set bit and implicitly defines which range each index covers, point update and prefix query in `O(log n)`, and the `prefix(R) - prefix(L-1)` identity that turns those into general range queries. You will also meet the difference-array technique that swaps the roles, supporting `O(log n)` range updates with `O(log n)` point queries. In **Arrays & Strings**, you saw how a flat array can encode rich structure when the indexing scheme is clever; the Fenwick tree pushes that idea further by letting binary representation itself carry the partition information. **Segment Tree** solved a more general version of this problem with explicit nodes; the BIT trades flexibility for simplicity and memory and wins on both metrics whenever prefix queries suffice. Next, **Sparse Table** addresses a different point in the trade space: arbitrary range minimum (and similar idempotent) queries, with `O(1)` queries when no updates are involved.

A social network is a graph, a road map is a graph, an `import` graph in your codebase is a graph, and so is the dependency tree of a package manager. The reason graphs feel everywhere is that they are the most general relationship structure: just vertices and edges, with no required root, no acyclic constraint, and no fixed branching factor. **Graphs: Representation Basics** is where you stop drawing them on whiteboards and start storing them in code. This lesson defines the core vocabulary (vertex, edge, degree, path, cycle, directed and undirected, connected and disconnected) and walks through the three canonical representations: an adjacency list backed by a hash map of vertex to neighbors, an adjacency matrix for dense graphs and `O(1)` edge-existence queries, and an edge list for algorithms that just iterate over edges. You will analyze the space and time trade-offs of each so you can pick the right one before writing any traversal logic. In **Hash Map (Dictionary) Basics**, you saw that a hash map maps keys to values in expected `O(1)`; an adjacency list is exactly that, mapping each vertex to its list of neighbors. **Queue & Deque** gave you the FIFO machinery that BFS will run on top of these representations once traversal lessons begin. With a graph stored in memory, the algorithms track is where it comes alive: BFS, DFS, shortest paths, connected components, and the rest of the graph algorithm canon.

Two Sum is the canonical example: scan the array once, and for every number `x` ask the data structure whether you have already seen `target - x`. With a list that is `O(n^2)`. With a **Hash Map**, the lookup becomes a single function call and the whole algorithm collapses to `O(n)`. This lesson covers the key-value abstraction, the intuition behind a hash function (a key gets converted to a bucket index by an integer-valued function), what a collision is, and how `get`, `set`, `delete`, and `has` behave in JavaScript's `Map` and Python's `dict`. You will also meet two recurring patterns: counting frequencies and bucketing/grouping by a derived key, both of which appear in dozens of interview problems and real applications such as analytics, caching, and indexing. In **Arrays & Strings**, you saw that searching an unsorted array is `O(n)` because every position is equally plausible. A hash map turns that linear scan into an arithmetic computation that points directly at the right slot, which is the entire reason hash-based lookups dominate practical software. With key-based lookup in hand, **Set Basics** specializes the same machinery to a single question: have I seen this value before?

Python's `dict` uses open addressing with a Robin Hood-inspired probe. Java's `HashMap` switches a bucket from a linked list to a red-black tree once chain length crosses eight. C++ `std::unordered_map` is required by the standard to use chaining. Three production hash tables, three different choices, all defending the same goal: keep expected `O(1)` lookups even as the table fills up. **Hash Table (Advanced)** unpacks the engineering decisions behind those choices. This lesson covers hash function design (division method, multiplication method, universal hashing), the two collision-resolution families (separate chaining and open addressing with linear, quadratic, or double hashing), the load-factor threshold that triggers a rehash, and the amortized `O(1)` cost of dynamic resizing. You will also see how tombstones make deletion correct under open addressing, and why Robin Hood and cuckoo hashing tame worst-case probe lengths. In **Hash Map (Dictionary) Basics**, you used a hash map as a black box; this lesson opens the box and replaces the hand-wave with a quantitative model. **Modular Arithmetic** is the workhorse behind every practical hash function: the `key % m` step that turns an arbitrary integer into a valid bucket index, and the `(h(k) + i*step) % m` formula behind double hashing. Next, **Skip List** answers the same fast-lookup question with a probabilistic, pointer-based design that has no hash function at all and no rehashing step.

Pull the next task in priority order from a stream of millions, and a sorted array gives you `O(1)` extract but `O(n)` insert; a sorted linked list flips the costs but stays linear; a balanced BST hits `O(log n)` for both but with substantial pointer overhead. A **Heap** quietly outperforms all three for this exact workload by storing a complete binary tree in a flat array and keeping just the min (or max) at the root. This lesson covers the heap property, the parent-and-child index formulas (`parent = (i-1)/2`, `left = 2i+1`, `right = 2i+2`) that let array indices encode tree structure with no pointers, sift-up and sift-down for `O(log n)` insert and extract, and the linear-time `heapify` build. You will see how this maps onto the priority queue abstraction and onto interview staples such as top-K elements, K-th largest, merge K sorted lists, and the streaming median with two heaps; on the systems side, the same structure powers Dijkstra and Prim. In **Trees: Binary Tree Fundamentals**, you saw what a complete binary tree is and how to traverse one; the heap reuses that exact shape but stores it implicitly. **Arrays & Strings** is what makes the implicit storage cheap: a flat array gives `O(1)` parent and child access through arithmetic, with no allocations per node. Next, **Binary Search Tree (BST)** trades the heap's partial ordering for a full ordering invariant, unlocking sorted iteration and key-based search at the cost of needing actual pointers.

Inserting at the front of an array of one million items forces every existing element to slide one slot to the right. A **Linked List** sidesteps that copy entirely: a head insertion is two pointer assignments and nothing else, no matter how many nodes follow. In this lesson, each node holds a value and a `next` reference, and you chain those nodes into a singly linked list with explicit head and optional tail pointers. You will implement traversal, head and tail and middle insertion, deletion by value and by position, and linear search, and you will analyze each operation precisely so the trade-off against arrays becomes concrete: `O(1)` insertion at the head, `O(n)` access by index, and per-node memory overhead for the pointer. In **Arrays & Strings**, the `O(n)` cost of inserting near the front came from shifting; the linked list was invented to remove that shift. **Memory Models** introduced the difference between a contiguous block on the stack or heap and scattered allocations connected by references, and that mental model is exactly how a node-based structure lives in memory. Once you are comfortable manipulating `next` pointers, **Stack (LIFO)** uses a linked list (or a dynamic array) as its underlying storage and adds a strict push, pop, peek discipline on top.

Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both `get(key)` and `put(key, value)` in `O(1)`. No single primitive does that: a hash map gives `O(1)` lookup but no recency order, and a doubly linked list gives `O(1)` recency moves but no key index. The classical **LRU Cache** wires the two together so each compensates for what the other lacks. This lesson designs the composite from scratch: a hash map that points keys to DLL nodes, and a doubly linked list that orders nodes by recency with most-recent at the head and least-recent at the tail. You will trace `get` and `put` through both structures, handle the capacity-of-one and update-existing-key edge cases, and see why this design appears in browser caches, database query caches, OS page replacement, and CDNs. In **Hash Map (Dictionary) Basics**, you used a hash map for `O(1)` lookup by key. **Doubly Linked List** added the `prev` pointer that makes mid-list deletion `O(1)` once you hold the node, plus the sentinel pattern that erases null checks at the boundaries; both are load-bearing here. The LRU pattern (one structure for indexing, another for ordering, kept consistent on every operation) is the gateway to a wider family of composite designs covered in later lessons.

Picture an image as a grid of pixels, a chessboard as an 8 by 8 array of squares, or a maze as a rectangle of walls and corridors. Each of these is a **Matrix/Grid**: a two-dimensional array indexed by `(row, column)` where the right traversal order can turn a hard problem into a single nested loop. This lesson covers how to allocate and initialize 2D arrays in JavaScript and Python, how row-major storage maps a `[i][j]` access to a contiguous memory offset, and the standard traversal patterns: row by row, column by column, and along the two diagonals. You will also practice boundary checks, the most common source of off-by-one bugs in grid problems, and implement a transpose to see how index swaps reshape data in place. In **Arrays & Strings**, you saw that a one-dimensional array gives `O(1)` indexed access through a single offset calculation. A grid is just nested arrays sharing that same property along two axes, so every shifting and bounds idea you used there carries over directly. Once you can move confidently through a grid, **Linked Lists (Singly)** shifts the focus to a very different memory layout: pointer-based nodes with no contiguous block at all.

Cloning a 100k-element segment tree before every update so the previous version stays queryable costs `O(n)` time and space per update, which is unworkable. **Persistent Data Structures** achieve the same 'every past version is still queryable' guarantee in `O(log n)` extra time and space per update by sharing the unchanged subtrees between versions and only allocating new nodes along the path that actually changed. This lesson covers the path-copying technique on a persistent segment tree (each update returns a brand-new root that shares everything except a thin spine of new nodes with the previous version), the `O(log n)` point update and range query on any historical version, persistent arrays built on top of persistent segment trees, and persistent stacks and queues using the cons-list approach from functional programming. You will analyze the total space (`O(n + q log n)` for `q` updates) and apply the structure to k-th smallest in subarrays, time-travel queries, and offline-query reductions. In **Trees: Binary Tree Fundamentals**, a recursive subtree was a self-contained piece of data; structural sharing exploits exactly that property to reuse old subtrees in new versions. **Segment Tree** built the recursive aggregate-over-intervals shape that the persistent variant adapts directly, swapping in-place updates for path copying. Next, **Treap (Randomized BST)** returns to the BST family with a different twist: random priorities for expected balance and `O(log n)` split and merge primitives.

BFS visits a graph one frontier at a time, and the trick that makes that work is a queue: nodes are added in the order they are discovered and pulled out in the same order, level by level. **Queue & Deque** captures that First In, First Out discipline as a reusable abstraction, then extends it to a double-ended variant that pops up surprisingly often in sliding-window problems. In this lesson, you will implement `enqueue`, `dequeue`, `front`, and `isEmpty` using both a linked list and an array, then see why a naive array queue wastes space and how a circular queue with two index pointers fixes that with `O(1)` operations. You will also build a deque that supports inserts and removes at both ends, the structure underneath the monotonic-deque pattern that solves sliding-window-maximum in linear time. In **Stack (LIFO)**, you implemented `push` and `pop` from the same end and saw how the choice of array versus linked list affected the worst-case bound. A queue uses the same two storage options but pulls from the opposite end, which is what forces the circular buffer trick when you back it with an array. With a queue in your toolkit, **Hash Map (Dictionary) Basics** introduces the most-used data structure in real-world code: a key-value store that answers lookups in expected `O(1)`.

Given an array and a stream of mixed queries (`sum(L, R)`, `min(L, R)`, plus single-index updates), prefix sums answer the queries in `O(1)` but pay `O(n)` for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A **Segment Tree** balances the two: every operation runs in `O(log n)` after an `O(n)` build. This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the `4n` flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in `O(log n)`, and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate. In **Arrays & Strings**, a flat array gave you `O(1)` indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. **Trees: Binary Tree Fundamentals** is where the recursive shape and the `O(h)`-stack traversal pattern came from, and you reuse both directly here. Next, **Fenwick Tree (BIT)** solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.

Drop a million IDs into a `Set`, ask `set.has(id)` for any one of them, and the answer comes back in expected constant time without any ordering, sorting, or scanning. That single primitive (membership testing) is what makes a **Set** the quiet workhorse behind deduplication, visited-node tracking in graph traversal, and almost every cache-invalidation routine you will read. This lesson covers the uniqueness invariant of a set, the four core operations `add`, `delete`, `has`, and iteration in both JavaScript's `Set` and Python's `set`, and the four classical set-theory operations: union, intersection, difference, and symmetric difference. You will see why a set is implemented as a hash map whose values are unused, and you will practice the visited-set pattern that reappears in BFS, DFS, and cycle detection. In **Hash Map (Dictionary) Basics**, you learned that a hash function maps keys to bucket indices for `O(1)` get and set. A set keeps only the keys, drops the values, and exposes the resulting structure as a pure membership data type. Next, **Trees: Binary Tree Fundamentals** moves from flat unordered collections to hierarchical structures, where parent and child relationships unlock entirely new traversal patterns.

Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a `ConcurrentSkipListMap` in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a **Skip List**: a sorted linked list with a few extra express-lane pointers that turn `O(n)` search into `O(log n)` expected. This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution. In **Linked Lists (Singly)**, a search was `O(n)` because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on. Next, **Balanced BST (AVL / Red-Black)** is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.

Range minimum queries on a fixed array do not need updates, so the segment tree's `O(log n)` query is leaving performance on the table. A **Sparse Table** flattens the query down to genuine `O(1)`: precompute the minimum of every power-of-2 length window, and any range `[L, R]` can be answered by combining two such windows that together cover it, exploiting the fact that `min(min(A), min(B)) = min(A union B)` when the windows overlap. This lesson covers the `O(n log n)` preprocessing that fills a 2D table indexed by `(start, log2_length)`, the `O(1)` query trick for idempotent operations such as min, max, GCD, and bitwise OR, the `log2_floor` precomputation that makes every query branch-free, and the slower `O(log n)` query needed when the operation is not idempotent (like sum). You will see why this structure is the right tool for the Range Minimum Query (RMQ) problem and an essential building block in algorithms like Lowest Common Ancestor in `O(1)` per query. In **Arrays & Strings**, a flat array stored values; here the same shape stores precomputed answers indexed by a length exponent. **Logarithms & Exponentiation** is what makes the geometry work: power-of-two windows tile the index space the way binary representations tile integers, and the `O(1)` query depends on `floor(log2(length))`. With Sparse Tables in your toolkit, the curriculum next pivots to specialized structures for strings, immutability, and bounded integer universes.

Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A **Splay Tree** turns that observation into a balancing strategy: every access (search, insert, or delete) drags the touched node to the root through a sequence of rotations, so frequently used keys stay shallow and effectively pay `O(1)` after the first hit. This lesson covers the three splay rotation cases (zig, zig-zig, and zig-zag) that move a target node toward the root in pairs of levels, the modified search, insert, and delete operations that always end with a splay, and the amortized analysis that yields `O(log n)` per operation across any sequence of `m` operations even though individual operations can be `O(n)` in the worst case. You will also meet the working set theorem, which is the formal version of the temporal-locality intuition. In **Binary Search Tree (BST)**, accesses left the tree shape unchanged; balanced variants enforced strict structural invariants. The splay tree refuses both options and instead lets the access pattern itself reshape the tree, with no balance factor or color bit stored anywhere. Next, **Treap (Randomized BST)** keeps the same single-bit-of-extra-state simplicity but uses random priorities (rather than recent access) to control balance.

Every time a function calls another function, the language runtime pushes a frame onto an internal stack; every `return` pops one off. That same Last In, First Out discipline shows up in undo buttons, expression evaluators, browser back navigation, and the call patterns of recursion, which is why **Stack (LIFO)** is one of the first abstract data types every engineer learns. This lesson introduces the four core operations of a stack (`push`, `pop`, `peek`, `isEmpty`), the underflow case you must handle on every pop, and two implementations: a dynamic array stack with amortized `O(1)` push, and a linked list stack with strict `O(1)` push at the head. You will trace stack state through bracket matching, postfix evaluation, and string reversal so the LIFO mental model becomes a tool you reach for instinctively when a problem asks you to remember the most recent thing. In **Arrays & Strings**, you saw that appending to the end of a dynamic array is `O(1)` amortized, which is exactly the cost model for an array-backed stack. **Linked Lists (Singly)** showed that head insertion is unconditionally `O(1)`, which is what makes a linked list the cleanest backing store for a stack with a strict worst-case guarantee. Next, **Queue & Deque** flips the discipline: instead of pulling from the same end you pushed to, you pull from the opposite end, and the implementation gets just a little more interesting.

Genome alignment tools like BWA and Bowtie find a 100-character read inside a 3-billion-base human reference in milliseconds, not by scanning the genome but by querying an index built once over all of its suffixes. **Suffix Array / Suffix Tree** is the family of data structures behind that workflow, and the same machinery powers full-text search, plagiarism detection, and the BWT-based compression in bzip2. This lesson covers the suffix array (a sorted array of starting positions of every suffix), the binary-search pattern match in `O(m log n)` for a pattern of length `m`, the LCP (Longest Common Prefix) array that captures shared prefixes between adjacent sorted suffixes, and the suite of substring problems the pair solves: longest repeated substring, number of distinct substrings, and longest common substring. You will also meet the suffix tree, a compressed trie of all suffixes that pushes pattern matching down to `O(m)` independent of text length, and weigh the suffix array's smaller memory footprint against the suffix tree's faster query. In **Arrays & Strings**, sorting and binary search worked over numbers; here the same primitives extend to strings, with a comparator that compares characters position by position. **Trie (Prefix Tree)** introduced the prefix-matching tree shape, and a suffix tree is a compressed trie built from every suffix of the input. Next, the curriculum explores data structures organized around a different axis entirely: preserving every historical version of themselves through time.

Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A **Treap** reaches the same expected `O(log n)` height in maybe sixty lines, with no color bits and no balance factor, by giving each node a random priority and asking the tree to satisfy two simple invariants at once. This lesson covers the dual structure (BST order on keys, heap order on randomly assigned priorities), the proof sketch that random priorities yield expected `O(log n)` height because the tree is shaped like a uniform random BST, and the two operations that make treaps unusually flexible: `split(key)` cuts the treap into 'less than' and 'greater or equal' pieces, and `merge` glues two treaps together when one contains only smaller keys. From those two primitives, insert, delete, k-th element, and even range reversal fall out naturally. You will also meet the implicit treap, where positions replace keys and the result behaves like a balanced array supporting `O(log n)` insert-at-index and slicing. In **Binary Search Tree (BST)**, you saw that an unlucky insertion order produced a chain; randomized priorities solve that by making any input look balanced in expectation, the same way randomized quicksort tames adversarial pivots. With treaps in hand, the curriculum next explores structures that exploit very different properties (such as bounded integer universes) to push performance beyond what comparison-based trees can offer.

Type the letters `a-p-p` into a search box and the autocomplete dropdown produces `apple`, `application`, `apply`, and `appoint` before you finish the next keystroke. The data structure doing that work is a **Trie** (or prefix tree), where every stored word is a path from root to a marked node and every shared prefix is shared in memory exactly once. This lesson covers the trie node layout (a `children` map plus an `isEndOfWord` flag), `insert`, `search`, and `startsWith` operations that all run in `O(m)` for a query of length `m` (independent of how many words the trie holds), and a `delete` that has to be careful not to break paths used by other words. You will also analyze the space behavior, including when a trie wins over a hash set (prefix queries, lexicographic enumeration) and when it loses (memory-tight workloads with no prefix structure to exploit). In **Hash Map (Dictionary) Basics**, you used hashing to answer 'have I seen this exact key' in `O(1)`; a trie answers a strictly richer question (any prefix lookup) by trading `O(1)` exact-match for `O(m)` traversal. **Trees: Binary Tree Fundamentals** introduced the recursive child-pointer pattern, and a trie generalizes it from two children per node to one child per alphabet symbol. With a trie in your toolkit, the curriculum moves on to graph and hash extensions that solve a different family of problems built on the same node-and-edge thinking.

Given a million pairwise 'these two accounts belong to the same person' relations, decide whether two arbitrary accounts are now equivalent. Brute-force flood fills are `O(n)` per query; sorting is the wrong shape entirely. **Union-Find** answers each query in nearly `O(1)` amortized time after the relations are merged, with two primitives and a parent array. This lesson covers the disjoint-set abstraction, the `find` operation that walks parent pointers up to a representative, the `union` operation that links two representatives, and the two optimizations (path compression during `find` and union by rank during `union`) that together push the amortized cost to `O(alpha(n))`, where `alpha` is the inverse Ackermann function (effectively constant for any input you can fit in memory). You will trace the parent array as merges happen, and apply the structure to cycle detection in undirected graphs, connected components, equivalence classes, and Kruskal's minimum spanning tree. In **Arrays & Strings**, you saw that an array can encode a mapping from index to value in `O(1)`; a parent array is exactly that mapping, applied to representative pointers. **Graphs: Representation Basics** gave you the vertex-and-edge vocabulary that Union-Find uses to define connectivity, even though the structure itself stores no edges directly. With Union-Find in your toolkit, the curriculum continues with composite designs that combine multiple primitives, starting with the LRU cache pattern.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.

Highways have lengths in kilometers, flights have ticket prices in dollars, and network links have latencies in milliseconds. Treating any of those graphs as unweighted throws away the only information that matters for the question you actually care about (the shortest, cheapest, or fastest route), which is exactly the gap a **Weighted Graph** representation closes by attaching a number to every edge. This lesson covers three representations: a weighted adjacency list backed by arrays of `{node, weight}` pairs, a weighted adjacency matrix where `matrix[u][v]` is the edge cost (and infinity for non-edges), and a weighted edge list that stores `(u, v, weight)` triples. You will analyze the space and time trade-offs, see why Dijkstra wants the adjacency list, why Floyd-Warshall wants the matrix, and why Kruskal wants the edge list, and you will represent both directed and undirected weighted graphs correctly in each format. In **Graphs: Representation Basics**, you stored connectivity (whether an edge exists) using the same three shapes; the weighted version simply replaces a boolean or membership check with a numeric value. **Hash Map (Dictionary) Basics** is what makes the adjacency list work: a vertex maps to its neighbor-and-weight list in expected `O(1)`, the same way the unweighted version did. With weights in the picture, the algorithms track unlocks shortest-path and minimum-spanning-tree algorithms that read the weight on every edge during their core inner loop.