๐ŸŽ“ A1Learner
๐Ÿ”

Rust Linked Lists

A linked list is a chain of links, where each link holds a value and the rest of the list. Its methods use the same impl tools as structs, now working on an enum.

The shape, from the Box lesson

Each Cons holds a number. It also holds the rest of the list in a Box. So the recursive type has a known size. List::new() gives back Nil, the empty list.

enum List {
    Cons(u32, Box<List>),
    Nil,
}

Build by prepending

prepend takes the old list by value. It moves the old list inside a fresh Cons. So each line rebinds the longer list. The last value prepended sits at the front.

let list = List::new();
let list = list.prepend(1);
let list = list.prepend(2);
println!("length = {}", list.len());

Looking methods borrow and recurse

len only looks. So it takes &self and matches on it. Matching on &self binds the tail by reference on its own. The Nil arm is the base case that stops the calls.

fn len(&self) -> u32 {
    match self {
        Cons(_, tail) => 1 + tail.len(),
        Nil => 0,
    }
}

The same walk, as text

stringify follows the same pattern. Print the head. Then let the tail describe itself. Stop when Nil answers with its own name. The closing program below prints 3, 2, 1, Nil this way.

match self {
    Cons(head, tail) => format!("{}, {}", head, tail.stringify()),
    Nil => String::from("Nil"),
}

Example

enum List { Cons(u32, Box<List>), Nil }
use List::{Cons, Nil};
impl List {
    fn new() -> List { Nil }
    fn prepend(self, elem: u32) -> List { Cons(elem, Box::new(self)) }
    fn len(&self) -> u32 {
        match self {
            Cons(_, tail) => 1 + tail.len(),
            Nil => 0,
        }
    }
    fn stringify(&self) -> String {
        match self {
            Cons(head, tail) => format!("{}, {}", head, tail.stringify()),
            Nil => String::from("Nil"),
        }
    }
}
fn main() {
    let mut list = List::new();
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);
    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
}

Key points

  • A list with a million links makes len follow a million calls, and even dropping such a list recurses.
  • For very long lists, a Vec is usually the better tool.
  • A linked list stores each value in a link that also holds the rest of the list.

In this example, List is the recursive enum from the Box lesson, and the impl block adds four methods. new gives back Nil, the empty list. prepend takes the whole list by value. It wraps the list in a Box inside a new Cons. It gives the longer list back. So main reassigns list each time. And 3 ends up at the front. len borrows the list. It counts by recursion. Each Cons adds 1 plus the length of its tail. Nil adds 0. stringify works the same way and builds the text 3, 2, 1, Nil.

Note

Deep recursion has a cost.

Try it Yourself

Edit the code, then press Run.

Running is simulated ยท Rust Playground

Exercise

Why does prepend take self by value instead of &self?