Linked lists

Chapter 8 introduced the pointer types. This chapter uses them to build the classic linked structure, the linked list. Linked lists are a good first test of ownership. Each operation moves a node from one owner to another, and the compiler checks every move.

The chapter goes from simple to hard. First a singly linked list, where each node points only to the next, and an algorithm that reverses it. Then four ways to write the same list, and a benchmark that compares them. The benchmark finds a size at which the list crashes the program when it is dropped. After explaining and fixing that, the chapter ends with a doubly linked list, where each node also points back to the one before.

9.1 What a linked list is

A linked list stores a sequence of values in separate nodes. Each node holds one value and a pointer to the next node. The list itself holds a pointer to the first node, called the head. The last node’s pointer is empty, which marks the end.

Figure 9.1 compares a linked list with a Vec holding the same three values.

The two structures are good at different things:

A linked list works like a treasure hunt. Each clue says where the next clue is hidden. To read the fifth clue, you must find the first four. To add a clue at the start, you write one new clue that names the old first one, and nothing else moves. A Vec works like a numbered row of lockers. Locker 5 is found in one step. A new locker at the front means renumbering the whole row.

In practice, a Vec is faster for most work. Its values are next to each other in memory, and the processor reads nearby memory quickly; chapter 15 measures that effect. The techniques you learn here for moving nodes between owners carry over to the trees and graphs of chapters 11 and 12.

In Rust, a node owns the next node through a Box, and the “empty” pointer at the end is None. So a node’s next field has type Option<Box<Node>>.

9.2 Moving nodes: take and replace

Every list operation moves a node from one owner to another. Rust has a rule that makes this tricky. You cannot move a value out of a place that you only borrowed. That would leave the place empty, and the owner would later find garbage there.

Two standard functions solve this by putting something valid in the place as they take the value out:

• option.take() returns the value inside an Option and leaves None in its place.
• std::mem::replace(&mut place, new_value) returns the old value and puts new_value in its place.

Figure 9.2 shows take on a node’s next field.

You will see these two calls in almost every listing of this chapter.

9.3 Reversing a list

The problem. Given the list 1 → 2 → 3 → 4, turn it into 4 → 3 → 2 → 1. Change the pointers; do not copy the values.

The idea. Walk the list from the front. Keep two variables: previous, the part already reversed, and current, the part not yet visited. At each step, take the first node of current, point it at previous, and make it the new front of previous. Figure 9.3 shows the state after two steps.

First, the node type and two helpers for building and reading lists:

Listing 9.1 The node and two helpers (lines 1 to 33). src/problems/linked_list.rs

//! Reverse a singly linked list, and remove nodes from it.
//!
//! Uses `Option<Box<ListNode>>` and a `while let` loop to move pointers in a
//! borrow-safe way. Removal walks a cursor: a mutable borrow of one link.

#[derive(Debug, PartialEq, Eq)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    pub fn from_slice(values: &[i32]) -> Option<Box<ListNode>> {
        let mut head = None;
        for &value in values.iter().rev() {
            head = Some(Box::new(ListNode {
                val: value,
                next: head,
            }));
        }
        head
    }

    pub fn to_vec(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut current = head;
        while let Some(node) = current {
            result.push(node.val);
            current = node.next;
        }
        result
    }
}

from_slice builds a list from a slice. It walks the slice backward, putting each value in front of the list built so far. The last value pushed is values[0], so it ends up first. Building from the back means it never needs a pointer to the end of the list.

to_vec reads a list into a Vec. It takes the list by value and consumes it. In while let Some(node) = current, each pass moves one box out of current. current = node.next then moves the rest of the list out of that node before the node is freed.

Animation 9.2 builds [1, 2, 3] with from_slice, reads it back with to_vec, and then shows what the loop does without .rev().

Now the reversal:

Listing 9.2 Reversing the list (lines 35 to 46).

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut previous = None;
    let mut current = head;

    while let Some(mut node) = current {
        current = node.next.take();
        node.next = previous;
        previous = Some(node);
    }

    previous
}

Each pass through the loop does three moves:

1. current = node.next.take(); takes the rest of the list out of the node, as in figure 9.2.
2. node.next = previous; points the node at the reversed part.
3. previous = Some(node); makes the node the front of the reversed part.

Trace it on 1 → 2 → 3:

At no moment do two variables own the same node, which is why the compiler accepts the code. The function visits each node once, so it is O(n), and it uses O(1) extra memory.

The complete file is listing 9.20 at the end of the chapter. Its tests reverse a four-element list, an empty list, and a one-element list.

9.4 Removing nodes with a cursor

The problem. Remove every node whose value equals target, in one pass. The head may match, and so may several nodes in a row.

The idea. To unlink a node, you change the link that points at it. That link is either head or the next field of the node before. So the loop holds a link, not a node. It is a &mut Option<Box<ListNode>> called the cursor.

Think of the cursor as a finger on one arrow of the chain. If the arrow points at a match, you bend the arrow past that node, and the finger stays where it is. If not, the finger moves to the next arrow.

Listing 9.3 Removing every match (lines 48 to 71). src/problems/linked_list.rs

/// Remove every node whose value is `target`, in one pass.
///
/// `cursor` is a mutable borrow of a link: first `head`, then the `next` of
/// each node that stays. A matching node is unlinked by moving its `next` into
/// the link that pointed at it. The cursor does not move after a removal,
/// because the link it holds now points at a node not yet checked.
pub fn remove_all(mut head: Option<Box<ListNode>>, target: i32) -> Option<Box<ListNode>> {
    let mut cursor = &mut head;
    while cursor.is_some() {
        let node = cursor
            .as_mut()
            .expect("checked by is_some");
        if node.val == target {
            let next = node.next.take();
            *cursor = next;
        } else {
            cursor = &mut cursor
                .as_mut()
                .expect("checked by is_some")
                .next;
        }
    }
    head
}

The loop reads:

1. let mut cursor = &mut head; puts the cursor on the head link. The head is a link like any other, so removing the first node needs no extra code.
2. cursor.as_mut() borrows the node the link points at.
3. On a match, node.next.take() moves the rest of the list out of the node. *cursor = next writes it into the link. Nothing owns the old node any more, so it is freed there.
4. Otherwise, cursor = &mut cursor...next moves the cursor to that node’s next link.

The cursor does not move after a removal. The link now points at the node that slid into place, and that node has not been checked yet. Trace it on 2 → 1 → 2 → 2 → 3 with target 2:

