7 chapters · 50 sections
- Chapter I
A Bad Stack
We build the worst version of a singly-linked stack first, on purpose. Every wall we hit teaches a piece of Rust we'll keep using.
- Chapter II
An Ok Stack
The stack from Chapter 1 works, but it has four obvious problems: it only holds `i32`, it reinvents a worse `Option`, it can't be peeked at, and it can't be iterated. We fix all four in this chapter and end with something that genuinely resembles a real Rust collection.
- Chapter III
A Persistent Stack
We've been single-owner the whole book. A persistent list shares its tail across many lists at once — prepend a new head, hand someone else the old list, both keep working. Single ownership can't express that. We need reference counting.
- Chapter IV
A Bad Safe Deque
A doubly-linked list in 100% safe Rust. It is possible. It is also a structurally bad design — and the point of this chapter is to show you exactly why, by building it.
- Chapter V
An Unsafe Queue
A queue needs O(1) push at the back and O(1) pop at the front. That means two pointers into the same chain — a head we own and a tail we also need to reach. Safe Rust will not let one chain be owned twice, so this chapter is where we earn the `unsafe` keyword. Along the way we meet Miri, stacked borrows, and the rules you have to obey when you hold a raw pointer.
- Chapter VI
A Production Unsafe Deque
We rebuild std::collections::LinkedList: a generic doubly-linked deque on raw pointers, with the variance, drop-check, panic safety, trait bouquet, and cursor API that a real collection has to ship. This is the chapter where the unsafe-Rust theory from the queue becomes a checklist.
- Chapter VII
A Bunch of Silly Lists
We made all the obvious lists. The point of this short closing chapter is to break the assumption that a linked list is a chain of heap nodes. A linked list is any chain of cells where each cell points at the next; where the cells live is up to you.