Module 1 · Linear Data Structures
A linear data structure stores elements in a sequence: every element has at most one predecessor and one successor. Arrays, strings, stacks, queues, deques and linked lists are the linear structures; hash tables are not linear in the strict sense but live here because they are the tool you reach for when a linear scan is too slow and the data has no order to exploit. Module 1 teaches these structures and the handful of patterns that turn a quadratic scan over them into a single pass — two pointers, sliding window, prefix sums, monotonic stacks and deques, interval sweeps. Those patterns account for a large share of what interviewers ask and of what runs inside databases, network stacks and runtimes.
The module is in the DSA: Zero to Mastery course. Previous module: Module 0 · Foundations. Next: Module 2 (searching and sorting).
What this module covers
Fourteen lessons and a capstone, grouped in four arcs.
Arc 1 — arrays and the three scanning patterns. The Arrays & Strings overview gives the patterns at a glance; the three deep pages that follow — Two Pointers, Sliding Window, Prefix Sums & Difference Arrays — each take one pattern from brute force to an algorithm with a proof. Matrices & 2D Grids extends the arrays to two dimensions and shows the moment a grid becomes a graph. Strings in Depth covers encodings, immutability, frequency patterns and parsing without regular expressions.
Arc 2 — stacks, queues and their monotonic forms. Stacks (LIFO order, expression evaluation, bracket matching, min-stack, recursion made explicit), Queues, Deques & Circular Buffers (FIFO, ring buffers, the deque behind BFS), and Monotonic Stack & Monotonic Deque, which solves next-greater-element, largest rectangle in a histogram and sliding-window maximum in with the same amortized argument you met in the sliding-window lesson.
Arc 3 — intervals and pointers. Intervals is sort-by-start, sweep, and most calendar and scheduling problems fall. Linked Lists is pointer manipulation with proofs: fast/slow pointers, cycle detection, reversal patterns.
Arc 4 — hashing and its probabilistic cousins. Hash Tables & Hashing in Depth covers hash functions, collision strategies, resizing and open addressing versus chaining; Bloom Filters, Count-Min Sketch & Probabilistic Structures trades a little accuracy for a lot of memory, the way caches, databases and CDNs do.
Capstone. Build an LRU Cache & Benchmark It: a hash map plus a doubly linked list for get and put, an LFU variant, and a benchmark against your language's built-ins. It uses every arc: the hash table for lookup, the linked list for recency order, and the measurement discipline from Module 0.
Optional deep dive. Advanced Data Structures — skip lists, Fenwick trees, segment trees and the structures you will want after Module 3. Read it when a lesson here mentions one.
Why in this order
The order follows dependencies, not difficulty. Two pointers comes first because it is the smallest idea with a real asymptotic win and because its correctness argument — "the pointer I move cannot be part of a better answer", written as a loop invariant — is reused verbatim by sliding windows. Prefix sums come after windows because the first thing a window cannot do (sums with negative numbers) is the first thing prefix sums can. Stacks and queues precede their monotonic forms, and monotonic deques close the loop with sliding-window maximum. Linked lists come late because, as the capstone shows, their real use is as a component inside a hash-map-backed structure. Probabilistic structures come last because they assume you understand ordinary hashing's costs well enough to want to trade accuracy for memory.
flowchart TD
M0["Module 0 · Foundations"] --> AS["Arrays & Strings overview"]
AS --> TP["Two Pointers"]
TP --> SW["Sliding Window"]
SW --> PS["Prefix Sums"]
PS --> MG["Matrices & Grids"]
AS --> SD["Strings in Depth"]
AS --> ST["Stacks"]
ST --> QD["Queues & Deques"]
QD --> MS["Monotonic Stack & Deque"]
SW --> MS
TP --> IV["Intervals"]
TP --> LL["Linked Lists"]
SW --> HT["Hash Tables"]
HT --> PD["Probabilistic Structures"]
LL --> CAP["Capstone: LRU Cache"]
HT --> CAP
CAP --> M2["Module 2 · Searching & Sorting"]
Arrows mean "read this first". Arcs 2 and 3 can be interleaved.
Prerequisites
From Module 0: Complexity Analysis (you will read " amortized" on nearly every page and should be able to verify it), Your Language's Data Structures (the real cost of list.pop(0), ArrayList.remove(0), Array.prototype.shift), How Data Structures Live in Memory, and the brute-force-comparator habit from Testing & Debugging Algorithms.
You need one of Python 3.12+, Java 21, C++20 or TypeScript (Node 22+); every canonical implementation is given in all four and is self-checking.
Lessons
| # | Lesson | After it you will be able to… | Minutes |
|---|---|---|---|
| 1 | Arrays & Strings (overview) | Recognise the five array patterns at a glance and know which deep page to open | 45 |
| 2 | Two Pointers | Turn pair, partition and merge problems into passes and prove the loop invariant | 45 |
| 3 | Sliding Window | Solve longest/shortest/count subarray problems in one pass and state when a window is the wrong tool | 50 |
| 4 | Prefix Sums & Difference Arrays | Answer range sums in , apply range updates in , handle negatives, XOR and 2D | 45 |
| 5 | Matrices & 2D Grids | Traverse, rotate, spiral and flood-fill a grid, and see when it becomes a graph | 45 |
| 6 | Strings in Depth | Reason about encodings and immutability, use frequency tables, parse without regex | 50 |
| 7 | Stacks | Evaluate expressions, match brackets, build a min-stack, convert recursion to iteration | 45 |
| 8 | Queues, Deques & Circular Buffers | Implement a ring buffer and a deque, and know what BFS and sliding-window maximum need from them | 40 |
| 9 | Monotonic Stack & Monotonic Deque | Solve next-greater-element, histogram rectangle and window maximum in with an amortized proof | 50 |
| 10 | Intervals | Merge, insert and schedule intervals with a sort-and-sweep, and recognise sweep-line problems | 45 |
| 11 | Linked Lists | Manipulate pointers safely, prove fast/slow cycle detection, reverse in groups | 55 |
| 12 | Hash Tables & Hashing in Depth | Explain hash functions, collisions, resizing and open addressing vs chaining, and defend against anti-hash tests | 60 |
| 13 | Bloom Filters, Count-Min Sketch & Probabilistic Structures | Size a Bloom filter for a target false-positive rate and know where sketches run in production | 45 |
| — | Capstone: Build an LRU Cache & Benchmark It | Implement LRU and LFU caches, write acceptance tests, benchmark and explain the numbers | 150–180 |
| opt. | Advanced Data Structures | Preview skip lists, Fenwick and segment trees for when the linear tools run out | 60 |
Lesson time totals about 620 minutes — roughly 10 to 11 hours — plus 3 hours for the capstone and as much again for the practice ladders. Two focused weeks at an hour a day is realistic.
How to study this module
Trace before you code. Every deep page has a trace table — the algorithm run by hand on a small input, one row per step. Cover the table, run the algorithm on paper yourself, then compare. If your table differs, you have found the misunderstanding before it became a bug.
Write the invariant down. Each pattern page states a loop invariant. Before writing a two-pointer or window loop, write the invariant as a comment in one sentence. If you cannot, you do not yet know why the loop is correct, and the problem will punish that with an off-by-one.
Climb the ladders, do not jump to the top. Every page has a "brute force → better → optimal" ladder. Implement the brute force first — it takes two minutes and becomes your comparator for randomized stress tests, exactly as Testing & Debugging Algorithms prescribes. Many of the solutions on these pages do this inline.
Read a second language's version. The canonical implementations are given in Python, Java, C++ and TypeScript with the same tests. Comparing two shows what is essential to the algorithm and what is an artefact of your language (integer overflow, string indexing by code unit, a lexicographic default sort).
Practice ladders: first eight now, the rest later. Each page lists 12–15 problems easy to hard with hints and worked solutions. Return to the hard tail after the monotonic-structures lesson.
Do the capstone. It is the only place in the module where the structures combine, and the benchmark shows the gap between Big-O and wall-clock time that Module 0 warned you about.
Start with Arrays & Strings (overview), then follow the table in order. Previous module: Foundations. Course map: DSA: Zero to Mastery.