Is there a difference between a linked list implemented using Box<T> and &'a T?

Question

I'm struggling trying to understand the difference between these two implementations of a linked list. This first version is the one presented in the Rust book using a Box<T>:

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

This is the other implementation I was thinking of:

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}

Is there any important difference between the two, or are they equivalent in this case?

Answer 1

Either of these implementations will technically work but there are some big trade-offs.

A Box allocates on the heap and then owns the data. This is pretty convenient and flexible, compared to managing references.

In order to build a list of the second type, using & references, you need to own the data somewhere. So you need to manage an arbitrary number of nodes and make sure they don't go out of scope. This can be very restrictive. For example, it isn't very easy to make a function that constructs a list and then returns it:

fn make_list<'a>() -> List<'a> {
    let node1 = List::Nil;
    let node2 = List::Cons(1, &node1);
    let node3 = List::Cons(2, &node2);
    node3
    // node1 and node2 go out of scope here...
}

This won't work because it's referencing function-local variables, which go out of scope when the function returns. The version using Box will work because the Box takes ownership of the data.