Each node is checked once, so the function is O(n). It uses O(1) extra memory.

Animation 9.3 plays this trace, then three unhappy cases. The target may be absent, every node may match, or the cursor may move after a removal.

The tests check the cases that break removal code. They remove a match at the head and matches in a row. They also try a target that is absent, a list where every node matches, and an empty list.

9.5 A list written as an enum

The first list separated the node type from the Option that marks the end. Another way puts both into one enum: a list is either empty, or a node holding a value and the rest of the list.

Listing 9.4 The list type (lines 1 to 13). src/bin/singly_linked_list.rs

// Singly linked list using an algebraic data type.
//
//    List<T> = Empty
//            | Node { value: T, next: Link<T> }
//
// `Empty` is the end of the list.

type Link<T> = Box<List<T>>;

pub enum List<T> {
    Empty,
    Node { value: T, next: Link<T> },
}

List<T> is generic. The T is a placeholder for the type of the values, so the same code works for a list of numbers or of strings. type Link<T> = Box<List<T>>; gives the boxed rest of the list a short name.

Listing 9.5 Creating, checking, and measuring (lines 16 to 29).

impl<T> List<T> {
    pub fn new() -> Self {
        List::Empty
    }

    pub fn is_empty(&self) -> bool {
        matches!(self, List::Empty)
    }

    pub fn len(&self) -> usize {
        match self {
            List::Empty => 0,
            List::Node { next, .. } => 1 + next.len(),
        }
    }
    // ...
}

len counts the nodes recursively: an empty list has length 0, and a node adds 1 to the length of the rest. Each call waits for the next, so a list of n nodes uses n stack frames. Section 9.7 shows where that ends.

Listing 9.6 Adding and removing at the front (lines 31 to 49).

impl<T> List<T> {
    // ...
    /// O(1)
    pub fn push_front(&mut self, value: T) {
        let old = std::mem::replace(self, List::Empty);
        *self = List::Node {
            value,
            next: Link::new(old),
        };
    }

    /// O(1)
    pub fn pop_front(&mut self) -> Option<T> {
        match std::mem::replace(self, List::Empty) {
            List::Empty => None,
            List::Node { value, next } => {
                *self = *next;
                Some(value)
            }
        }
    }
}

Both methods take &mut self, so they change the list in place. They use std::mem::replace from section 9.2. The method cannot move the old list out of *self and assign a new one later. Between those two steps, *self would be empty. replace(self, List::Empty) puts a temporary Empty in place and hands back the old list in one step.

push_front wraps the old list in a new node with the new value, and writes it back into *self.

pop_front matches on the old list. If it was Empty, there is nothing to pop, and *self is already Empty again. If it was a Node, the method writes the rest of the list back into *self with *self = *next, and returns the value. *next moves the list out of its Box.

Animation 9.4 shows both methods, then the version without replace that the compiler refuses.

The complete program is listing 9.21 at the end of the chapter. Its main pushes three values and pops them back in reverse order, the last one pushed coming out first. A list that adds and removes at the same end behaves as a stack, like the Vec in chapter 3.

$ cargo run --bin singly_linked_list
ok

9.6 Four node layouts, measured

Section 9.3 wrote a node as a struct with an Option<Box<Node>>, and section 9.5 wrote the list as an enum. Which is faster? To answer, the benchmark in this section puts four versions of the same list behind one trait. Then one piece of code can measure them all.

9.6.1 One trait for four lists

The four list types are measured by one benchmark, so they share a trait with the operations the benchmark calls.

Listing 9.7 The trait every list implements. benchmarking_examples/lists/mod.rs

//! Singly linked lists in four variants, so one benchmark loop can cover all of
//! them.
//!
//! The variants differ only in how a node is stored and in how the list frees
//! itself. `boxed` and `enum_node` free a chain of boxes recursively, which
//! overflows the stack past roughly 265,000 nodes. `boxed_drop` and `enum_drop`
//! unlink iteratively and scale.

pub mod boxed;
pub mod boxed_drop;
pub mod enum_drop;
pub mod enum_node;

/// The operations every variant supports, so the benchmark can be written once.
pub trait SinglyList<T>: Sized {
    /// A new, empty list.
    fn new() -> Self;

    /// Adds `value` to the front of the list.
    fn push_front(&mut self, value: T);

    /// Removes and returns the front value, if there is one.
    fn pop_front(&mut self) -> Option<T>;

    /// Whether the list holds nothing.
    fn is_empty(&self) -> bool;

    /// The variant's name, for benchmark output and error messages.
    fn variant() -> &'static str;
}

The trait lists the operations: new, push_front, pop_front, is_empty, and variant, which returns a name for printing. SinglyList<T>: Sized limits the trait to types whose size is known at compile time. The benchmark uses the trait only through generic functions, so the limit costs nothing. The four pub mod lines declare the four versions, each in its own file.

The first two versions are the struct form and the enum form:

Listing 9.8 Option<Box<Node<T>>>: the types, push_front, and pop_front (lines 9 to 38). benchmarking_examples/lists/boxed.rs

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> SinglyList<T> for LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn push_front(&mut self, value: T) {
        self.head = Some(Box::new(Node {
            value,
            // .take() leaves None in its place and extracts the old head
            next: self.head.take(),
        }));
    }

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            // Point the list head to the next node in line
            self.head = node.next;
            // Return the unboxed value
            node.value
        })
    }
    // ...
}

Listing 9.9 enum ListNode<T>: the types, push_front, and pop_front (lines 9 to 44). benchmarking_examples/lists/enum_node.rs

enum ListNode<T> {
    Empty,
    Next(T, Box<ListNode<T>>),
}

pub struct LinkedList<T> {
    head: ListNode<T>,
}

impl<T> SinglyList<T> for LinkedList<T> {
    fn new() -> Self {
        Self {
            head: ListNode::Empty,
        }
    }

    fn push_front(&mut self, value: T) {
        // Extract the old head and leave Empty in its place
        let old_head = std::mem::replace(&mut self.head, ListNode::Empty);

        // Wrap the old head inside a Box behind the new value
        self.head = ListNode::Next(value, Box::new(old_head));
    }

    fn pop_front(&mut self) -> Option<T> {
        let old_head = std::mem::replace(&mut self.head, ListNode::Empty);

        match old_head {
            ListNode::Empty => None,
            ListNode::Next(value, next_node) => {
                // Point the list head to the next node in the sequence
                self.head = *next_node;
                Some(value)
            }
        }
    }
    // ...
}

