rust - Adding an append method to a singly linked list

Question

I was looking through the singly linked list example on rustbyexample.com and I noticed the implementation had no append method, so I decided to try and implement it:

fn append(self, elem: u32) -> List {
    let mut node = &self;
    loop { 
        match *node {
            Cons(_, ref tail) => {
                node = tail;
            },
            Nil => {
                node.prepend(elem);
                break;
            },
        }
    }
    return self;
}

The above is one of many different attempts, but I cannot seem to find a way to iterate down to the tail and modify it, then somehow return the head, without upsetting the borrow checker in some way.

I am trying to figure out a solution that doesn't involve copying data or doing additional bookkeeping outside the append method.

Answer 1

As described in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time, you need to transfer ownership of the mutable reference when performing iteration. This is needed to ensure you never have two mutable references to the same thing.

We use similar code as that Q&A to get a mutable reference to the last item (back) which will always be the Nil variant. We then call it and set that Nil item to a Cons. We wrap all that with a by-value function because that's what the API wants.

No extra allocation, no risk of running out of stack frames.

use List::*;

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

impl List {
    fn back(&mut self) -> &mut List {
        let mut node = self;

        loop {
            match {node} {
                &mut Cons(_, ref mut next) => node = next,
                other => return other,
            }
        }
    }

    fn append_ref(&mut self, elem: u32) {        
        *self.back() = Cons(elem, Box::new(Nil));
    }

    fn append(mut self, elem: u32) -> Self {
        self.append_ref(elem);
        self
    }
}

fn main() {
    let n = Nil;
    let n = n.append(1);
    println!("{:?}", n);
    let n = n.append(2);
    println!("{:?}", n);
    let n = n.append(3);
    println!("{:?}", n);
}

---

When non-lexical lifetimes are enabled, this function can be more obvious:

fn back(&mut self) -> &mut List {
    let mut node = self;

    while let Cons(_, next) = node {
        node = next;
    }

    node
}