Linked Lists - why is this working?

help
1

Hi there!

I've been tinkering with Linked Lists trying to implement one for a while, and after failing numerous times, I've come across something that looks functional.

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkedList {
    root: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { root: None }
    }

    fn insert(&mut self, val: i32) {
        let new_node = Node{value: val, next: None};
        let mut current_node = &mut self.root;
        while let Some(ref mut node) = current_node {
            current_node = &mut node.next;
        }
        *current_node = Some(Box::new(new_node));
    }

    fn print_vals(& self) {
        let mut current_node = & self.root;
        while let Some(node) = current_node {
            println!("node value is {}", node.value);
            current_node = & node.next;
        }
    }

}

fn main() {
    let mut a: LinkedList = LinkedList::new();
    a.insert(1);
    a.insert(2);
    a.insert(3);
    a.insert(4);
    a.insert(5);
    a.print_vals();
}

However, I don't understand why this is working.
My expectation here would be that the compiler would not allow me to run this, as node itself is under a mutable borrow, meaning that I cannot access the node.next through a borrow, or a mutable one either way.

Is it allowed due to the fact that node is no longer accessed?

Any explanation will be greatly appreciated :bowing_man:

PS: Have mercy on me, I'm just a rust newbie.

2

Yes; because you are using node exactly once, the lifetime of a borrow from it may be just as long as the current_node it borrows from. If you used node further after current_node = &mut node.next, then the borrow &mut node.next would have to have a shorter lifetime not overlapping with that second use, and so it could not be assigned to current_node.

1 Like
3

Hi there, thanks for the answer!

I was thinking the same, but turns out

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct LinkedList {
    root: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { root: None }
    }

    fn insert(&mut self, val: i32) {
        let new_node = Node{value: val, next: None};
        let mut current_node = &mut self.root;
        while let Some(ref mut node) = current_node {
            current_node = &mut node.next;
            node.value = 32;
        }
        *current_node = Some(Box::new(new_node));
    }

    fn print_vals(& self) {
        let mut current_node = & self.root;
        while let Some(node) = current_node {
            println!("node value is {}", node.value);
            current_node = & node.next;
        }
    }

}

fn main() {
    let mut a: LinkedList = LinkedList::new();
    a.insert(1);
    a.insert(2);
    a.insert(3);
    a.insert(4);
    a.insert(5);
    a.print_vals();
}

This works as well.

4

That is because current_node is only reborrowing node.next, so node.value can still be accessed through node. The Rust compiler is fortunately smart enough to treat different fields of a struct as distinct places that can be separately borrowed.

3 Likes
5

That‘s sometimes called “borrow splitting”.

2 Likes