Each file also has is_empty and variant, which are one line each. The two files implement the trait with impl<T> SinglyList<T> for LinkedList<T>. Each uses the tool from section 9.2 that fits its type: take() on the Option in the struct version, and mem::replace on the enum.

9.6.2 What each node costs in memory

Figure 9.4 draws both lists after pushing 10, 20, and 30.

On a 64-bit machine, with u64 values, each node is 16 bytes in both versions: 8 for the value and 8 for the pointer. Option<Box<Node>> is only 8 bytes, because a Box is never null, so Rust uses the null address to mean None. The enum gets the same treatment, using a null Box to mean Empty.

The versions still differ in two ways. The enum list keeps its first node, 16 bytes, inside the list value. So every push moves those 16 bytes into a new box, where the struct version moves one 8-byte pointer. And the enum chain ends with a boxed Empty. Both lists make one allocation per push, but one of the enum’s boxes holds no value.

Animation 9.5 pushes 10, 20, and 30 onto both lists, pops one value, and then pops from two empty lists.

Two small demo programs, list_box.rs and list_enum.rs, push and pop on each version. They import the lists from the crate’s library with use systems_lab::lists::..., so every program shares one compiled copy of the list code. Both are listed at the end of the chapter.

9.7 When dropping a list crashes

Here is a short program built on the struct version:

let mut list = boxed::LinkedList::new();
for value in 0..270_000u64 {
    list.push_front(value);
}
// list goes out of scope here and is dropped

It builds the list without trouble, and then it crashes at the closing brace:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow, aborting

None of the list’s methods is recursive. The recursion is in the code the compiler generates to drop the list. To drop the list, Rust drops head. To drop a Box<Node>, it drops the node, which means dropping its fields, including next, another Box<Node>. That drops the next node, and so on. Each step is a function call nested inside the previous one, so each node adds one stack frame (figure 9.5, left).

Animation 9.6 runs both. Watch the stack on the right: one frame per node for the default drop, and never more than three for the loop.

The main thread’s stack is 8 MiB on most systems. The crash happened between 260,000 and 270,000 nodes, so each level of nesting used about 32 bytes of stack. A thread you start with std::thread::spawn gets a 2 MiB stack by default. On such a thread the limit would be about a quarter as many nodes.

The fix is to write the list’s Drop yourself, as a loop. Drop is a trait. Rust calls its drop method when a value goes out of scope. If you implement it, your code runs before the fields are dropped.

Listing 9.10 The struct version's Drop (lines 46 to 55). benchmarking_examples/lists/boxed_drop.rs

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        // Walk the chain and unlink each node before it is freed, so no node's
        // drop has to carry the rest of the list on the stack.
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

The file boxed_drop.rs repeats the types and operations of listing 9.8. Only this Drop implementation is new. Its loop reads:

1. let mut current = self.head.take(); takes the whole chain out of the list.
2. while let Some(mut node) = current moves the first box out of current.
3. current = node.next.take(); moves the rest of the chain out of that node.
4. At the end of the loop body, node goes out of scope and is freed. Its next is already None, so freeing it frees nothing else.

The loop runs in one stack frame, whatever the length of the list.

Listing 9.11 The enum version's Drop (lines 52 to 62). benchmarking_examples/lists/enum_drop.rs

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        // Take the chain out of the list first, then step it forward one node at
        // a time. Each node has already lost its `next` by the time it is freed,
        // so the drop stays on the heap.
        let mut current = std::mem::replace(&mut self.head, ListNode::Empty);
        while let ListNode::Next(_, next) = current {
            current = *next;
        }
    }
}

The enum version does the same with mem::replace and a while let ListNode::Next(_, next) = current loop. current = *next; moves the rest of the chain out of the box. Assigning to current drops its old value, a Next whose box has already been emptied, so again nothing nests.

A third demo builds a list of five million nodes and drops it:

Listing 9.12 Five million nodes, dropped with a loop. benchmarking_examples/list_drop.rs

//! Demo of the iterative `Drop` in `lists::boxed_drop`.
//!
//! The same program against `lists::boxed` aborts with a stack overflow at this
//! size, because that variant frees its chain recursively.
//!
//! Run with: cargo run --release --bin list_drop

use systems_lab::lists::{SinglyList, boxed_drop::LinkedList};

fn main() {
    const N: u64 = 5_000_000;

    let mut list = LinkedList::new();
    for value in 0..N {
        list.push_front(value);
    }
    println!("built a list of {N} nodes");

    list.pop_front();
    println!("dropping the remaining {} nodes", N - 1);

    drop(list);
    println!("dropped without recursing");
}

9.8 The benchmark

The benchmark program measures all four versions with one generic function. The full program also measures the caches of chapter 13, and is listed there. This is the part that measures the lists.

Listing 9.13 The list benchmark (lines 160 to 236). benchmarking_examples/benchmark.rs

use std::{
    hint::black_box,
    time::{Duration, Instant},
};

use systems_lab::{
    cache::{Cache, arena::LruCache as ArenaCache, rc_list::LruCache as RcCache},
    lists::{SinglyList, boxed, boxed_drop, enum_drop, enum_node},
};

// ---------------------------------------------------------------------------
// Lists: four variants, one loop
// ---------------------------------------------------------------------------

fn list_benchmark(variant: Option<&str>, elements: usize) {
    println!(
        "Singly linked list: push {} values, pop them back in order, then drop a full list",
        with_thousands(elements as u64)
    );
    println!("Best of {LIST_RUNS} runs per variant, allocator warmed up.\n");
    println!(
        "  {:<10} {:>12} {:>13} {:>13}",
        "variant", "elements", "push", "drop"
    );
    println!("  {}", "-".repeat(52));

    match variant {
        Some("box") => run_list::<boxed::LinkedList<u64>>(elements),
        Some("enum") => run_list::<enum_node::LinkedList<u64>>(elements),
        Some("box+drop") => run_list::<boxed_drop::LinkedList<u64>>(elements),
        Some("enum+drop") => run_list::<enum_drop::LinkedList<u64>>(elements),
        _ => {
            run_list::<boxed::LinkedList<u64>>(elements);
            run_list::<enum_node::LinkedList<u64>>(elements);
            run_list::<boxed_drop::LinkedList<u64>>(elements);
            run_list::<enum_drop::LinkedList<u64>>(elements);
        }
    }
}

