将附加方法添加到单个链接列表

Question

我正在查看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

如在迭代递归结构时无法获取可变引用:不能一次多次借用可变引用,您需要在执行迭代时转移可变引用的所有权.这需要确保您永远不会有两个对同一事物的可变引用.

我们使用与Q&A类似的代码来获取对最后一个项目(back)的可变引用,该项目始终是Nil变体.然后我们调用它并将该项设置Nil为a 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);
}

当启用非词法生命周期时,此功能可以更明显:

fn back(&mut self) -> &mut List {
    let mut node = self;

    while let Cons(_, next) = node {
        node = next;
    }

    node
}