rust - 向单向链表添加追加方法

Question

我正在浏览 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 方法之外进行额外的簿记。

Answer 1

如 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。我们用一个按值函数包装所有这些，因为这是 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
}