Mutable borrow errors while implementing a linked list where new elements are added to the end in Rust

Question

I wanted to implement a linked list from scratch. The basic idea is that new elements are added to the end of the list, requiring the program to cycle to the end to reach the last element to append.

I realise that there is a LinkedList type as part of the standard library but I am trying to implement this for educational purposes.

I also took a look at the Rust tutorial Learn Rust With Entirely Too Many Linked Lists but this didn't really have what I was looking for as it implemented stacks, placing new elements at the start.

The code I have come up with is as follows:

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkList {
    head: Option<Box<Node>>,
}

impl LinkList {
    fn has_head(&self) -> bool {
        self.head.is_none()
    }

    fn insert_node(&mut self, node: Node) {
        if self.has_head() {
            self.head = Some(Box::new(node));
        } else {
            let mut curr = &mut self.head;
            let mut cont = true;

            while cont {
                match curr {
                    Some(ref mut p) => {
                        println!("has value {:?}", p);
                        if p.next.is_none() {
                            cont = false;
                        }
                        else {
                            curr = &mut p.next;
                        }
                    },
                    None => cont = false,
                }
            }

            match curr {
                Some(ref mut p) => {
                    println!("Yay");
                    p.next = Some(Box::new(node));
                },
                None => println!("Something has gone wrong..."),
            }
        }
    }
}

With the main function being:

fn main() {
    let n1 = Node {
        value: 1,
        next: None
    };

    let n2 = Node {
        value: 2,
        next: None
    };

    let n3 = Node {
        value: 3,
        next: None
    };

    let mut l = LinkList { head: None };
    l.insert_node(n1);
    l.insert_node(n2);
    l.insert_node(n3);
    println!("{:?}", l.head);
}

I think I am pretty close but the error I am currently getting is

error[E0503]: cannot use `*curr` because it was mutably borrowed
  --> src/lib.rs:25:21
   |