fn run_list<L: SinglyList<u64>>(elements: usize) {
    // Warm the allocator first: without this the first variant in a process pays
    // for fresh heap pages and looks several times slower than an identical one.
    let mut warm_up = L::new();
    for value in 0..elements as u64 {
        warm_up.push_front(value);
    }
    drop(warm_up);

    let mut best_push = Duration::MAX;
    let mut best_drop = Duration::MAX;

    for _ in 0..LIST_RUNS {
        let mut list = L::new();

        let start = Instant::now();
        for value in 0..elements as u64 {
            list.push_front(value);
        }
        best_push = best_push.min(start.elapsed());

        // Pop every value back and check the order, so a broken list cannot post
        // a fast time.
        let mut expected = elements as u64;
        while let Some(value) = list.pop_front() {
            expected -= 1;
            assert_eq!(value, expected, "{} lost LIFO order", L::variant());
        }
        assert_eq!(expected, 0);
        black_box(expected);

        // Rebuild, then time the drop of a full list. This is where the
        // recursive variants overflow the stack.
        for value in 0..elements as u64 {
            list.push_front(value);
        }
        let start = Instant::now();
        drop(list);
        best_drop = best_drop.min(start.elapsed());
    }

    println!(
        "  {:<10} {:>12} {best_push:>13.2?} {best_drop:>13.2?}",
        L::variant(),
        with_thousands(elements as u64)
    );
}

The whole file is listing 13.16. Chapter 13 adds the cache benchmarks to it, and shows it complete there.

run_list::<L: SinglyList<u64>> is generic over the list type L. The compiler generates a separate copy of the function for each list type. So each list is measured with its own code.

The function follows three rules that apply to any small benchmark:

1. Warm up first. The first time a program allocates a lot of memory, the operating system has to supply fresh pages, which is slow. A warm-up pass pays that cost before timing starts.
2. Run several times and keep the fastest. Other programs can slow a run down but never speed it up. So the fastest run is the closest to the true cost.
3. Check the result before trusting the time. Every run pops all the values and checks their order. A broken list cannot report a fast time.

std::hint::black_box(expected) tells the compiler to treat the value as used, so it cannot delete the loop that computed it.

These results come from a release build on an 8-core aarch64 development board:

  variant        elements          push          drop
  ----------------------------------------------------
  box             200,000        2.40ms        3.23ms
  enum            200,000        3.42ms        3.20ms
  box+drop        200,000        2.32ms        2.91ms
  enum+drop       200,000        3.62ms        2.52ms

  box+drop      5,000,000       58.11ms       72.32ms
  enum+drop     5,000,000       90.98ms       67.51ms

Read the table this way:

• A push costs about 12 nanoseconds for the struct node and about 17 for the enum node. Section 9.6.2 gave two differences that could explain the gap. The benchmark does not measure them separately.
• box and box+drop share the same push code, and their push times agree, 2.40 against 2.32 ms. That agreement is a sign the measurement is stable.
• The loop drop is not much faster than the recursive one. Its purpose is to remove the size limit, not to save time.

You can reproduce the crash and the fix:

cargo run --release --bin benchmark list box 260000   # completes
cargo run --release --bin benchmark list box 270000   # crashes
cargo run --release --bin list_drop                   # five million nodes, no crash

9.9 A doubly linked list

In a doubly linked list, each node points to the next node and also back to the previous one. That lets you add and remove at both ends in O(1), and walk the list in either direction.

In Rust this creates an ownership problem. Every node in the middle is pointed to twice: by the previous node’s next and by the following node’s prev. A Box has exactly one owner, so it cannot express this.

The solution uses the three types from chapter 8. Nodes live in Rc<RefCell<Node>>, so they can have more than one handle and still be changed. The forward links, next, are strong Rc handles, so the list owns its nodes from front to back. The backward links, prev, are Weak handles, so they do not create reference cycles (figure 9.6).

9.9.1 The types

A node of the doubly linked list has a value and two links. The link forward owns the next node; the link back is weak, so the two directions do not keep each other alive.

Listing 9.14 Type names, the node, and the list (lines 1 to 25). src/bin/ll.rs

// ============================================================================
// Type aliases for clarity.
// ============================================================================
use std::cell::{Ref, RefCell}; // Ref is needed for peek return types
use std::rc::{Rc, Weak};

type NodeRef<T> = Rc<RefCell<Node<T>>>;
type WeakNodeRef<T> = Weak<RefCell<Node<T>>>;
type OptNodeRef<T> = Option<NodeRef<T>>;
type OptWeakNodeRef<T> = Option<WeakNodeRef<T>>;

// ============================================================================
// Node and LinkedList definitions.
// ============================================================================
struct Node<T> {
    data: T,
    next: OptNodeRef<T>,
    prev: OptWeakNodeRef<T>,
}

pub struct LinkedList<T> {
    head: OptNodeRef<T>,
    tail: OptNodeRef<T>,
    len: usize,
}

The full type of a link is Option<Rc<RefCell<Node<T>>>>. It appears in almost every function, so the file names it once, OptNodeRef<T>, with a type alias. The list keeps a head, a tail, and its length.

9.9.2 Adding at either end

A new node at the front must point forward to the old head, and the old head must point back to it. The back of the list works the same way, mirrored.

Listing 9.15 new, len, and push_front (lines 28 to 69).

impl<T> LinkedList<T> {
    /// Creates an empty list.
    pub fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
            len: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    // --------------------------------------------------------------------
    // push_front
    // --------------------------------------------------------------------
    pub fn push_front(&mut self, data: T) {
        let new_node = Rc::new(RefCell::new(Node {
            data,
            next: None,
            prev: None,
        }));

        // take() moves the old head out of the Option, leaving None.
        match self.head.take() {
            Some(old_head) => {
                // Link old head back to new node (weakly).
                old_head.borrow_mut().prev = Some(Rc::downgrade(&new_node));
                // Link new node forward to old head.
                new_node.borrow_mut().next = Some(old_head);
            }
            None => {
                // List was empty: new node is also the tail.
                self.tail = Some(new_node.clone());
            }
        }
        self.head = Some(new_node);
        self.len += 1;
    }
    // ...
}

push_front creates the new node, then looks at the old head with self.head.take():

