如何实现一个链表的加法？

Question

我想创建一个简单的链表并向其中添加一个值。 add 方法应该如何实现才能使这段代码在第 42 行输出 100 50 10 5，第二次 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();
}

(Playground)

我重写了这个函数：

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; }
        }
    }
}

但是编译器说

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

我不明白为什么它说那个项目只用过一次就被移动了，以及如何实现 Some(_) 分支来遍历列表？

Answer 1

这就是你需要的写法(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,
        };
    }
}

好的，这是什么？

步骤1，我们需要在使用值item后立即return。然后编译器正确地看到它只被移动了一次。

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

第 2 步，使用我们沿途更新的 &mut 指针循环是很棘手的。

默认情况下，Rust 将重新借用 一个被解引用的&mut。它不消耗引用，它只是认为它是借来的，只要借来的产品还活着。

显然，这在这里效果不佳。我们想要从旧 current 到新 current 的“交接”。我们可以强制 &mut 指针服从改为移动语义。

我们需要这个（identity 函数强制移动！）：

match moving(current).next

我们也可以这样写：

let tmp = current;
match tmp.next

或者这个：

match {current}.next

第 3 步，我们在内部查找后没有当前指针，因此请修改代码。

使用ref mut slot 获取下一个值的位置。

如何实现一个链表的加法？

How to implement an addition method of linked list?

rust