我正在浏览singly linked list example on rustbyexample.com，我注意到实现没有append方法，所以我决定尝试实现它：
fn append(self, elem: u32) -> List {
let mut node = &self;
loop {
match *node {
Cons(_, ref tail) => {
node = tail;
},
Nil => {
node.prepend(elem);
break;
},
}
}
return self;
}
以上是许多不同尝试之一，但我似乎无法找到一种方法迭代到尾部并修改它，然后以某种方式返回头部，而不会以某种方式扰乱借用检查器。
我试图找出一个解决方案，不涉及复制数据或在append方法之外进行额外的簿记。
如Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time中所述，您需要在执行迭代时转移可变引用的所有权。这需要确保您永远不会有两个可变引用相同的东西。
我们使用类似于Q＆A的代码来获得对最后一项（back）的可变引用，该项最终将是Nil变体。然后我们调用它并将Nil项设置为Cons。我们使用by-value函数包装所有这些，因为这是API想要的。
没有额外的分配，没有堆栈帧耗尽的风险。
use List::*;
#[derive(Debug)]
enum List {
Cons(u32, Box<List>),
Nil,
}
impl List {
fn back(&mut self) -> &mut List {
let mut node = self;
loop {
match {node} {
&mut Cons(_, ref mut next) => node = next,
other => return other,
}
}
}
fn append_ref(&mut self, elem: u32) {
*self.back() = Cons(elem, Box::new(Nil));
}
fn append(mut self, elem: u32) -> Self {
self.append_ref(elem);
self
}
}
fn main() {
let n = Nil;
let n = n.append(1);
println!("{:?}", n);
let n = n.append(2);
println!("{:?}", n);
let n = n.append(3);
println!("{:?}", n);
}
启用non-lexical lifetimes时，此功能可以更明显：
fn back(&mut self) -> &mut List {
let mut node = self;
while let Cons(_, next) = node {
node = next;
}
node
}
由于len方法是递归实现的，我对append实现也做了同样的事情：
fn append(self, elem: u32) -> List {
match self {
Cons(current_elem, tail_box) => {
let tail = *tail_box;
let new_tail = tail.append(elem);
new_tail.prepend(current_elem)
}
Nil => {
List::new().prepend(elem)
}
}
}
一个可能的迭代解决方案是用append和反向函数来实现prepend，就像这样（它不会是高效的，但仍然只能是O（N））：
// Reverses the list
fn rev(self) -> List {
let mut result = List::new();
let mut current = self;
while let Cons(elem, tail) = current {
result = result.prepend(elem);
current = *tail;
}
result
}
fn append(self, elem: u32) -> List {
self.rev().prepend(elem).rev()
}
所以，它实际上会比你想象的要困难一些;主要是因为Box真的缺少一种破坏性的take方法，它将返回其内容。
简单的方法：递归的方式，没有回报。
fn append_rec(&mut self, elem: u32) {
match *self {
Cons(_, ref mut tail) => tail.append_rec(elem),
Nil => *self = Cons(elem, Box::new(Nil)),
}
}
如上所述，这相对容易。
更难的方式：递归方式，带回报。
fn append_rec(self, elem: u32) -> List {
match self {
Cons(e, tail) => Cons(e, Box::new((*tail).append_rec(elem))),
Nil => Cons(elem, Box::new(Nil)),
}
}
请注意，这非常低效。对于大小为N的列表，我们正在销毁N个盒子并分配N个新盒子。就地变异（第一种方法）在这方面要好得多。
更难的方式：迭代的方式，没有回报。
fn append_iter_mut(&mut self, elem: u32) {
let mut current = self;
loop {
match {current} {
&mut Cons(_, ref mut tail) => current = tail,
c @ &mut Nil => {
*c = Cons(elem, Box::new(Nil));
return;
},
}
}
}
好的......所以在嵌套数据结构上迭代（可变）并不容易，因为所有权和借用检查将确保：
这就是为什么这里：
{current}将current移动到比赛中，c @ &mut Nil，因为我们需要一个来命名&mut Nil的匹配，因为current已被移动。请注意，幸运的是，rustc足够聪明，可以检查执行路径并检测可以继续循环，只要我们采用Cons分支，因为我们重新初始化该分支中的current，但是在采取Nil分支后继续进行是不行的我们终止循环:)
更难的方式：迭代方式，返回
fn append_iter(self, elem: u32) -> List {
let mut stack = List::default();
{
let mut current = self;
while let Cons(elem, tail) = current {
stack = stack.prepend(elem);
current = take(tail);
}
}
let mut result = List::new();
result = result.prepend(elem);
while let Cons(elem, tail) = stack {
result = result.prepend(elem);
stack = take(tail);
}
result
}
以递归的方式，我们使用堆栈为我们保留项目，这里我们使用堆栈结构。
它比返回的递归方式效率更低;每个节点导致两次解除分配和两次分配。
TL; DR：就地修改通常更有效，不必害怕在必要时使用它们。