• If there was an old head, its prev becomes a weak link to the new node, made with Rc::downgrade. The new node’s next becomes the old head.
• If there was no old head, the list was empty, so the new node is also the tail. new_node.clone() makes a second strong handle for tail.

Finally the new node becomes the head, and the length grows by one. borrow_mut() is the RefCell method from section 8.4. Each call is released at the end of its statement, so no two borrows of the same node overlap.

Listing 9.16 push_back (lines 71 to 93).

impl<T> LinkedList<T> {
    // ...
    // --------------------------------------------------------------------
    // push_back
    // --------------------------------------------------------------------
    pub fn push_back(&mut self, data: T) {
        let new_node = Rc::new(RefCell::new(Node {
            data,
            next: None,
            // self.tail.as_ref() gives Option<&NodeRef<T>>,
            // map(Rc::downgrade) turns it into Option<WeakNodeRef<T>>.
            prev: self.tail.as_ref().map(Rc::downgrade),
        }));

        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
            }
            None => {
                self.head = Some(new_node.clone());
            }
        }
        self.tail = Some(new_node);
        self.len += 1;
    }
    // ...
}

push_back mirrors it at the other end. The new node’s prev is set as it is created: self.tail.as_ref().map(Rc::downgrade). as_ref() turns Option<Rc<...>> into Option<&Rc<...>>, so the tail is looked at without being moved. map(Rc::downgrade) turns that reference into a weak link.

9.9.3 Removing from either end

Removing the front node means unlinking it from its neighbor and moving its value out to the caller.

Listing 9.17 pop_front (lines 95 to 125).

impl<T> LinkedList<T> {
    // ...
    // --------------------------------------------------------------------
    // pop_front
    // --------------------------------------------------------------------
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            // Take ownership of the next node (if any).
            let next = old_head.borrow_mut().next.take();

            match next {
                Some(next_node) => {
                    // Disconnect the new head's prev pointer.
                    next_node.borrow_mut().prev = None;
                    self.head = Some(next_node);
                }
                None => {
                    self.tail = None; // list becomes empty
                }
            }

            self.len -= 1;

            // Safely extract the data. At this point, old_head is the only
            // strong reference (because we removed it from the list and the
            // new head's prev doesn't point to it).
            let node = Rc::try_unwrap(old_head)
                .ok()
                .unwrap()
                .into_inner();
            node.data
        })
    }
    // ...
}

pop_front must return the value by ownership, not a reference. To move the value out, the node itself must be moved out of its Rc, and Rc::try_unwrap does that. It succeeds only if the handle is the last strong one. So the method first removes every other strong link to the node:

1. self.head.take() removes the list’s link to it.
2. The next node’s prev is set to None. That link was weak, so it did not count anyway.
3. If there was no next node, the list is now empty, so self.tail is cleared, removing the tail’s link.

Now Rc::try_unwrap(old_head) succeeds, and .into_inner() moves the Node out of its RefCell.

The call is written .ok().unwrap() rather than .unwrap(). Result::unwrap needs to print the error if it fails, which requires the error type to implement Debug. Here the error type is the Rc itself, and Node does not implement Debug, so .unwrap() would not compile. .ok() turns the Result into an Option, whose unwrap needs no Debug.

Animation 9.7 builds the list of figure 9.6 and pops its front. The badge on each node is its strong count. The last part makes prev strong, to show the leak that Weak prevents.

Listing 9.18 pop_back (lines 127 to 157).

impl<T> LinkedList<T> {
    // ...
    // --------------------------------------------------------------------
    // pop_back
    // --------------------------------------------------------------------
    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            // Get the previous node (upgrade the weak reference).
            let prev = old_tail
                .borrow_mut()
                .prev
                .take()
                .and_then(|w| w.upgrade());

            match prev {
                Some(prev_node) => {
                    prev_node.borrow_mut().next = None;
                    self.tail = Some(prev_node);
                }
                None => {
                    self.head = None; // list becomes empty
                }
            }

            self.len -= 1;

            let node = Rc::try_unwrap(old_tail)
                .ok()
                .unwrap()
                .into_inner();
            node.data
        })
    }
    // ...
}

pop_back mirrors pop_front. It follows the weak prev link with upgrade(), which returns None if the previous node is gone, then clears that node’s next.

Animation 9.8 runs pop_back on 10, 30, 40. Then it pops down to one node, and pops once more from the empty list.

9.9.4 Looking without removing

Looking at the front value must not move it out of the list. The caller gets a borrow of the value instead.

Listing 9.19 peek_front and peek_back (lines 159 to 180).

impl<T> LinkedList<T> {
    // ...
    // --------------------------------------------------------------------
    // peek_front: returns a guarded reference to the front data.
    // The returned Ref<'_, T> holds the borrow of the RefCell until it goes
    // out of scope, ensuring the reference stays valid.
    // --------------------------------------------------------------------
    pub fn peek_front(&self) -> Option<Ref<'_, T>> {
        // self.head.as_ref() -> Option<&NodeRef<T>>
        self.head.as_ref().map(|node| {
            // node.borrow() returns Ref<'_, Node<T>>.
            // Ref::map projects that to a Ref<'_, T> pointing to the data field.
            Ref::map(node.borrow(), |n| &n.data)
        })
    }

    // --------------------------------------------------------------------
    // peek_back: similar to peek_front.
    // --------------------------------------------------------------------
    pub fn peek_back(&self) -> Option<Ref<'_, T>> {
        self.tail
            .as_ref()
            .map(|node| Ref::map(node.borrow(), |n| &n.data))
    }
}

peek_front returns Option<Ref<'_, T>>, not Option<&T>. The value is inside a RefCell, and a reference to it is only safe while the cell’s borrow is active. A Ref is the guard that keeps the borrow active, as section 8.4 showed. Ref::map narrows a guard for the whole node into a guard for its data field. The caller reads the value with *, as main does.

9.9.5 Running it

The complete program, with its tests, is listing 9.28 at the end of the chapter. Running it:

$ cargo run --bin ll
Length: 4
Front: 20
Back: 40
Pop front: Some(20)
Pop back:  Some(40)
Popped: 10
Popped: 30
Empty? true

The test alternating_push_pop_keeps_invariants pushes 100 values at each end, then pops from both ends and checks every value. The comment block at the end of the file lists each standard-library method the file uses, with a one-line description.

This list costs more than the singly linked list. Each node needs a heap block, two counts, and a borrow flag, and every access is checked. It also keeps the recursive drop from section 9.7, because dropping the head drops the next Rc, which drops the next node. Chapter 13 avoids both costs for an LRU cache by storing its nodes in a Vec and linking them by index.

