Got any issues or want to check out all the final code at once?
Everything’s on Github!

NOTE: The current edition of this book is written against Rust 2018,
which was first released with rustc 1.31 (Dec 8, 2018). If your rust toolchain
is new enough, the Cargo.toml file that cargo new creates should contain the
line edition = "2018" (or if you’re reading this in the far future, perhaps
some even larger number!). Using an older toolchain is possible, but unlocks
a secret hardmode, where you get extra compiler errors that go completely
unmentioned in the text of this book. Wow, sounds like fun!

I fairly frequently get asked how to implement a linked list in Rust. The
answer honestly depends on what your requirements are, and it’s obviously not
super easy to answer the question on the spot. As such I’ve decided to write
this book to comprehensively answer the question once and for all.

In this series I will teach you basic and advanced Rust programming
entirely by having you implement 6 linked lists. In doing so, you should
learn:

• The following pointer types: &, &mut, Box, Rc, Arc, *const, *mut, NonNull(?)
• Ownership, borrowing, inherited mutability, interior mutability, Copy
• All The Keywords: struct, enum, fn, pub, impl, use, …
• Pattern matching, generics, destructors
• Testing, installing new toolchains, using miri
• Unsafe Rust: raw pointers, aliasing, stacked borrows, UnsafeCell, variance

Yes, linked lists are so truly awful that you deal with all of these concepts in
making them real.

Everything’s in the sidebar (may be collapsed on mobile), but for quick
reference, here’s what we’re going to be making:

1. A Bad Singly-Linked Stack
2. An Ok Singly-Linked Stack
3. A Persistent Singly-Linked Stack
4. A Bad But Safe Doubly-Linked Deque
5. An Unsafe Singly-Linked Queue
6. TODO: An Ok Unsafe Doubly-Linked Deque
7. Bonus: A Bunch of Silly Lists

Just so we’re all the same page, I’ll be writing out all the commands that I
feed into my terminal. I’ll also be using Rust’s standard package manager, Cargo,
to develop the project. Cargo isn’t necessary to write a Rust program, but it’s
so much better than using rustc directly. If you just want to futz around you
can also run some simple programs in the browser via play.rust-lang.org.

In later sections, we’ll be using “rustup” to install extra Rust tooling.
I strongly recommend installing all of your Rust toolchains using rustup.

Let’s get started and make our project:

> cargo new --lib lists
> cd lists

We’ll put each list in a separate file so that we don’t lose any of our work.

It should be noted that the authentic Rust learning experience involves
writing code, having the compiler scream at you, and trying to figure out
what the heck that means. I will be carefully ensuring that this occurs as
frequently as possible. Learning to read and understand Rust’s generally
excellent compiler errors and documentation is incredibly important to
being a productive Rust programmer.

Although actually that’s a lie. In writing this I encountered way more
compiler errors than I show. In particular, in the later chapters I won’t be
showing a lot of the random “I typed (copy-pasted) bad” errors that you
expect to encounter in every language. This is a guided tour of having the
compiler scream at us.

We’re going to be going pretty slow, and I’m honestly not going to be very
serious pretty much the entire time. I think programming should be fun, dang it!
If you’re the type of person who wants maximally information-dense, serious, and
formal content, this book is not for you. Nothing I will ever make is for you.
You are wrong.

Just so we’re totally 100% clear: I hate linked lists. With
a passion. Linked lists are terrible data structures. Now of course there’s
several great use cases for a linked list:

• You want to do a lot of splitting or merging of big lists. A lot.
• You’re doing some awesome lock-free concurrent thing.
• You’re writing a kernel/embedded thing and want to use an intrusive list.
• You’re using a pure functional language and the limited semantics and absence
  of m