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

这将无法编译,因为由于不兼容的可变性,下一个不能在match语句中分配给tail.我知道这可以很容易地使用垃圾收集指针来完成,但这种做法违背了练习的教育目的:我想知道如何在没有Gc或Rc指针的情况下做到这一点.

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

由于可变借用的问题,我不确定如何使用迭代方法实现这一点.