9.10 The complete files

Each file below is shown whole, in the order the chapter used it.

Listing 9.20 The node, the helpers, reverse_list, and remove_all, with tests. src/problems/linked_list.rs

//! Reverse a singly linked list, and remove nodes from it.
//!
//! Uses `Option<Box<ListNode>>` and a `while let` loop to move pointers in a
//! borrow-safe way. Removal walks a cursor: a mutable borrow of one link.

#[derive(Debug, PartialEq, Eq)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    pub fn from_slice(values: &[i32]) -> Option<Box<ListNode>> {
        let mut head = None;
        for &value in values.iter().rev() {
            head = Some(Box::new(ListNode {
                val: value,
                next: head,
            }));
        }
        head
    }

    pub fn to_vec(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut current = head;
        while let Some(node) = current {
            result.push(node.val);
            current = node.next;
        }
        result
    }
}

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut previous = None;
    let mut current = head;

    while let Some(mut node) = current {
        current = node.next.take();
        node.next = previous;
        previous = Some(node);
    }

    previous
}

/// Remove every node whose value is `target`, in one pass.
///
/// `cursor` is a mutable borrow of a link: first `head`, then the `next` of
/// each node that stays. A matching node is unlinked by moving its `next` into
/// the link that pointed at it. The cursor does not move after a removal,
/// because the link it holds now points at a node not yet checked.
pub fn remove_all(mut head: Option<Box<ListNode>>, target: i32) -> Option<Box<ListNode>> {
    let mut cursor = &mut head;
    while cursor.is_some() {
        let node = cursor
            .as_mut()
            .expect("checked by is_some");
        if node.val == target {
            let next = node.next.take();
            *cursor = next;
        } else {
            cursor = &mut cursor
                .as_mut()
                .expect("checked by is_some")
                .next;
        }
    }
    head
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn reverses_list() {
        let head = ListNode::from_slice(&[1, 2, 3, 4]);
        assert_eq!(ListNode::to_vec(reverse_list(head)), vec![4, 3, 2, 1]);
    }

    #[test]
    fn removes_head_middle_and_consecutive_matches() {
        let head = ListNode::from_slice(&[2, 1, 2, 2, 3, 2]);
        assert_eq!(ListNode::to_vec(remove_all(head, 2)), vec![1, 3]);
    }

    #[test]
    fn remove_all_edge_cases() {
        let absent = ListNode::from_slice(&[1, 3]);
        assert_eq!(ListNode::to_vec(remove_all(absent, 2)), vec![1, 3]);
        let every = ListNode::from_slice(&[7, 7, 7]);
        assert_eq!(remove_all(every, 7), None);
        assert_eq!(remove_all(None, 7), None);
    }

    #[test]
    fn handles_empty_and_single() {
        assert_eq!(reverse_list(None), None);
        assert_eq!(
            ListNode::to_vec(reverse_list(ListNode::from_slice(&[42]))),
            vec![42]
        );
    }
}

Listing 9.21 The enum list and its main. src/bin/singly_linked_list.rs

// Singly linked list using an algebraic data type.
//
//    List<T> = Empty
//            | Node { value: T, next: Link<T> }
//
// `Empty` is the end of the list.

type Link<T> = Box<List<T>>;

pub enum List<T> {
    Empty,
    Node { value: T, next: Link<T> },
}

impl<T> List<T> {
    pub fn new() -> Self {
        List::Empty
    }

    pub fn is_empty(&self) -> bool {
        matches!(self, List::Empty)
    }

    pub fn len(&self) -> usize {
        match self {
            List::Empty => 0,
            List::Node { next, .. } => 1 + next.len(),
        }
    }

    /// O(1)
    pub fn push_front(&mut self, value: T) {
        let old = std::mem::replace(self, List::Empty);
        *self = List::Node {
            value,
            next: Link::new(old),
        };
    }

    /// O(1)
    pub fn pop_front(&mut self) -> Option<T> {
        match std::mem::replace(self, List::Empty) {
            List::Empty => None,
            List::Node { value, next } => {
                *self = *next;
                Some(value)
            }
        }
    }
}

fn main() {
    let mut list = List::new();
    list.push_front(2);
    list.push_front(1);
    list.push_front(0);

    assert_eq!(list.len(), 3);
    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.pop_front(), Some(2));
    println!("ok");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn push_pop_works() {
        let mut list = List::new();
        list.push_front(1);
        list.push_front(2);
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
    }

    #[test]
    fn len_works() {
        let mut list = List::new();
        assert_eq!(list.len(), 0);
        list.push_front(1);
        list.push_front(2);
        assert_eq!(list.len(), 2);
    }
}

Listing 9.22 The Option<Box<Node>> list. benchmarking_examples/lists/boxed.rs

//! `Option<Box<Node<T>>>`: one heap allocation per node.
//!
//! Pushing takes the old head and boxes it inside the new node. Freeing the head
//! frees its `next`, which frees its `next`, so the drop recurses once per
//! element and overflows the stack on a long list.

use super::SinglyList;

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> SinglyList<T> for LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn push_front(&mut self, value: T) {
        self.head = Some(Box::new(Node {
            value,
            // .take() leaves None in its place and extracts the old head
            next: self.head.take(),
        }));
    }

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            // Point the list head to the next node in line
            self.head = node.next;
            // Return the unboxed value
            node.value
        })
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    fn variant() -> &'static str {
        "box"
    }
}

Listing 9.23 The enum list behind the trait. benchmarking_examples/lists/enum_node.rs

//! `enum ListNode<T> { Empty, Next(T, Box<ListNode<T>>) }`.
//!
//! Same shape as the boxed variant, written with an enum instead of an
//! `Option`. The enum cannot contain itself by value, so the recursive arm holds
//! a `Box`. The drop is recursive for the same reason.

use super::SinglyList;

enum ListNode<T> {
    Empty,
    Next(T, Box<ListNode<T>>),
}

pub struct LinkedList<T> {
    head: ListNode<T>,
}

impl<T> SinglyList<T> for LinkedList<T> {
    fn new() -> Self {
        Self {
            head: ListNode::Empty,
        }
    }

    fn push_front(&mut self, value: T) {
        // Extract the old head and leave Empty in its place
        let old_head = std::mem::replace(&mut self.head, ListNode::Empty);

        // Wrap the old head inside a Box behind the new value
        self.head = ListNode::Next(value, Box::new(old_head));
    }

