On this page

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

#LessonAfter it you will be able to…Minutes
1Arrays & Strings (overview)Recognise the five array patterns at a glance and know which deep page to open45
2Two PointersTurn pair, partition and merge problems into passes and prove the loop invariant45
3Sliding WindowSolve longest/shortest/count subarray problems in one pass and state when a window is the wrong tool50
4Prefix Sums & Difference ArraysAnswer range sums in , apply range updates in , handle negatives, XOR and 2D45
5Matrices & 2D GridsTraverse, rotate, spiral and flood-fill a grid, and see when it becomes a graph45
6Strings in DepthReason about encodings and immutability, use frequency tables, parse without regex50
7StacksEvaluate expressions, match brackets, build a min-stack, convert recursion to iteration45
8Queues, Deques & Circular BuffersImplement a ring buffer and a deque, and know what BFS and sliding-window maximum need from them40
9Monotonic Stack & Monotonic DequeSolve next-greater-element, histogram rectangle and window maximum in with an amortized proof50
10IntervalsMerge, insert and schedule intervals with a sort-and-sweep, and recognise sweep-line problems45
11Linked ListsManipulate pointers safely, prove fast/slow cycle detection, reverse in groups55
12Hash Tables & Hashing in DepthExplain hash functions, collisions, resizing and open addressing vs chaining, and defend against anti-hash tests60
13Bloom Filters, Count-Min Sketch & Probabilistic StructuresSize a Bloom filter for a target false-positive rate and know where sketches run in production45
—Capstone: Build an LRU Cache & Benchmark ItImplement LRU and LFU caches, write acceptance tests, benchmark and explain the numbers150–180
opt.Advanced Data StructuresPreview skip lists, Fenwick and segment trees for when the linear tools run out60

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.