如何在Rust中实现链表

提示: 如代码出现折行，请将手机旋转锁定取消后横屏阅读

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

开发之前

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

简单链表的实现

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

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

当然为了接下来好操作您可以加上 。这里笔者展示了 、、 和 这四个必要函数的写法。

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

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

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

这里笔者给了一个附加的长度信息，如果您觉得这是不必要的，也可以去掉。此外根据需要也对 类型增加了部分方法:

读到这里笔者相信对于各位读者来说如何给新的链表类型写构造方法已经不需要讲解了:

那么我们现在就来讲解下面两个核心方法—— 方法和 方法的实现。对于 方法来说和 的情况基本一致：

这里只需要注意处理原本是个空链表的情况即可，此外我们需要实现对于新的链表类型的 方法：

这里重点需要讲解的是 方法的实现思路：

首先我们需要处理的就是这个链表是一个空链表的情况。这里我们可以很方便的读取出长度信息。如果是一个空链表马上返回 。这是一个技巧，可以有效的减少一层不必要的嵌套。接下来是我们处理弹出末节点的核心部分。

接着我们需要对链表进行整理，即隐藏 类型和与其相关的函数。经过整理后得到：

因为我们的弹出方法是不能返回值的，我们这里增加了获取末尾节点值的方法，和一系列相关方法，现在来试试吧：

您现在可能会说笔者实在是太不负责任了，这种东西难以有什么实际的用途呀。实际上如果您给泛型 增加 特征的话会方便许多。在没有 的情况下我们不能深拷贝一个已经得到的值。且Rust总是限制我们在同时进行多次可变引用或在不可变引用没有结束前进行可变引用。不过我们构建双向链表，而且您会发现标准库中提供的正是双向链表：

如果您想封装一个好的库应该采用测试驱动开发的方式来进行测试。限于篇幅原因，我们把测试驱动开发的部分放在《Rust 程序设计语言实例教程》中去讲解。