    fn pop_front(&mut self) -> Option<T> {
        let old_head = std::mem::replace(&mut self.head, ListNode::Empty);

        match old_head {
            ListNode::Empty => None,
            ListNode::Next(value, next_node) => {
                // Point the list head to the next node in the sequence
                self.head = *next_node;
                Some(value)
            }
        }
    }

    fn is_empty(&self) -> bool {
        matches!(self.head, ListNode::Empty)
    }

    fn variant() -> &'static str {
        "enum"
    }
}

Listing 9.24 The demo of the boxed list. benchmarking_examples/list_box.rs

//! Demo of the `Option<Box<Node<T>>>` list in `lists::boxed`.
//!
//! Run with: cargo run --bin list_box

use systems_lab::lists::{SinglyList, boxed::LinkedList};

fn main() {
    let mut list = LinkedList::new();

    list.push_front(10);
    list.push_front(20);
    list.push_front(30);

    assert_eq!(list.pop_front(), Some(30));
    assert_eq!(list.pop_front(), Some(20));
    assert_eq!(list.pop_front(), Some(10));
    assert_eq!(list.pop_front(), None);
    assert!(list.is_empty());

    println!("All tests passed successfully!");
}

Listing 9.25 The demo of the enum list. benchmarking_examples/list_enum.rs

//! Demo of the `enum ListNode<T>` list in `lists::enum_node`.
//!
//! Run with: cargo run --bin list_enum

use systems_lab::lists::{SinglyList, enum_node::LinkedList};

fn main() {
    let mut list = LinkedList::new();
    list.push_front(42);
    list.push_front(100);

    assert_eq!(list.pop_front(), Some(100));
    assert_eq!(list.pop_front(), Some(42));
    assert_eq!(list.pop_front(), None);
    assert!(list.is_empty());
}

Listing 9.26 The boxed list with its own Drop. benchmarking_examples/lists/boxed_drop.rs

//! `Option<Box<Node<T>>>` with an iterative `Drop`.
//!
//! Push and pop are identical to [`boxed`](super::boxed); only freeing changes.
//! Dropping a node would otherwise drop its `next` and recurse once per element,
//! so the list is unlinked in a loop before any node is freed.

use super::SinglyList;

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> SinglyList<T> for LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn push_front(&mut self, value: T) {
        self.head = Some(Box::new(Node {
            value,
            next: self.head.take(),
        }));
    }

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    fn variant() -> &'static str {
        "box+drop"
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        // Walk the chain and unlink each node before it is freed, so no node's
        // drop has to carry the rest of the list on the stack.
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

Listing 9.27 The enum list with its own Drop. benchmarking_examples/lists/enum_drop.rs

//! `enum ListNode<T>` with an iterative `Drop`.
//!
//! Push and pop are identical to [`enum_node`](super::enum_node); only freeing
//! changes. The recursive arm holds a `Box`, so the default drop walks the chain
//! on the stack. This one replaces the head with `Empty`, then takes the box out
//! of each node in turn.

use super::SinglyList;

enum ListNode<T> {
    Empty,
    Next(T, Box<ListNode<T>>),
}

pub struct LinkedList<T> {
    head: ListNode<T>,
}

impl<T> SinglyList<T> for LinkedList<T> {
    fn new() -> Self {
        Self {
            head: ListNode::Empty,
        }
    }

    fn push_front(&mut self, value: T) {
        let old_head = std::mem::replace(&mut self.head, ListNode::Empty);
        self.head = ListNode::Next(value, Box::new(old_head));
    }

    fn pop_front(&mut self) -> Option<T> {
        let old_head = std::mem::replace(&mut self.head, ListNode::Empty);

        match old_head {
            ListNode::Empty => None,
            ListNode::Next(value, next_node) => {
                self.head = *next_node;
                Some(value)
            }
        }
    }

    fn is_empty(&self) -> bool {
        matches!(self.head, ListNode::Empty)
    }

    fn variant() -> &'static str {
        "enum+drop"
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        // Take the chain out of the list first, then step it forward one node at
        // a time. Each node has already lost its `next` by the time it is freed,
        // so the drop stays on the heap.
        let mut current = std::mem::replace(&mut self.head, ListNode::Empty);
        while let ListNode::Next(_, next) = current {
            current = *next;
        }
    }
}

Listing 9.28 The doubly linked list, with its tests. src/bin/ll.rs

// ============================================================================
// Type aliases for clarity.
// ============================================================================
use std::cell::{Ref, RefCell}; // Ref is needed for peek return types
use std::rc::{Rc, Weak};

type NodeRef<T> = Rc<RefCell<Node<T>>>;
type WeakNodeRef<T> = Weak<RefCell<Node<T>>>;
type OptNodeRef<T> = Option<NodeRef<T>>;
type OptWeakNodeRef<T> = Option<WeakNodeRef<T>>;

// ============================================================================
// Node and LinkedList definitions.
// ============================================================================
struct Node<T> {
    data: T,
    next: OptNodeRef<T>,
    prev: OptWeakNodeRef<T>,
}

pub struct LinkedList<T> {
    head: OptNodeRef<T>,
    tail: OptNodeRef<T>,
    len: usize,
}

impl<T> LinkedList<T> {
    /// Creates an empty list.
    pub fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
            len: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    // --------------------------------------------------------------------
    // push_front
    // --------------------------------------------------------------------
    pub fn push_front(&mut self, data: T) {
        let new_node = Rc::new(RefCell::new(Node {
            data,
            next: None,
            prev: None,
        }));

        // take() moves the old head out of the Option, leaving None.
        match self.head.take() {
            Some(old_head) => {
                // Link old head back to new node (weakly).
                old_head.borrow_mut().prev = Some(Rc::downgrade(&new_node));
                // Link new node forward to old head.
                new_node.borrow_mut().next = Some(old_head);
            }
            None => {
                // List was empty: new node is also the tail.
                self.tail = Some(new_node.clone());
            }
        }
        self.head = Some(new_node);
        self.len += 1;
    }

