Custom link list pop_back implementation

Question

I'm new to rust and try to understand &mut ref variables and mutability. I started creating a simple link list with pop_back function.

pub fn pop_back(&mut self) -> Option<T> {
        let mut head = &mut self.head;
        while let Some(v) = head {
            if v.next.is_none() {
                break;
            }
            head = &mut v.next;
        }
        head.take().map(|node| node.data)
    }

but can't make it to work. error is cannot borrow *head as mutable more than once at a time. How can I tell rust that I want to only change the reference in my loop not the value? I don't want to add another tail variable to my list so without changing structure how can I make this work?

this is the struct definition

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

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

Mandatory reading: Learn Rust With Entirely Too Many Linked Lists — Aiden4
– Aiden4, Commented Sep 20, 2022 at 17:04
wow really good article. but still doesn't explain this problem. — danics
– danics, Commented Sep 21, 2022 at 8:59

Chayim Friedman · Accepted Answer · 2022-09-20 16:24:48Z

2

This is a known limitation of the borrow checker. The next-gen Polonius will solve this.

In the meantime, the solution (without unsafe) is to repeat the calculation. In your case, this means some unwrap()s:

pub fn pop_back(&mut self) -> Option<T> {
    let mut head = &mut self.head;
    while head.is_some() {
        if head.as_mut().unwrap().next.is_none() {
            break;
        }
        head = &mut head.as_mut().unwrap().next;
    }
    head.take().map(|node| node.data)
}

2 Comments

danics Over a year ago

I understand that we don't mutate the head value in the loop anymore. but it was the case before too. what I don't understand is, how rust figure it out in this case? I mean in the end as_mut function as well takes a &mut self and can internally change the head value, so why rust doesn't complain in this case? and one other question when we mutate a variable twice in a row it should be fine anyway or(like a vec push)?

Chayim Friedman Over a year ago

@danics This is pretty complicated, but the main idea is that Rust doesn't understand that when we break the loop we will not use v anymore, and thus head is free. When we use as_mut().unwrap(), now there is no v and the borrow happen only when we didn't break.

Collectives™ on Stack Overflow

Custom link list pop_back 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