Learn Rust Series (#45) - Mini Project: A Doubly-Linked List, Safe then Unsafe

avatar

Learn Rust Series (#45) - Mini Project: A Doubly-Linked List, Safe then Unsafe

rust-banner.png

What will I learn

  • You will learn why a doubly-linked list is famously awkward to build in safe Rust;
  • how to build a working one with Rc<RefCell<Node>> for forward links and Weak for back links;
  • how to build a faster raw-pointer version with NonNull and unsafe, including a correct Drop;
  • the real trade-offs between the two approaches, side by side;
  • why, in practice, you should almost always reach for the standard library's collections in stead.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Rust toolchain (via rustup, from rustup.rs);
  • The previous forty-four episodes, especially smart pointers (episode 12), Rc internals (episode 33), Weak and cycles (episode 35), and Drop (episode 20);
  • The ambition to learn systems programming from the ground up.

Difficulty

  • Advanced

Curriculum (of the Learn Rust Series):

Learn Rust Series (#45) - Mini Project: A Doubly-Linked List, Safe then Unsafe

The doubly-linked list is the traditional way to prove you understand a language's memory model, and in Rust it is a genuine challenge, because every node points both forward and backward, which is exactly the two-way ownership that fights the borrow checker. It is one of those data structures that feels trivial in C and turns into a rite of passage in Rust. So we are going to build it twice: first safely, with the reference-counting tools this whole phase has been sharpening, and then with raw pointers and unsafe. Doing both back to back makes the trade-offs concrete in a way that no amount of prose about "safety versus speed" ever could, and it ties together nearly everything Phase 3 covered ;-)

At the end of episode 44 I promised exactly this: a classic linked structure that Rust's ownership rules make famously awkward, built the safe way first and then, carefully, the other way. Here we are. But before we touch a single Node, let us clear last episode's homework, because episode 44 left three exercises on the table.

Solutions to Episode 44 Exercises

Episode 44 was higher-ranked trait bounds and lifetime elision. There were three exercises, and here is full, runnable code for each.

Exercise 1 asked for an HRTB-bounded runner that builds a local Vec inside itself and calls the closure on a slice of it:

fn run<F: for<'a> Fn(&'a [i32]) -> i32>(f: F) -> i32 {
    let v = vec![1, 2, 3, 4];
    f(&v)
}
fn main() { println!("{}", run(|s| s.iter().sum())); } // 10

The for<'a> says the closure must accept a slice of any lifetime, which is what lets run hand it a borrow of the local v. Drop the for<'a> and write the short Fn(&[i32]) -> i32 form and it still compiles, because the compiler inserts that higher-ranked lifetime for you invisibly, exactly as we saw last time.

Exercise 2 wanted a method borrowing a &str from a String field of &self, with no lifetime annotation:

struct Doc { body: String }
impl Doc { fn head(&self) -> &str { &self.body[..1] } }
fn main() { println!("{}", Doc { body: "hello".into() }.head()); } // h

No 'a is needed because elision rule three settles it: with a &self in play, every elided output lifetime borrows from self. The full form would be fn head<'a>(&'a self) -> &'a str, and elision simply spares you from typing it.

Exercise 3 was the two-input case that elision cannot resolve, so it forces a shared 'a:

fn longer<'a>(x: &'a str, y: &'a str) -> &'a str { if x.len() > y.len() { x } else { y } }
fn main() { println!("{}", longer("aaa", "bb")); } // aaa

Two reference inputs and no self means rules two and three both fail, and the compiler cannot guess which input the output borrows from. Writing 'a on both inputs and the output states the promise the body actually keeps. Right, homework cleared. Now, the list.

Why it is hard

A singly-linked list is easy in Rust, because ownership only ever flows one way. Each node owns the next one with a Box, and when the head drops it drops its child, which drops its child, all the way down:

enum List { Cons(i32, Box<List>), Nil }
use self::List::{Cons, Nil};
fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Nil))));
    if let Cons(v, _) = &list { println!("head {v}"); } // head 1
}

A doubly-linked list breaks that comfortable picture. Now node A owns node B forward, while B also points back at A. The instant you make both directions owning, you have a strong reference cycle - the exact leak we studied in episode 35 - and the list never frees itself. Here is that mistake made concrete, so you can see it rather than take my word for it:

use std::rc::Rc;
use std::cell::RefCell;

// If BOTH directions owned with Rc, we build a cycle that leaks.
struct Node { next: Option<Rc<RefCell<Node>>>, prev: Option<Rc<RefCell<Node>>> }

