将 append 方法添加到单向链表 [英] Adding an append method to a singly linked list

问题描述

我正在浏览 rustbyexample.com 上的 单链表示例，我注意到实现没有 append 方法，所以我决定尝试实现它:

I was looking through the singly linked list example on rustbyexample.com and I noticed the implementation had no append method, so I decided to try and implement it:

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

以上是许多不同尝试之一，但我似乎无法找到一种方法来迭代到尾部并修改它，然后以某种方式返回头部，而不会以某种方式扰乱借用检查器.

The above is one of many different attempts, but I cannot seem to find a way to iterate down to the tail and modify it, then somehow return the head, without upsetting the borrow checker in some way.

我正在尝试找出一种解决方案，它不涉及复制数据或在 append 方法之外进行额外的簿记.

I am trying to figure out a solution that doesn't involve copying data or doing additional bookkeeping outside the append method.

推荐答案

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

As described in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time, you need to transfer ownership of the mutable reference when performing iteration. This is needed to ensure you never have two mutable references to the same thing.

我们使用与 Q&A 类似的代码来获取对最后一项 (back) 的可变引用，它始终是 Nil 变体.然后我们调用它并将 Nil 项设置为 Cons.我们使用按值函数包装所有这些，因为这是 API 想要的.

We use similar code as that Q&A to get a mutable reference to the last item (back) which will always be the Nil variant. We then call it and set that Nil item to a Cons. We wrap all that with a by-value function because that's what the API wants.

没有额外的分配，没有堆栈帧用完的风险.

No extra allocation, no risk of running out of stack frames.

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

<小时>

当非词法生命周期被启用时，这个功能可以更明显:

---

When non-lexical lifetimes are enabled, this function can be more obvious:

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

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

    node
}

这篇关于将 append 方法添加到单向链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！