Linked Lists (the Rite of Passage)

A linked list is a backyard scavenger hunt. Each clue is a slip of paper with two things on it — a message, and where to find the next slip. You start at the first clue, read what it says, walk to the spot it points to, pick up the next clue, and keep going until one of the slips says you are done. The slips are scattered all over the yard. They do not sit in a neat row. The only thread holding the hunt together is each slip remembering exactly one other slip — the next one. Every linked list you will ever build is that scavenger hunt dressed up in different clothing.

The reason this data structure is the rite of passage for a Rust programmer is that it is the first time the language fights you. Anywhere else — Python, JavaScript, even C — you can write a linked list in twenty minutes flat. Rust makes you sit in a chair and answer hard questions. Who owns the next clue? If the second clue is also pointed at by something else, what happens when one owner throws it away? A guy named Aria Beingessner spent a whole book — Learning Rust With Entirely Too Many Linked Lists, written in 2015 while he was working on the Rust standard library at Mozilla — walking through six different ways to build one. The book is a hundred pages. The lesson under it is that Rust takes the bookkeeping you used to do in your head and forces you to write it down. Once you finish the fight, you understand the rest of the language.

The easiest version of the hunt is the one where each clue is owned outright by the clue before it. Slip 1 holds slip 2 inside it. Slip 2 holds slip 3. Slip 3 holds nothing — that is the end of the trail. In Rust the wrapper that means "I am the only owner of this thing on the heap" is called Box. A Box<Clue> is a slip of paper with a chain through the corner running to exactly one other slip. Nothing else can reach in and grab the next clue except the slip that owns it.

struct Clue {
    text: &'static str,
    next: Option<Box<Clue>>,
}

fn run_box_hunt() {
    let third = Box::new(Clue {
        text: "under the slide",
        next: None,
    });
    let second = Box::new(Clue {
        text: "behind the oak tree",
        next: Some(third),
    });
    let first = Clue {
        text: "start at the mailbox",
        next: Some(second),
    };

    let mut current: Option<&Clue> = Some(&first);
    let mut step = 1;
    while let Some(node) = current {
        println!("clue {step}: {}", node.text);
        current = node.next.as_deref();
        step += 1;
    }
}

Read the struct first. A Clue has a text and a next. The next is Option<Box<Clue>>. The Option is how Rust spells "maybe nothing" — it is Some(box) when another slip follows, and None when the trail ends. There is no null pointer in Rust. The compiler will not let you forget to check. Then read run_box_hunt. We build the trail from the end backwards, because each slip has to own the one after it — third has no next, second owns third, first owns second. To walk the hunt we hand a borrowed reference to a current variable and follow node.next.as_deref() until it returns None. The as_deref is the bit that turns Option<Box<Clue>> into Option<&Clue> so we can peek without taking ownership. We are tourists on the trail, not the owner of it.

The Box version works perfectly until you want two hunters to share the same trail. Imagine your little brother wants to play too, starting at the same first clue. If first owns second which owns third, your brother cannot hold any of those slips at the same time you do — Rust enforces a rule of exactly one owner per thing, and the compiler will not let you hand him a copy of first while you still have it. The same problem shows up if anyone wants to rewrite a clue mid-hunt while you are walking the trail. You own the slip. You alone get to change it. Nobody else can reach in.

To let two hunters share the trail and let one of them edit a slip while the other reads it, you need two new wrappers stacked on top of each other. The outer wrapper is Rc — short for reference-counted. An Rc<Clue> is a slip of paper with a little tally mark on the back showing how many people are holding it right now. When you call .clone() on an Rc, you do not copy the slip — you just bump the tally. When somebody walks away and drops their handle, the tally goes down. When the tally hits zero, the slip is thrown out. That solves the sharing problem. But Rc alone is read-only. To let your brother edit the middle slip, you wrap the inside with RefCell. A RefCell<Clue> is a slip with a tiny logbook taped to it. Anyone who wants to read the slip writes "reading" in the book first. Anyone who wants to edit writes "editing." The book enforces the rule at runtime — many readers at once is fine, but an editor needs the slip all to themselves. The combination Rc<RefCell<Clue>> is the Rust idiom for "shared, mutable thing on the heap." It is also the cleanest singly-linked list you can build.