fn main() {
    let a = Rc::new(RefCell::new(Node { next: None, prev: None }));
    let b = Rc::new(RefCell::new(Node { next: None, prev: None }));
    a.borrow_mut().next = Some(Rc::clone(&b));
    b.borrow_mut().prev = Some(Rc::clone(&a)); // strong cycle formed here
    println!("a strong count = {}", Rc::strong_count(&a)); // 2 -- and it never returns to 0
}

When main ends, a and b go out of scope, but each is still held alive by the other's strong Rc, so neither refcount ever reaches zero, and neither node's memory is ever reclaimed. That is the trap. The safe solution is the lesson of episode 35: pick one owning direction and make the other one weak.

The safe version: Rc, RefCell, and Weak

Forward links own their nodes with Rc<RefCell<Node>>; backward links use Weak, which points without owning, so no cycle can form. This combines three tools from earlier in the phase: Rc for shared ownership (episode 33), RefCell for interior mutability so we can rewrite a node's prev after it exists (episode 32), and Weak to break the cycle (episode 35):

use std::rc::{Rc, Weak};
use std::cell::RefCell;

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

struct Node {
    value: i32,
    next: Link,
    prev: Option<Weak<RefCell<Node>>>, // weak: does not own
}

struct DoublyLinkedList { head: Link, tail: Option<Weak<RefCell<Node>>> }

impl DoublyLinkedList {
    fn new() -> DoublyLinkedList { DoublyLinkedList { head: None, tail: None } }

    fn push_front(&mut self, value: i32) {
        let node = Rc::new(RefCell::new(Node { value, next: self.head.take(), prev: None }));
        match &node.borrow().next {
            Some(next) => next.borrow_mut().prev = Some(Rc::downgrade(&node)),
            None => self.tail = Some(Rc::downgrade(&node)),
        }
        self.head = Some(node);
    }

    fn to_vec(&self) -> Vec<i32> {
        let mut out = Vec::new();
        let mut cursor = self.head.clone();
        while let Some(node) = cursor {
            out.push(node.borrow().value);
            cursor = node.borrow().next.clone();
        }
        out
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.push_front(3);
    list.push_front(2);
    list.push_front(1);
    println!("{:?}", list.to_vec()); // [1, 2, 3]
}

Walk through push_front. We build the new node with its next pointing at whatever was previously the head - self.head.take() moves the old head out and leaves None behind, so ownership transfers cleanly. Then, if there was an old head, we reach into it and set its prev to a Weak handle on the new node via Rc::downgrade; if the list was empty, this new node is also the tail, so we record a weak handle to it there. Finally the new node becomes the head. The Rc::downgrade calls are the crux: every backward link is a Weak, so no matter how the list is shaped, there is never a strong cycle to leak.

It works, and it is fully safe. But look hard at the cost, because this is the whole reason the second half of the episode exists. Every node is a separate heap allocation carrying a strong count, a weak count, and a RefCell borrow flag. Every single field access goes through a runtime-checked borrow() or borrow_mut(), and a careless borrow pattern - holding one borrow while trying to take another - does not fail to compile, it panics at runtime. Traversal clones an Rc at every step, bumping and later dropping a reference count each time. It is correct and idiomatic Rust, but it is emphatically not what a systems programmer pictures when they say "linked list": a lean chain of nodes you walk with a bare pointer.

The unsafe version: raw pointers

For the performance a linked list is usually chosen for, you drop to raw pointers. Each node holds Option<NonNull<Node>> links both ways - NonNull is a raw pointer that is guaranteed non-null and is the idiomatic choice for this exact job (we met it back in episode 41). Allocations are handed to and reclaimed from the heap with Box::into_raw and Box::from_raw, and the critical addition, the part that separates a working list from a memory catastrophe, is a correct Drop that frees every node exactly once:

use std::ptr::NonNull;

struct Node { value: i32, next: Option<NonNull<Node>>, prev: Option<NonNull<Node>> }
struct RawList { head: Option<NonNull<Node>>, tail: Option<NonNull<Node>>, len: usize }

impl RawList {
    fn new() -> RawList { RawList { head: None, tail: None, len: 0 } }

    fn push_front(&mut self, value: i32) {
        let node = NonNull::new(Box::into_raw(Box::new(Node { value, next: self.head, prev: None }))).unwrap();
        // SAFETY: node is freshly allocated; head, if present, is still valid.
        match self.head {
            Some(mut old) => unsafe { old.as_mut().prev = Some(node) },
            None => self.tail = Some(node),
        }
        self.head = Some(node);
        self.len += 1;
    }

