Learn Rust Series (#45) - Mini Project: A Doubly-Linked List, Safe then Unsafe
Published on HivePostify by @scipio · Wed Sep 02 2026
Learn Rust Series (#45) - Mini Project: A Doubly-Linked List, Safe then Unsafe
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 > 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 (#1) - Introduction to Rust](https://hive.blog/hive-196387/@scipio/learn-rust-series-1-introduction-to-rust) - [Learn Rust Series (#2) - Variables, Types, Functions](https://hive.blog/hive-196387/@scipio/learn-rust-series-2-variables-types-functions) - [Learn Rust Series (#3) - Ownership & Borrowing](https://hive.blog/hive-196387/@scipio/learn-rust-series-3-ownership-borrowing) - [Learn Rust Series (#4) - Control Flow & Pattern Matching](https://hive.blog/hive-196387/@scipio/learn-rust-series-4-control-flow-pattern-matching) - [Learn Rust Series (#5) - Structs & Enums](https://hive.blog/hive-196387/@scipio/learn-rust-series-5-structs-enums) - [Learn Rust Series (#6) - Error Handling](https://hive.blog/hive-196387/@scipio/learn-rust-series-6-error-handling) - [Learn Rust Series (#7) - Collections](https://hive.blog/hive-196387/@scipio/learn-rust-series-7-collections) - [Learn Rust Series (#8) - Traits & Generics](https://hive.blog/hive-196387/@scipio/learn-rust-series-8-traits-generics) - [Learn Rust Series (#9) - Modules & Crates](https://hive.blog/hive-196387/@scipio/learn-rust-series-9-modules-crates) - [Learn Rust Series (#10) - Lifetimes](https://hive.blog/hive-196387/@scipio/learn-rust-series-10-lifetimes) - [Learn Rust Series (#11) - Closures & the Iterator Trait](https://hive.blog/hive-196387/@scipio/learn-rust-series-11-closures-the-iterator-trait) - [Learn Rust Series (#12) - Smart Pointers: Box, Rc & RefCell](https://hive.blog/hive-196387/@scipio/learn-rust-series-12-smart-pointers-box-rc-refcell) - [Learn Rust Series (#13) - Concurrency: Threads, Channels, Arc & Mutex](https://hive.blog/hive-196387/@scipio/learn-rust-series-13-concurrency-threads-channels-arc-mutex) - [Learn Rust Series (#14) - Mini Project: A Command-Line To-Do App](https://hive.blog/hive-196387/@scipio/learn-rust-series-14-mini-project-a-command-line-to-do-app) - [Learn Rust Series (#15) - Trait Objects & Dynamic Dispatch](https://hive.blog/hive-196387/@scipio/learn-rust-series-15-trait-objects-dynamic-dispatch) - [Learn Rust Series (#16) - Static vs Dynamic Dispatch](https://hive.blog/hive-196387/@scipio/learn-rust-series-16-static-vs-dynamic-dispatch) - [Learn Rust Series (#17) - Associated Types vs Generic Parameters](https://hive.blog/hive-196387/@scipio/learn-rust-series-17-associated-types-vs-generic-parameters) - [Learn Rust Series (#18) - Operator Overloading with std::ops](https://hive.blog/hive-196387/@scipio/learn-rust-series-18-operator-overloading-with-stdops) - [Learn Rust Series (#19) - Deref, DerefMut & Deref Coercion](https://hive.blog/hive-196387/@scipio/learn-rust-series-19-deref-derefmut-deref-coercion) - [Learn Rust Series (#20) - Drop & Deterministic Destruction (RAII)](https://hive.blog/hive-196387/@scipio/learn-rust-series-20-drop-deterministic-destruction-raii) - [Learn Rust Series (#21) - From, Into, TryFrom & Idiomatic Conversions](https://hive.blog/hive-196387/@scipio/learn-rust-series-21-from-into-tryfrom-idiomatic-conversions) - [Learn Rust Series (#22) - Deriving Common Traits](https://hive.blog/hive-196387/@scipio/learn-rust-series-22-deriving-common-traits) - [Learn Rust Series (#23) - The Orphan Rule & Trait Coherence](https://hive.blog/hive-196387/@scipio/learn-rust-series-23-the-orphan-rule-trait-coherence) - [Learn Rust Series (#24) - Blanket Implementations & the Newtype Pattern](https://hive.blog/hive-196387/@scipio/learn-rust-series-24-blanket-implementations-the-newtype-pattern) - [Learn Rust Series (#25) - Marker Traits: Sized, Send, Sync & Copy](https://hive.blog/hive-196387/@scipio/learn-rust-series-25-marker-traits-sized-send-sync-copy) - [Learn Rust Series (#26) - Const Generics: Types That Depend on Values](https://hive.blog/hive-196387/@scipio/learn-rust-series-26-const-generics-types-that-depend-on-values) - [Learn Rust Series (#27) - Generic Associated Types & Lending Iterators](https://hive.blog/hive-196387/@scipio/learn-rust-series-27-generic-associated-types-lending-iterators) - [Learn Rust Series (#28) - Sealed Traits & Designing Stable APIs](https://hive.blog/hive-196387/@scipio/learn-rust-series-28-sealed-traits-designing-stable-apis) - [Learn Rust Series (#29) - Typestate Programming: State Machines in the Type System](https://hive.blog/hive-196387/@scipio/learn-rust-series-29-typestate-programming-state-machines-in-the-type-system) - [Learn Rust Series (#30) - Mini Project: A Generic Units-of-Measure Library](https://hive.blog/hive-196387/@scipio/learn-rust-series-30-mini-project-a-generic-units-of-measure-library) - [Learn Rust Series (#31) - Move Semantics Deep Dive](https://hive.blog/hive-196387/@scipio/learn-rust-series-31-move-semantics-deep-dive) - [Learn Rust Series (#32) - Interior Mutability: Cell & RefCell](https://hive.blog/hive-196387/@scipio/learn-rust-series-32-interior-mutability-cell-refcell) - [Learn Rust Series (#33) - Rc Internals: Reference Counting & Shared Ownership](https://hive.blog/hive-196387/@scipio/learn-rust-series-33-rc-internals-reference-counting-shared-ownership) - [Learn Rust Series (#34) - Arc: Thread-Safe Reference Counting & Its Cost](https://hive.blog/hive-196387/@scipio/learn-rust-series-34-arc-thread-safe-reference-counting-its-cost) - [Learn Rust Series (#35) - Weak References & Breaking Reference Cycles](https://hive.blog/hive-196387/@scipio/learn-rust-series-35-weak-references-breaking-reference-cycles) - [Learn Rust Series (#36) - Cow: Clone-on-Write for Borrow-or-Own APIs](https://hive.blog/hive-196387/@scipio/learn-rust-series-36-cow-clone-on-write-for-borrow-or-own-apis) - [Learn Rust Series (#37) - Pin & Self-Referential Structs](https://hive.blog/hive-196387/@scipio/learn-rust-series-37-pin-self-referential-structs) - [Learn Rust Series (#38) - PhantomData, Zero-Sized Types & Marker Lifetimes](https://hive.blog/hive-196387/@scipio/learn-rust-series-38-phantomdata-zero-sized-types-marker-lifetimes) - [Learn Rust Series (#39) - Variance: Covariance, Contravariance & Why It Matters](https://hive.blog/hive-196387/@scipio/learn-rust-series-39-variance-covariance-contravariance-why-it-matters) - [Learn Rust Series (#40) - Arena & Bump Allocation Patterns](https://hive.blog/hive-196387/@scipio/learn-rust-series-40-arena-bump-allocation-patterns) - [Learn Rust Series (#41) - Building Your Own Smart Pointer](https://hive.blog/hive-196387/@scipio/learn-rust-series-41-building-your-own-smart-pointer) - [Learn Rust Series (#42) - Drop Order, the Drop Check & Leak Safety](https://hive.blog/hive-196387/@scipio/learn-rust-series-42-drop-order-the-drop-check-leak-safety) - [Learn Rust Series (#43) - std::mem: swap, replace, take & forget](https://hive.blog/hive-196387/@scipio/learn-rust-series-43-stdmem-swap-replace-take-forget) - [Learn Rust Series (#44) - Higher-Ranked Trait Bounds & Lifetime Elision](https://hive.blog/hive-196387/@scipio/learn-rust-series-44-higher-ranked-trait-bounds-lifetime-elision) - [Learn Rust Series (#45) - Mini Project: A Doubly-Linked List, Safe then Unsafe](https://hive.blog/hive-196387/@scipio/learn-rust-series-45-mini-project-a-doubly-linked-list-safe-then-unsafe) (this post)
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: rust fn run 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 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 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: rust 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 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: rust fn longer (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: rust enum List { Cons(i32, Box ), 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: rust use std::rc::Rc; use std::cell::RefCell;
// If BOTH directions owned with Rc, we build a cycle that leaks. struct Node { next: Option >>, prev: Option >> }
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.borrowmut().next = Some(Rc::clone(&b)); b.borrowmut().prev = Some(Rc::clone(&a)); // strong cycle formed here println!("a strong count = {}", Rc::strongcount(&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 >; 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): rust use std::rc::{Rc, Weak}; use std::cell::RefCell;
type Link = Option >>;
struct Node { value: i32, next: Link, prev: Option >>, // weak: does not own }
struct DoublyLinkedList { head: Link, tail: Option >> }
impl DoublyLinkedList { fn new() -> DoublyLinkedList { DoublyLinkedList { head: None, tail: None } }
fn pushfront(&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.borrowmut().prev = Some(Rc::downgrade(&node)), None => self.tail = Some(Rc::downgrade(&node)), } self.head = Some(node); }
fn tovec(&self) -> Vec { 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.pushfront(3); list.pushfront(2); list.pushfront(1); println!("{:?}", list.tovec()); // [1, 2, 3] }
Walk through pushfront. 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 borrowmut(), 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 > 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::intoraw and Box::fromraw, 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: rust use std::ptr::NonNull;
struct Node { value: i32, next: Option >, prev: Option > } struct RawList { head: Option >, tail: Option >, len: usize }
impl RawList { fn new() -> RawList { RawList { head: None, tail: None, len: 0 } }
fn pushfront(&mut self, value: i32) { let node = NonNull::new(Box::intoraw(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.asmut().prev = Some(node) }, None => self.tail = Some(node), } self.head = Some(node); self.len += 1; }
fn tovec(&self) -> Vec { 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.asref().value); cursor = node.asref().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::fromraw(node.asptr()); cursor = boxed.next; } } } }
fn main() { let mut list = RawList::new(); list.pushfront(3); list.pushfront(2); list.pushfront(1); println!("{:?} len {}", list.tovec(), list.len); // [1, 2, 3] len 3 }
Box::intoraw 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::fromraw, which is the exact inverse of intoraw: 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: rust use std::collections::VecDeque;
fn main() { let mut dq = VecDeque::new(); dq.pushfront(1); dq.pushback(2); dq.pushfront(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: rust 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] }
Tags: #stem#stemsocial#steemstem#rust#programming