type Link = Option<Rc<RefCell<SharedClue>>>;

struct SharedClue {
    text: String,
    next: Link,
}

fn rc_clue(text: &str, next: Link) -> Rc<RefCell<SharedClue>> {
    Rc::new(RefCell::new(SharedClue {
        text: String::from(text),
        next,
    }))
}

fn walk(start: &Rc<RefCell<SharedClue>>, hunter: &str) {
    let mut current = Some(start.clone());
    let mut step = 1;
    while let Some(node) = current {
        let borrowed = node.borrow();
        println!("{hunter} reads clue {step}: {}", borrowed.text);
        current = borrowed.next.clone();
        step += 1;
    }
}

fn run_shared_hunt() {
    let third = rc_clue("under the slide", None);
    let second = rc_clue("behind the oak tree", Some(third));
    let first = rc_clue("start at the mailbox", Some(second.clone()));

    walk(&first, "hunter A");
    second.borrow_mut().text = String::from("behind the oak tree (now with a sticker)");
    println!("hunter B rewrote the middle clue");
    walk(&first, "hunter A");
}

The Link type alias is Option<Rc<RefCell<SharedClue>>> — exactly the same shape as before, just with the new wrappers in the middle. rc_clue is a tiny helper to keep the construction readable. The interesting function is walk. It takes an &Rc<RefCell<SharedClue>>, clones the Rc to bump the tally, then loops. Inside the loop, node.borrow() opens the logbook for reading. We print the text, then clone the next link to advance. When the loop ends, all the clones are dropped and the tallies go back down. In run_shared_hunt we build the trail, walk it once, then call second.borrow_mut() to grab an editor's lock on the middle slip and rewrite its text. Walk the trail a second time and the change is visible — because both walks are following the same physical slips, not copies.

Run the program.

-- box hunt: one owner, one trail --
clue 1: start at the mailbox
clue 2: behind the oak tree
clue 3: under the slide

-- shared hunt: two hunters, edits visible to both --
hunter A reads clue 1: start at the mailbox
hunter A reads clue 2: behind the oak tree
hunter A reads clue 3: under the slide
hunter B rewrote the middle clue
hunter A reads clue 1: start at the mailbox
hunter A reads clue 2: behind the oak tree (now with a sticker)
hunter A reads clue 3: under the slide

Look at line 12. Hunter A walked the trail twice. The first walk printed behind the oak tree. Between the walks, hunter B opened the middle slip and added a sticker. The second walk printed behind the oak tree (now with a sticker) — same slip, same position in the trail, new text. That is the whole point of Rc<RefCell>. The trail has one set of slips. Everyone with an Rc can see them. Anyone willing to grab a borrow_mut can rewrite them. Drop the last Rc and the slip is gone.

A question worth asking. Why did we have to write second.clone() when building first, but not when building second itself? Because each rc_clue call moves its next argument into the new node. second owned third outright after the second call. When we built first, we needed second to live in two places at once — inside first.next, and still bound to the local name second so we could mutate it later. The .clone() bumps the tally so both handles are valid. That is the bookkeeping Rust makes you do. In C you would have just written a pointer and hoped nobody freed the wrong one. In Rust the tally is the proof that nobody will.

The scavenger hunt has one weakness. Walking the trail is fast. Jumping to clue number 50 is slow — you have to read 1, then 2, then 3, all the way to 50, because each slip only knows the next one. That linear walk is what makes linked lists wonderful for inserting in the middle and miserable for random access. The next lesson narrows the trail to only its two ends and asks what falls out when the only moves allowed are push and pop — the structures called stacks and queues.