    fn to_vec(&self) -> Vec<i32> {
        let mut out = Vec::new();
        let mut cursor = self.head;
        // SAFETY: every node pointer is valid until the list is dropped.
        while let Some(node) = cursor {
            unsafe { out.push(node.as_ref().value); cursor = node.as_ref().next; }
        }
        out
    }
}

impl Drop for RawList {
    fn drop(&mut self) {
        let mut cursor = self.head;
        while let Some(node) = cursor {
            // SAFETY: reclaim each leaked Box exactly once, in order.
            unsafe { let boxed = Box::from_raw(node.as_ptr()); cursor = boxed.next; }
        }
    }
}

fn main() {
    let mut list = RawList::new();
    list.push_front(3);
    list.push_front(2);
    list.push_front(1);
    println!("{:?} len {}", list.to_vec(), list.len); // [1, 2, 3] len 3
}

Box::into_raw is the move that starts it all: it consumes a Box, hands you the bare pointer inside, and - crucially - forgets to run the destructor, so the heap allocation is now leaked on purpose, owned by nobody the compiler tracks. From that point on, keeping it correct is entirely on you. Notice how each unsafe block carries a // SAFETY: comment: that is not decoration, it is the discipline. Every unsafe block is a place where you, not the compiler, are personally vouching that the pointers are valid, and writing down why is how you keep that promise honest.

The Drop is where the whole thing lives or dies. It walks from the head, and for each node it calls Box::from_raw, which is the exact inverse of into_raw: it reclaims ownership of that leaked allocation into a real Box, reads the next pointer out of it, and then - because the boxed binding goes out of scope at the end of the loop body - drops it and frees the memory. Free each node exactly once and the list is airtight. Free one twice and you have a double free; free one zero times and you have a leak. There is no borrow checker standing behind you here, which is precisely the point of the exercise.

Safe versus unsafe, side by side

Having built both, it is worth stating the trade plainly, because it is the real lesson. The safe DoublyLinkedList costs you, per node, one heap allocation plus the Rc bookkeeping (two counts) and a RefCell flag, a runtime borrow check on every access, and a reference-count bump on every traversal step - and in exchange the compiler guarantees you cannot leak a cycle, cannot double free, and cannot read freed memory. The RawList costs you a plain Node per element with no count and no flag, and traversal is a bare pointer walk with nothing between you and the machine - and in exchange you take on the entire burden of proving, by hand, that every pointer is live when you use it and freed exactly once when you are done.

That is the trade in one sentence: the safe version buys correctness with runtime overhead the compiler polices; the unsafe version buys speed by moving that policing into your own head. Neither is "better" in the abstract. The unsafe version is faster and leaner; the safe version is one you can hand to a teammate at 2 a.m. without lying awake wondering whether they got the Drop right.

The real advice

So here is the honest conclusion, the one I would be cheating you to leave out: do not write your own linked list in production. I mean it. The standard library ships std::collections::LinkedList for the genuinely rare case you truly need the linked-list shape - stable addresses, O(1) splice - and it has already solved the unsafe correctness problem, reviewed by people who do this for a living. Far more often, though, what you actually want is a Vec or a VecDeque, which are contiguous, cache-friendly, and faster than any linked list for almost every real workload, because modern CPUs adore sequential memory and despise chasing pointers all over the heap:

use std::collections::VecDeque;

fn main() {
    let mut dq = VecDeque::new();
    dq.push_front(1);
    dq.push_back(2);
    dq.push_front(0);
    println!("{:?}", dq); // [0, 1, 2]
}

A VecDeque gives you cheap pushes and pops at both ends - the one thing people reach to a linked list for - while storing everything in a contiguous ring buffer, so it stays cache-friendly. And even a plain Vec handles front operations perfectly well; it just shifts the elements over, which sounds expensive but is usually cheaper than the pointer-chasing a list would do, again thanks to cache locality:

fn main() {
    let mut v = vec![1, 2, 3];
    v.insert(0, 0); // front insert: shifts, but stays contiguous
    v.push(4);
    println!("{:?}", v); // [0, 1, 2, 3, 4]
}

The value of this whole exercise was never the list itself. It is that you now understand, from the inside, exactly why the safe version is heavy, exactly what the unsafe version buys and risks, and exactly why reaching for a Vec is usually the wise move. That judgement - knowing which tool the problem actually needs - is the real takeaway of Phase 3.

How this compares to other languages

Since quite some of you came to Rust from the Learn Python Series, a look sideways is illuminating, because the doubly-linked list is where Rust feels hardest relative to other languages, and it is worth understanding precisely why.

In Python, a doubly-linked list is a five-minute exercise: each node is an object with next and prev attributes, you assign them freely, and the garbage collector cleans up whenever, cycle or no cycle (CPython's cycle collector handles the back-and-forth references automatically). It is easy - right up until you want it to be fast, at which point you discover every node is a separate heap object with a dictionary of attributes, and you would have been far better off with a plain list (which is a dynamic array, Python's Vec) or collections.deque (a doubly-linked list of blocks, which is Python quietly admitting that pointer-per-element is a bad idea). The convenience is real; so is the cost, and it is the same cost our safe version pays.

In C, the doubly-linked list is folklore - the canonical struct node { int v; struct node *next, *prev; } with malloc and free - and it is genuinely simple to write. The catch is that nothing checks you. Forget one free and you leak; call it twice and you corrupt the heap; follow a pointer to a node you already freed and you get undefined behaviour that may crash today or silently eat your data next Tuesday. Our RawList is that exact C program, with the unsafe keyword marking the spots where the C-level danger lives - and with a Box and a Drop giving it a real destructor. C++ with std::list sits closer to Rust's answer: RAII runs the destructor for you, so the memory management is handled, but the language still lets you hold a dangling iterator into a node you erased, with no complaint until it bites.

In Go, as in Python, garbage collection means the cycle never leaks and you never write free; container/list is right there in the standard library. The familiar trade across this whole series shows up one more time: the GC languages buy you a linked list that is trivial to write and impossible to leak, and pay for it with a runtime tracing collector and unpredictable pauses. Rust refuses that bargain and hands you two honest choices instead - pay the Rc/Weak/RefCell overhead and let the compiler prove you safe, or go raw and prove it yourself. The linked list is simply the place where that refusal is felt most sharply.

What did we actually learn?

