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

Learn Rust With Entirely Too Many Linked Lists is strongly recommended reading for anyone writing data structures in Rust, or using Rust at all, really. — trent
– trent, Commented Jul 6, 2019 at 11:02
Cannot move out of borrowed content when unwrapping; Why is it discouraged to accept a reference to a String (&String), Vec (&Vec), or Box (&Box) as a function argument?; Option::is_none; What would be a better way to implement .pop() in my single linked list in Rust? — Shepmaster
– Shepmaster, Commented Jul 6, 2019 at 12:46
Stack Overflow is not suited for general feedback on your code, but rather for specific problems. You are encouraged to post to Code Review if you want broad feedback on your working code. — Shepmaster
– Shepmaster, Commented Jul 6, 2019 at 12:53
@Shepmaster: My question was about the bug I got. I just wanted people to not hesitate to correct anything else. Thank you for the links also. Since I don't understand well my issues, it's hard to look for related ones. I'll definitely check these out! — Nakor
– Nakor, Commented Jul 6, 2019 at 19:37

Shepmaster · Accepted Answer · 2019-07-06 12:48:21Z

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.

edited Jul 6, 2019 at 12:48

Shepmaster

439k116 gold badges1.3k silver badges1.5k bronze badges

answered Jul 6, 2019 at 6:11

Axel Montini

4407 silver badges14 bronze badges

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

2 Comments

Nakor Over a year ago

Oh you're totally right, I should put it in the front... But just for the sake of knowing, let's say I wanted to always put it at the end, would my code be fixable? Doing let before_last = &mut match &mut self.head does not work, so I'm not sure how to make before_last a mutable reference

Axel Montini Over a year ago

@Naktor You would need to have the function get_before_last to take mutable references (&'a mut Box<Node<T>>). The problem is that you would end up with a double mut borrow, which is not allowed in safe rust. I have yet to see a solution using this approach that doesn't use unsafe.

Collectives™ on Stack Overflow

References in linked list implementation

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related