如何實現鏈表的加法？

Question

我想創建一個簡單的鏈接列表並向其中添加一個值。 add方法應該如何實現，以使該代碼輸出100 50 10 5在第42行，第二個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

這就是你需要寫它(playpen link)

fn add(&mut self, node: Node) 
{ 
    /// Identity function. Move the input to output. 
    fn moving<T>(x: T) -> T { x } 

    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。然後編譯器正確地看到它僅從一次移動。

=> { *slot = item; return } 

步驟2，與我們更新很長的路是棘手的一個&mut指針循環。

默認情況下，Rust將重新出借 a &mut這是取消引用。它不會消耗參考資料，只要借用的產品仍然存在，它就會認爲它是借來的。

顯然，這在這裏並不奏效。我們希望從舊的current到新的current「手」。我們可以強制&mut指針服從 移動語義。

我們需要這個（身份功能的力量感動！）：

match moving(current).next 

我們也可以把它寫這樣的：

let tmp = current; 
match tmp.next 

或本：

match {current}.next 

第3步，在我們查看它之後，我們沒有當前的指針，所以請修改代碼那。

• 使用ref mut slot來獲得下一個值的位置。
• 將 next從 Some(ref mut next)移到匹配的外部，以便具有None的另一個分支已經返回並且其借位與循環的最後一行上的更新 current不衝突。 這是不必要的。