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
}

Answer 2

So, it's actually going to be slightly more difficult than you may think; mostly because Box is really missing a destructive take method which would return its content.

---

Easy way: the recursive way, no return.

fn append_rec(&mut self, elem: u32) {
    match *self {
        Cons(_, ref mut tail) => tail.append_rec(elem),
        Nil => *self = Cons(elem, Box::new(Nil)),
    }
}

This is relatively easy, as mentioned.

---

Harder way: the recursive way, with return.

fn append_rec(self, elem: u32) -> List {
    match self {
        Cons(e, tail) => Cons(e, Box::new((*tail).append_rec(elem))),
        Nil => Cons(elem, Box::new(Nil)),
    }
}

Note that this is grossly inefficient. For a list of size N, we are destroying N boxes and allocating N new ones. In place mutation (the first approach), was much better in this regard.

---

Harder way: the iterative way, with no return.

fn append_iter_mut(&mut self, elem: u32) {
    let mut current = self;
    loop {
        match {current} {
            &mut Cons(_, ref mut tail) => current = tail,
            c @ &mut Nil => {
                *c = Cons(elem, Box::new(Nil));
                return;
            },
        }
    }
}

Okay... so iterating (mutably) over a nested data structure is not THAT easy because ownership and borrow-checking will ensure that:

• a mutable reference is never copied, only moved,
• a mutable reference with an outstanding borrow cannot be modified.

This is why here:

• we use {current} to move current into the match,
• we use c @ &mut Nil because we need a to name the match of &mut Nil since current has been moved.

Note that thankfully rustc is smart enough to check the execution path and detect that it's okay to continue looping as long as we take the Cons branch since we reinitialize current in that branch, however it's not okay to continue after taking the Nil branch, which forces us to terminate the loop :)

---

Harder way: the iterative way, with return

fn append_iter(self, elem: u32) -> List {
    let mut stack = List::default();
    {
        let mut current = self;
        while let Cons(elem, tail) = current {
            stack = stack.prepend(elem);
            current = take(tail);
        }
    }

    let mut result = List::new();
    result = result.prepend(elem);

    while let Cons(elem, tail) = stack {
        result = result.prepend(elem);
        stack = take(tail);
    }

    result
}

In the recursive way, we were using the stack to keep the items for us, here we use a stack structure instead.

It's even more inefficient than the recursive way with return was; each node cause two deallocations and two allocations.

---

TL;DR: in-place modifications are generally more efficient, don't be afraid of using them when necessary.

Answer 3

As the len method is implemented recursively, I have done the same for the append implementation:

fn append(self, elem: u32) -> List {
    match self {
        Cons(current_elem, tail_box) => {
            let tail = *tail_box;
            let new_tail = tail.append(elem);

            new_tail.prepend(current_elem)
        }
        Nil => {
            List::new().prepend(elem)
        }
    }
}

One possible iterative solution would be to implement append in terms of prepend and a reverse function, like so (it won't be as performant but should still only be O(N)):

// Reverses the list
fn rev(self) -> List {
    let mut result = List::new();
    let mut current = self;
    while let Cons(elem, tail) = current {
        result = result.prepend(elem);
        current = *tail;
    }

    result
}

fn append(self, elem: u32) -> List {
    self.rev().prepend(elem).rev()
}