Rust：如何实现链表？

Question

我想通过实现一些非常简单的数据结构和算法来深入了解Rust，我从链表开始。结果发现这并不是那么简单。以下是我的代码：

enum List<T> 
{
    Node(T, ~List<T>),
    Nil
}

impl<T> List<T>
{
    fn new(vector: &[T]) -> List<T> { Nil }

    fn add(&mut self, item: T)
    {
        let tail = self;
        loop
        {
            match *tail
            {
                Node(_, ~ref next) => tail = next,
                Nil => break
            }
        }
        *tail = Node(item, ~Nil);
    }
}

由于不兼容的可变性，此代码无法编译，因为在匹配语句中无法将 next 分配给 tail。我知道可以使用垃圾收集指针轻松完成这个问题，但那样做有点违背了练习的教育目的：我想知道如何在没有 Gc 或 Rc 指针的情况下完成这个问题。

- kralyk

Answer 1

看起来你试图遍历自己的列表以找到最后一个元素，但实际上你并没有循环。假设你修复了这个问题，使用ref mut代替ref可以解决可变性问题。

为了尝试它，我使用了add()的递归实现，它可以正常工作。

fn add(&mut self, item: T) {
    match *self {
        Node(_, ref mut next) => next.add(item),
        Nil => *self = Node(item, ~Nil)
    }
}

一时半会儿我不确定如何使用迭代方法来实现这个，因为存在可变借用的问题。

- Lily Ballard

---

谢谢！是的，我用了一个循环，但是我在使用循环和递归的方法时来回切换，我想在某个时候我失去了它。我会进行编辑。 - kralyk

Answer 2

迭代解决方案，使用 Box::borrow_mut()：

#[derive(Debug)]
enum List<T> {
    Node(T, Box<List<T>>),
    Nil
}

impl<T> List<T> {
    fn new() -> List<T> { List::Nil }

    fn add(&mut self, item: T) {
        use std::borrow::BorrowMut;
        
        let mut tail = self;
        while let Self::Node(_, next) = tail {
            tail = next.borrow_mut();
        }
        *tail = List::Node(item, Box::new(List::Nil));
    }
}

游乐场链接

- Ben