How to implement an addition method of linked list?

Question

I want to create a simple linked list and add a value into it. How should the add method be implemented to make this code output 100 50 10 5 at line 42, the second root.print() call?

use std::rc::Rc;

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

impl Node {
    fn print(&self) {
        let mut current = self;
        loop {
            println!("{}", current.value);
            match current.next {
                Some(ref next) => {
                    current = &**next;
                }
                None => break,
            }
        }
    }

    fn add(&mut self, node: Node) {
        let item = Some(Box::new(node));
        let mut current = self;
        loop {
            match current.next {
                None => current.next = item,
                _ => {} 
                //Some(next) => { current = next; }
            }
        }
    }
}

fn main() {
    let leaf = Node {
        value: 10,
        next: None,
    };
    let branch = Node {
        value: 50,
        next: Some(Box::new(leaf)),
    };
    let mut root = Node {
        value: 100,
        next: Some(Box::new(branch)),
    };
    root.print();

    let new_leaf = Node {
        value: 5,
        next: None,
    };
    root.add(new_leaf);
    root.print();
}

(Playground)

I rewrote the function like this:

fn add(&mut self, node: Node) {
    let item = Some(Box::new(node));
    let mut current = self;
    loop {
        match current {
            &mut Node {
                     value: _,
                     next: None,
                 } => current.next = item,
            _ => {} 
            //Some(next) => { current = next; }
        }
    }
}

but the compiler says

error[E0382]: use of moved value: `item`
  --> <anon>:28:40
   |
28 |                 None => current.next = item,
   |                                        ^^^^ value moved here in previous iteration of loop
   |
   = note: move occurs because `item` has type `std::option::Option<std::boxed::Box<Node>>`, which does not implement the `Copy` trait

I don't understand why it says that item was previously moved if it's used only once, and how the Some(_) branch should be implemented to iterate through the list?

Answer 1

This is how you need to write it (playground link)

fn add(&mut self, node: Node) {
    let item = Some(Box::new(node));
    let mut current = self;
    loop {
        match moving(current).next {
            ref mut slot @ None => {
                *slot = item;
                return;
            }
            Some(ref mut next) => current = next,
        };
    }
}

Ok, so what is this?

Step 1, we need to return immediately after using the value item. Then the compiler correctly sees that it is only moved from once.

ref mut slot @ None => {
    *slot = item;
    return;
}

Step 2, to loop with a &mut pointer that we update along the way is tricky.

By default, Rust will reborrow a &mut that is dereferenced. It doesn't consume the reference, it just considers it borrowed, as long as the product of the borrow is still alive.

Obviously, this doesn't work very well here. We want a “hand off” from the old current to the new current. We can force the &mut pointer to obey move semantics instead.

We need this (the identity function forces move!):

match moving(current).next 

we can also write it like this:

let tmp = current;
match tmp.next

or this:

match {current}.next

Step 3, we have no current pointer after we looked up inside it, so adapt the code to that.

• Use ref mut slot to get a hold on the location of the next value.