How do I implement a method for adding a linked list?
I want to create a simple linked list and add a value to it. How do I implement a method add
to make this code output 100 50 10 5
on line 42, the second call root.print()
?
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();
}
I rewrote a 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 the item has been moved earlier if it is only used once and how the branch Some(_)
should be implemented to repeat in the list?
source to share
This is how you need to write (link to playgrounds)
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,
};
}
}
So what is it?
Step 1 , we need return
immediately after using the value item
. The compiler then correctly sees that it only moves once.
ref mut slot @ None => {
*slot = item;
return;
}
Step 2 , the loop with the pointer &mut
that we update along the way is tricky.
By default, Rust will reborrow a &mut
, which is dereferenced. He does not use the link, he just thinks that he is borrowed while the borrowed product is still alive.
Obviously not very good here. We want to "undo" from old current
to new current
. We can make the pointer &mut
obey Move the semantics instead.
We need this (moving functions identity
move!):
match moving(current).next
we can also write it like this:
let tmp = current;
match tmp.next
or that:
match {current}.next
Step 3 , we don't have a current pointer after looking inside it, so we'll adapt the code to that.
- Use the
ref mut slot
next value to fix the location.
source to share