25 |                     Some(ref mut p) => {
   |                     ^^^^^---------^
   |                     |    |
   |                     |    borrow of `curr.0` occurs here
   |                     use of borrowed `curr.0`
   |                     borrow later used here

error[E0499]: cannot borrow `curr.0` as mutable more than once at a time
  --> src/lib.rs:25:26
   |
25 |                     Some(ref mut p) => {
   |                          ^^^^^^^^^ mutable borrow starts here in previous iteration of loop

error[E0503]: cannot use `*curr` because it was mutably borrowed
  --> src/lib.rs:39:17
   |
25 |                     Some(ref mut p) => {
   |                          --------- borrow of `curr.0` occurs here
...
39 |                 Some(ref mut p) => {
   |                 ^^^^^^^^^^^^^^^
   |                 |
   |                 use of borrowed `curr.0`
   |                 borrow later used here

error[E0499]: cannot borrow `curr.0` as mutable more than once at a time
  --> src/lib.rs:39:22
   |
25 |                     Some(ref mut p) => {
   |                          --------- first mutable borrow occurs here
...
39 |                 Some(ref mut p) => {
   |                      ^^^^^^^^^
   |                      |
   |                      second mutable borrow occurs here
   |                      first borrow later used here

I understand the basics of Rust's ownership rules and can kinda understand why this issue is occurring. How do I work with the ownership rules to achieve what I need?

Answer 1

One very useful idea when you have loops with at least one condition being checked is to see what invariants you're trying to uphold. In Rust, you should make the invariants be expressed in the type of the terms as much as possible. That will allow the type system to work for you and you'll have a much better time.

So let's look at what invariants we have for this function. First, we check if the head is None. If it is, the rest of the function isn't executed, so from then on, we can assume the head is Some. Side note here, it would probably be better to simply return early rather than have the bulk of the function in an else block.

Next, we assign &mut self.head to curr, so we know (at least for now) that curr is Some. In the loop, we first check if curr is Some or None, so this should be the first sign that something's wrong.

Continuing the loop, we check if the next node is None, and if it isn't, we assign it to curr, so the invariant that curr is Some is upheld. We still check it at the start of every loop.

Another invariant is that cont is true until p.next is None, at which point it switches to false and the loop ends. It can also be set to false if curr is None, but since our first invariant is that curr is never None, this can't happen.

My first suggested change would be to get rid of the cont variable and simply break when p.next is None. Then the while loop can just be loop, which continues until there's a break. This actually fixes one problem, which I'll discuss below, but leaves another problem.

My second suggested change is to either make curr be &mut Box<Node> rather than &mut Option<Box<Node>> or simply find a way to do this without maintaining that invariant. The first approach is closer to your code right now, but you may find that the second approach makes things easier. After all, we're just trying to traverse the list until we get something that isn't Some.

The first approach can be done with unwrapping, or, much more idiomatically, by replacing if option.is_none() with a match statement. For example, at the start of the function, we can replace the check by

let mut curr;
if let Some(ref mut head) = self.head {
    curr = head;
} else {
    self.head = Some(Box::new(node));
    return;
}

(note the return statement so that the rest of the function doesn't need to be in a block).

Similarly reworking the inside of the loop and the end of the function lets the function compile. All this comes from changing the type of curr and using if let (or a match statement) instead of using if to check when an option is None or Some. Since now curr isn't an option, we don't need to do any checks on it and instead only check curr.next.

loop cont {
    println!("has value {:?}", curr);
    if let Some(ref mut next_node) = curr.next {
        curr = next_node;
    } else {
        break;
    }
}

println!("Yay");
curr.next = Some(Box::new(node));

---

You may be wondering why the problem occurred in the first place. Basically, curr is a mutable borrow of the whole list after some point. When we match on it and bind ref mut p, p is now a mutable borrow of the same list. That must mean that curr is no longer an active borrow, since otherwise we'd have two mutable borrows of (parts of) the same list.

What saves us is reassigning curr. In most iterations of the loop we have, curr = &mut p.next;, which is a new borrow and will last until the next time we match on curr. However, in the last iteration of the loop, we don't do that. We just set cont to false (or simply break) and end. That means that curr is invalid after the loop ends. So you can't use curr to modify the list at the end.

What you could do is still assign a new mutable reference in the last loop too, but unfortunately the types don't work out very well. We can't get &mut Option<T> out of p, whose type is simply &mut T (where T is Box<Node>). A second variable actually does work. You could have let mut final_node; before the loop and then have final_node = p when p.next is None. To convince the compiler that final_node is initialized in every branch of the code, you'd still need to use break instead of cont and use unreachable!() in the case where curr is None (it certainly should be unreachable - return would also convince the compiler here).

With my suggestion above using if let, we actually avoid ending curr's borrow on the last iteration. In the Some(ref mut p) case, we reassign curr and otherwise we don't bind p at all so the borrow in curr doesn't need to end.

---

For reference, here's the complete rework with the minimal changes I suggested.

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkList {
    head: Option<Box<Node>>,
}

impl LinkList {
    fn has_head(&self) -> bool {
        self.head.is_none()
    }

    fn insert_node(&mut self, node: Node) {
        let mut curr;
        if let Some(ref mut head) = self.head {
            curr = head;
        } else {
            self.head = Some(Box::new(node));
            return;
        }

        loop {
            println!("has value {:?}", curr);
            if let Some(ref mut next_node) = curr.next {
                curr = next_node;
            } else {
                break;
            }
        }

        println!("Yay");
        curr.next = Some(Box::new(node));
    }
}

(playground)

By letting curr simply be a general option (not necessarily Some) and checking if it's Some or None at the start of the loop, we can eliminate some more code.

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkList {
    head: Option<Box<Node>>,
}

impl LinkList {
    fn insert_node(&mut self, node: Node) {
        let mut curr_opt = &mut self.head;
        while let Some(curr_node) = curr_opt {
            curr_opt = &mut curr_node.next;
        }
        *curr_opt = Some(Box::new(node));
    }
}

(playground)

Answer 2

Here is a recursive solution:

impl Node {
    fn append(&mut self, new_node: Node) {
        match self.next {
            Some(ref mut p) => p.append(new_node),
            None => self.next = Some(Box::new(new_node))
        }
    }
}

struct LinkList {
    head: Option<Box<Node>>,
}

impl LinkList {
    fn has_head(&self) -> bool {
        self.head.is_none()
    }

    fn insert_node(&mut self, node: Node) {
        if self.has_head() {
            self.head = Some(Box::new(node));
        } else {
            self.head.as_mut().unwrap().append(node);
        }
    }
}

Playground

Though note that in a actual queue (first in, first out) which seems like what you are trying to implement, rather than looping through the entire list to add one element, just keep track of the tail as a pointer/reference. I.e. add a element directly onto the tail, and move the tail pointer to the new element