笔者听到了很多对于Rust中实现数据结构如何如何困难这样对Rust的评价。如果笔者说这样的评价不客观那叫睁着眼睛说瞎话。因为想要在Rust语言中实现数据结构的确有一些难度。所以笔者就以开了上帝视角的“过来人”的身份来告诉初学者一些使用Rust编写数据结构的一些技巧。在学会这些技巧后，您会发现实际上使用Rust来开发数据结构比别的语言还要简单呢。

开发之前

在开发之前，您需要明确本文内容只是把链表作为一种示例数据结构。您并不需要开发链表，因为它已经被写好了。本文的目的是指导任何一个还不会开发自己的私有数据结构的读者使用Rust开发数据结构相关的内容。此外，在绝大多数情况下您都不需要自己开发新的数据结构，因为您可以很方便的使用标准库中提供的内容。

简单链表的实现

如果按照过去语言的思路我们似乎应该这样写：

struct Node<T> {
    value: T,
    next: Box<Node<T>>,
}

然而如果您这样写了就会发现一个可怕的事情，即您永远都不能定义这个链表。因为这个链表会不断的向您所求下一个Node是什么。正确的写法是：

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

当然为了接下来好操作您可以加上 #[derive(Clone, Debug)]。这里笔者展示了 new、set_next、get_last 和 push 这四个必要函数的写法。

impl<T> Node<T> {
    fn new(elem: T) -> Self {
        Node {
            value: elem,
            next: None,
        }
    }
    
    fn set_next(&mut self, node: Self) {
        self.next = Some(Box::new(node));
    }
    
    fn get_last<'a>(&'a mut self) -> &'a mut Self {
        if let Some(ref mut x) = self.next {
            return x.get_last();
        } 
        self
    }
    
    fn push(&mut self, elem: T) {
        let new_node = Node::new(elem);
        self.get_last().set_next(new_node);
    }
}

您会发现如果这样写链表您是没有办法写 pop 函数的。因为第一个节点总是没办法 pop。我们需要在第一个节点之前增加一个附设节点。称之为头结点。实际上您在其他语言中也是这样操作的。（详细请参考：参考书1）

参考书1: 严蔚敏, 吴伟民.《数据结构（C语言版）》.北京: 清华大学出版社. 1997

在Rust中您需要单独写一个头结点的类型：

#[derive(Clone, Debug)]
struct List<T> {
    len: usize,
    next: Option<Box<Node<T>>>,
}

阅读全文