Rust: How to implement linked list?

Question

I thought I'd dive into Rust by imeplementing some very simple structure & algorithms, I started with a linked list. Turns out it's not actually that simple. This is my code so far:

enum List<T> 
{
    Node(T, ~List<T>),
    Nil
}

impl<T> List<T>
{
    fn new(vector: &[T]) -> List<T> { Nil }

    fn add(&mut self, item: T)
    {
        let tail = self;
        loop
        {
            match *tail
            {
                Node(_, ~ref next) => tail = next,
                Nil => break
            }
        }
        *tail = Node(item, ~Nil);
    }
}

This won't compile because next cannot be assigned to tail in the match statement due to incompatible mutability. I know this can easily be done using garbage collected pointers, but that kind of defeats the educational purpose of the exercise: I'd like to know how to do this without Gc or Rc pointers.

Answer 1

It looks like you're trying to walk your own list to find the final element, but you don't actually have a loop. Assuming you fix that, your issue with mutability can be fixed by using ref mut instead of ref.

To try it myself I used a recursive implementation of add() and this works:

fn add(&mut self, item: T) {
    match *self {
        Node(_, ref mut next) => next.add(item),
        Nil => *self = Node(item, ~Nil)
    }
}

Offhand I'm not sure how to implement this using an iterative approach, due to issues with mutable borrowing.