  • A doubly-linked list is hard in Rust because two-way ownership is a strong reference cycle, and a cycle of owning Rcs never reaches refcount zero, so it leaks - the very trap episode 35 was about.
  • The safe build owns forward with Rc<RefCell<Node>> and points back with Weak, so no cycle forms. It is correct and idiomatic, at the cost of per-node allocations, reference counts, RefCell borrow flags, runtime-checked borrows that can panic, and a refcount bump on every step.
  • The unsafe build uses Option<NonNull<Node>> links both ways, Box::into_raw/from_raw to manage the heap, and a hand-written Drop that reclaims each node exactly once. It is much leaner and faster, at the cost of you guaranteeing pointer validity - every unsafe block earns a // SAFETY: note explaining why it is sound.
  • The trade is symmetric, not one-sided: the safe version moves the policing into the compiler at a runtime price; the unsafe version moves it into your head for raw speed.
  • The real advice: do not roll your own in production. Reach for Vec or VecDeque first - contiguous and cache-friendly beats pointer-chasing almost every time - and for std::collections::LinkedList in the rare case you truly need the linked shape.

Exercises

Three exercises, from gentle to chewier. Type them yourself before the next episode - a linked list is one of those things that only truly clicks once you have watched your own pointers behave.

  1. Add a push_back(&mut self, value: i32) to the safe DoublyLinkedList using the tail weak pointer: upgrade it with Weak::upgrade to get an Rc to the current tail, attach the new node after it, and update both the old tail's next and the list's tail. Test that push_back(1); push_back(2) yields [1, 2].
  2. Add a pop_front(&mut self) -> Option<i32> to the RawList that unlinks the head node, reclaims it with Box::from_raw, fixes up the new head's prev (and the tail if the list becomes empty), decrements len, and returns the value. Confirm popping every element leaves an empty list that still drops cleanly.
  3. Give the safe list a to_vec_reversed(&self) -> Vec<i32> that starts from tail, upgrades each Weak prev pointer as it walks backward, and collects the values. Confirm it is the exact reverse of to_vec.

Dat was Phase 3, en wat een rit! Bedankt voor het meelezen, en tot de volgende keer, waar we het rustiger aan gaan doen met foutafhandeling ;-)

@scipio

stem stemsocial steemstem rust programming
0
0
0.000
0 comments