Linear Data Structures

reading · we frame, you read MIT or the canonical taught · we author, no canonical fits ↺ spirals back to earlier lessons

Course locked

Complete The Missing Semester — CS Tools first.

This course unlocks once you've finished its prerequisite. Open prerequisite →

Prerequisites

Introduction to Algorithms and Complexity not yet

Systems Programming (C and Zig) not yet

Complete prerequisites first to enroll.

reading · 30 min + ~203 min canonical

Arrays: Static and Dynamic, and the Cost Model You Already Know

You've been using arrays since your first program. [1, 2, 3] in Ruby. int arr[10] in C. They feel obvious — a row of values you can index into. But there are two distinct things h…

primary UC Berkeley CS61B (Spring 2026) by Josh Hug

preview →

reading · 30 min + ~203 min canonical L1

Linked Lists: The Other Way to Build a Sequence

In the last lesson you saw a sequence built out of contiguous memory — one big slab, indexed by offset. Linked lists are the opposite: a sequence made of scattered nodes, each one…

primary UC Berkeley CS61B (Spring 2026) by Josh Hug

after L1 locked

reading · 35 min + ~203 min canonical L1

Abstract Data Types: The API/Implementation Split

You just learned two ways to build a sequence — arrays and linked lists — with opposite performance profiles. Now suppose you're writing code that needs a sequence. You add items …

primary UC Berkeley CS61B (Spring 2026) by Josh Hug

after L2 locked

reading · 25 min + ~203 min canonical L1

Stacks: The Function-Call Machine and the Bracket-Matcher

You've already used a stack thousands of times — every function you've called has pushed a frame onto one, and every time the function returned, a frame popped off. The pattern is…

primary UC Berkeley CS61B (Spring 2026) by Josh Hug

after L3 locked

reading · 25 min + ~203 min canonical L1

Queues, Deques, and the Ruby Shift/Unshift Lens

A stack is what you reach for when the most recent thing matters most. A queue is what you reach for when the oldest thing matters most — the line at the coffee shop, the print jo…

primary UC Berkeley CS61B (Spring 2026) by Josh Hug

after L4 locked

exercise reading · 15 min L1

Exercises: Easy (Warm-up)

- [ ] Contains Duplicate (#217) — NC/LC — Use a Set to detect duplicates in O(n) - [ ] Valid Parentheses (#20) — NC/LC — Stack-based matching of brackets - [ ] Implement Queue usi…

after L5 locked

exercise reading · 30 min L1

Exercises: Medium (Core)

- [ ] Min Stack (#155) — NC/LC — Stack that supports O(1) getMin - [ ] Evaluate Reverse Polish Notation (#150) — NC/LC — Stack-based expression evaluation - [ ] Daily Temperatures…

after L6 locked

exercise reading · 45 min L1

Exercises: Hard (Stretch)

- [ ] Largest Rectangle in Histogram (#84) — NC/LC — Monotonic stack, O(n) solution - [ ] Sliding Window Maximum (#239) — NC/LC — Monotonic deque for O(n) sliding max - [ ] Car Fl…

after L7 locked

exercise reading · 60 min L1

Mini-Project

- [ ] Build a calculator in Ruby — parse infix expressions, convert to postfix (Shunting-yard algorithm), evaluate with a stack; support +, -, , /, (, ), and operator precedence

after L8 locked

L10

project reading · 360 min L1

Project: Ruby Array Internals Reimplementation

Build MyArray in Ruby that behaves like Ruby's Array but you implement the dynamic resizing yourself (backed by a fixed-size C-style array conceptually). Implement push, pop, shif…

after L9 locked

L11

project reading · 240 min L1

Project: Undo/Redo System

Implement a text buffer with undo/redo using two stacks. Support operations: insert(pos, text), delete(pos, length), undo, redo. Each operation pushes its inverse onto the undo st…

after L10 locked

L12

project reading · 600 min L1

Capstone: Database Index Engine

- [ ] Milestone 1: Implement MyDynamicArray with amortized O(1) append - [ ] Milestone 2: Implement MyHash with chaining, rehashing at load factor 0.75 - [ ] Milestone 3: Implemen…

after L11 locked

L13

assessment reading · 63 min L1

Self-Assessment: Linear Data Structures

- [ ] What is the difference between an array and a linked list? What are the time complexities for insertion, deletion, and access in each? - [ ] What is amortized O(1) for dynam…

after L12 locked

13 lessons. Read in order; spiral back when you need to. By the end you'll have used the core ideas twice — once on the abstract, once on something you'll meet at work next week.