References in linked list implementation

Question

I am trying to do the Simple Linked List Exercism problem, but I am stuck implementing the pop() method. The errors I get are not very clear to me; I'm not quite used to Rust's way of thinking, I guess.

Also, because of the compiler suggestions, I added a bunch of as_ref() that I don't really understand.

I am interested in knowing why my way of doing things doesn't work more than the solution.

pub struct SimpleLinkedList<T> {
    head: Option<Box<Node<T>>>,
}

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T> SimpleLinkedList<T> {
    pub fn new() -> Self {
        unimplemented!()
    }

    pub fn len(&self) -> usize {
        unimplemented!()
    }

    pub fn push(&mut self, _element: T) {
        unimplemented!()
    }

    pub fn pop(&mut self) -> Option<T> {
        // Recursive function to return the before last element of the list
        fn get_before_last<'a, T>(
            prev: &'a Box<Node<T>>,
            current: &'a Box<Node<T>>,
        ) -> &'a Box<Node<T>> {
            match &current.next {
                Some(next_node) => get_before_last(&current, &next_node),
                None => &prev,
            }
        }

        // Check if the head is None
        match &self.head {
            None => return None,
            _ => (),
        };

        let before_last = &mut match &self.head {
            // Beginning of the recursion
            Some(node) => get_before_last(&node, node.next.as_ref().unwrap()),
            None => self.head.as_ref().unwrap(),
        };

        let to_pop = before_last.next.as_ref();
        before_last.next = None;

        Some(to_pop.unwrap().data)
    }
}

I get the following errors:

error[E0594]: cannot assign to `before_last.next` which is behind a `&` reference
  --> src/lib.rs:48:9
   |
48 |         before_last.next = None;
   |         ^^^^^^^^^^^^^^^^ cannot assign

error[E0507]: cannot move out of borrowed content
  --> src/lib.rs:50:14
   |
50 |         Some(to_pop.unwrap().data)
   |              ^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content

Answer 1

In your code, before_last is not mutable. In fact it's a &mut &'a Box<Node>. For this reason you cannot assign anything to the node because it's a mutable reference to an immutable one.

The best suggestion I can give you is to rethink the implementation. Instead of pushing and popping to the end of the chain, you can do so on the front. Create a new boxed node, remove the head and put it in the new node's next field. Then the new node becomes the head.

This way you have a LIFO list and you don't have to traverse the whole list to push & pop, so it's also more efficient. Pushing to the front also reduces the amount of code required.

My solution is available on Exercism.