    // --------------------------------------------------------------------
    // push_back
    // --------------------------------------------------------------------
    pub fn push_back(&mut self, data: T) {
        let new_node = Rc::new(RefCell::new(Node {
            data,
            next: None,
            // self.tail.as_ref() gives Option<&NodeRef<T>>,
            // map(Rc::downgrade) turns it into Option<WeakNodeRef<T>>.
            prev: self.tail.as_ref().map(Rc::downgrade),
        }));

        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
            }
            None => {
                self.head = Some(new_node.clone());
            }
        }
        self.tail = Some(new_node);
        self.len += 1;
    }

    // --------------------------------------------------------------------
    // pop_front
    // --------------------------------------------------------------------
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            // Take ownership of the next node (if any).
            let next = old_head.borrow_mut().next.take();

            match next {
                Some(next_node) => {
                    // Disconnect the new head's prev pointer.
                    next_node.borrow_mut().prev = None;
                    self.head = Some(next_node);
                }
                None => {
                    self.tail = None; // list becomes empty
                }
            }

            self.len -= 1;

            // Safely extract the data. At this point, old_head is the only
            // strong reference (because we removed it from the list and the
            // new head's prev doesn't point to it).
            let node = Rc::try_unwrap(old_head)
                .ok()
                .unwrap()
                .into_inner();
            node.data
        })
    }

    // --------------------------------------------------------------------
    // pop_back
    // --------------------------------------------------------------------
    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            // Get the previous node (upgrade the weak reference).
            let prev = old_tail
                .borrow_mut()
                .prev
                .take()
                .and_then(|w| w.upgrade());

            match prev {
                Some(prev_node) => {
                    prev_node.borrow_mut().next = None;
                    self.tail = Some(prev_node);
                }
                None => {
                    self.head = None; // list becomes empty
                }
            }

            self.len -= 1;

            let node = Rc::try_unwrap(old_tail)
                .ok()
                .unwrap()
                .into_inner();
            node.data
        })
    }

    // --------------------------------------------------------------------
    // peek_front: returns a guarded reference to the front data.
    // The returned Ref<'_, T> holds the borrow of the RefCell until it goes
    // out of scope, ensuring the reference stays valid.
    // --------------------------------------------------------------------
    pub fn peek_front(&self) -> Option<Ref<'_, T>> {
        // self.head.as_ref() -> Option<&NodeRef<T>>
        self.head.as_ref().map(|node| {
            // node.borrow() returns Ref<'_, Node<T>>.
            // Ref::map projects that to a Ref<'_, T> pointing to the data field.
            Ref::map(node.borrow(), |n| &n.data)
        })
    }

    // --------------------------------------------------------------------
    // peek_back: similar to peek_front.
    // --------------------------------------------------------------------
    pub fn peek_back(&self) -> Option<Ref<'_, T>> {
        self.tail
            .as_ref()
            .map(|node| Ref::map(node.borrow(), |n| &n.data))
    }
}

// ============================================================================
// Demonstration with main().
// ============================================================================
fn main() {
    let mut list = LinkedList::new();

    list.push_front(10);
    list.push_front(20);
    list.push_back(30);
    list.push_back(40);

    println!("Length: {}", list.len());

    // Peek returns a Ref; we can dereference it with *.
    if let Some(front) = list.peek_front() {
        println!("Front: {}", *front);
    }
    if let Some(back) = list.peek_back() {
        println!("Back: {}", *back);
    }

    println!("Pop front: {:?}", list.pop_front()); // 20
    println!("Pop back:  {:?}", list.pop_back()); // 40

    // Drain the list.
    while let Some(val) = list.pop_front() {
        println!("Popped: {}", val);
    }
    println!("Empty? {}", list.is_empty());
}

// ============================================================================
// Tests (cargo test --bin ll)
// ============================================================================
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn new_list_is_empty() {
        let list: LinkedList<i32> = LinkedList::new();
        assert!(list.is_empty());
        assert_eq!(list.len(), 0);
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
    }

    #[test]
    fn push_front_back_and_len() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_front(0);

        assert_eq!(list.len(), 3);
        assert_eq!(*list.peek_front().unwrap(), 0);
        assert_eq!(*list.peek_back().unwrap(), 2);
    }

    #[test]
    fn pop_front_and_back_work_in_order() {
        let mut list = LinkedList::new();
        list.push_back(10);
        list.push_back(20);
        list.push_back(30);

        assert_eq!(list.pop_front(), Some(10));
        assert_eq!(list.pop_back(), Some(30));
        assert_eq!(list.pop_front(), Some(20));
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.pop_back(), None);
        assert!(list.is_empty());
    }

    #[test]
    fn popping_last_item_empties_the_list() {
        let mut list = LinkedList::new();
        list.push_back(42);
        assert_eq!(list.peek_front().map(|x| *x), Some(42));
        assert_eq!(list.pop_back(), Some(42));
        assert!(list.is_empty());
    }

    #[test]
    fn alternating_push_pop_keeps_invariants() {
        let mut list = LinkedList::new();
        for i in 0..100 {
            list.push_back(i);
            list.push_front(-i);
        }
        assert_eq!(list.len(), 200);
        for i in (0..100).rev() {
            assert_eq!(list.pop_front(), Some(-i));
            assert_eq!(list.pop_back(), Some(i));
        }
        assert!(list.is_empty());
    }
}

// ============================================================================
// Explanation of key methods used:
//
// - Rc::new / RefCell::new        : create a reference-counted, mutable cell.
// - borrow() / borrow_mut()       : borrow the RefCell's contents (immutably/mutably).
// - Rc::downgrade()               : turn an Rc into a Weak (no ownership).
// - Weak::upgrade()               : attempt to get an Rc from a Weak (returns Option).
// - Option::take()                : take the value out of an Option, leaving None.
// - Option::as_ref()              : convert Option<T> to Option<&T> without moving.
// - Option::map()                 : apply a function to the inner value if Some.
// - Option::and_then()            : like map but returns an Option (for chaining).
// - Rc::try_unwrap()              : move the value out of the Rc if it's the only strong ref.
// - Ref::map()                    : project a Ref to a subfield, keeping the borrow alive.
// ============================================================================

Chapter 10 uses the singly linked list from section 9.3 to merge many sorted lists into one, and compares eleven ways of doing it.

Exercises

1. Write len for the enum list of section 9.5 with a loop instead of recursion.
2. Implement Iterator for the struct list of section 9.3, with an iter() method that yields &i32.
3. Implement Drop for the doubly linked list, and test it with one million nodes.
4. Build a doubly linked list whose nodes live in a Vec, with Option<usize> indexes as links. Compare its push and pop times with the Rc version.