It is possible to implement a Cons list in Rust wthout using a smart pointer

Question

I have implemented a Cons list using a Box pointer to the next element in the list as follows.

#[derive(Debug, PartialEq, Eq)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

impl<T: Copy> List<T> {
    pub fn from_slice(v: &[T]) -> List<T> {
        let mut inner = List::Nil;
        for &next_elem in v.iter().rev() {
            inner = List::Cons(next_elem, Box::new(inner));
        }
        inner
    }
}

struct ListIter<'a, T>(&'a List<T>);
impl<'a, T> Iterator for ListIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            List::Cons(inner, next) => {
                self.0 = next;
                Some(inner)
            },
            List::Nil => None
        }
    }
}

This implementation works the way I want and has all the features I want. But is it possible to achieve the same functionality using a plain shared reference (&List) to represent a pointer to the next node in the List? For example such that List might defined as

#[derive(Debug, PartialEq, Eq)]
enum List<'a, T> {
    Cons(T, &'a List<'a, T>),
    Nil,
}

And if so, what are the costs and benefits of using a plain shared reference as opposed to a Box?

I tried my hand at it but I couldn't find a straightforward way to implement from_slice for List<'a, T> without violating the borrowing rules.

Answer 1

If I make a list List::Cons(1, &List::Cons(2, &List::Nil)), I have a reference to that inner list &List::Cons(2, &List::Nil), right? That reference is to a List on the stack.

That is to say, List::Cons(1, &List::Cons(2, &List::Nil)) is extremely similar to

let x = List::Nil;
let y = List::Cons(2, &x);
let z = List::Cons(1, &y);

When I return from the function, no one owns the resulting stack values -- x and y are destroyed. Thus you can't return z, it's referencing data that will no longer exist.

Answer 2

There are two ways to use references: on stack or with arenas.

On the stack means something like:

let nil = List::Nil;
let cons1 = List::Cons(1, &nil);
let cons2 = List::Cons(0, &cons1);

The advantage is that it involves only stack allocations and therefore should be blazing fast; the disadvantage is that you cannot return the list from the function, and that implies creating from_slice() is impossible.

Another way is to use arenas, a memory allocator without deallocation. For example, using the bumpalo crate:

use bumpalo::Bump;

#[derive(Debug, PartialEq, Eq)]
enum List<'a, T> {
    Cons(T, &'a List<'a, T>),
    Nil,
}

impl<'a, T: Copy> List<'a, T> {
    pub fn from_slice(v: &[T], arena: &'a Bump) -> List<'a, T> {
        let mut inner = List::Nil;
        for &next_elem in v.iter().rev() {
            inner = List::Cons(next_elem, arena.alloc(inner));
        }
        inner
    }
}

struct ListIter<'a, T>(&'a List<'a, T>);
impl<'a, T> Iterator for ListIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            List::Cons(inner, next) => {
                self.0 = next;
                Some(inner)
            },
            List::Nil => None
        }
    }
}

The advantages is that this is very fast (as arena allocation is just some pointer manipulation) and this allows sharing the tail of similar lists; the disadvantages is that this does not allow you to free only some elements, so don't use it if you are not going to free all (or at least most) elements at once, and that it requires a reference to the arena to exist (you cannot store the arena alongside the list because this creates a self-referential struct).