Implementing a Linked List in Rust

Memory, Iterators, Pointers, and Recursive Types

Photo by Patrick Robert Doyle on Unsplash

I’ve been pretty dedicated to learning and sharing about Rust lately. I also have an ongoing thing with data structures — they’re like little puzzle boxes; like a conglomerate of abstract simple-machines whose unique structures have inherent advantages and disadvantages. And even more so in Rust, since I get to think about how they actually are laid out in memory. So I decided I’d try to implement a Linked List in Rust flavor. On this Linked List journey I’ll touch on std::mem functions, Iterators and IntoIterators, and recursive types (and therefore pointers), and I’ll attempt to satisfy the dreaded borrow checker while I’m at it!

(I assume the reader has some minimal basic knowledge of Rust!)

(EDIT: It was brought to my attention that i could probably drop the Tail type. Here’s an updated Rust Playground!)

Before we begin laying out our Linked List data structures, let’s discuss what a linked list is exactly. It’s a list composed of Nodes (we’ll call ours Links), which can exist in one of three states:

1. An empty node,
2. a node with no linked next node, but a value (a Tail node),
3. or a Link node — one with both a value and a next node.