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.

Lily Ballard · Accepted Answer · 2014-01-16 03:54:40Z

7

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.

answered Jan 16, 2014 at 3:54

Lily Ballard

187k34 gold badges390 silver badges350 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

kralyk Over a year ago

Thanks! Yes, there was a loop, but I was going back and forth between loop and recursion approach and I guess at point some I lost it. Will edit.

Ben · Accepted Answer · 2021-01-07 12:11:53Z

1

Iterative solution, using Box::borrow_mut():

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

impl<T> List<T> {
    fn new() -> List<T> { List::Nil }

    fn add(&mut self, item: T) {
        use std::borrow::BorrowMut;
        
        let mut tail = self;
        while let Self::Node(_, next) = tail {
            tail = next.borrow_mut();
        }
        *tail = List::Node(item, Box::new(List::Nil));
    }
}

Playground link

answered Jan 7, 2021 at 12:11

Ben

3,7234 gold badges21 silver badges46 bronze badges

Collectives™ on Stack Overflow

Rust: How to implement linked list?

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related