双向链表

说明

使用unsafe Rust 编写一个双向链表，其中包括一个遍历链表的迭代器，以及一个用于高效修改的游标。

双向链表是计算机科学中的一种基础数据结构。

双向链表中的每个节点都包含数据，以及指向后一个节点和前一个节点的指针（如果存在的话）。

只要已经持有某个位置的引用，就能高效地把新节点添加到链表的任意位置。同样，也可以在常数时间内把另一个链表中的所有元素插入到任意位置。

在 Rust 中，链表很少被使用，但偶尔会在新手尝试实现链表时把他们绊住。他们常常会发现，与还不熟悉的借用检查器打交道出乎意料地困难。

关于unsafe的说明

请记住，unsafe Rust 的目标是：在编译器无法帮助我们保证正确性的情况下，依然能写出安全的代码。用户仅使用我们暴露出的安全接口，绝不能造成任何形式的内存不安全。

记录下你需要维护的、关乎安全的关键不变量，并为每个 unsafe 块添加注释，说明它为什么是安全的。

任何要求调用方维护这些安全关键不变量的函数，都应标记为 unsafe，私有函数也不例外。

第 1 步

实现从头部和尾部添加、删除元素（压入和弹出）的功能。这已足够把链表当作双端队列使用。同时实现len和is_empty函数。

在最终实现中，对链表的所有修改都应通过游标结构体完成，以尽量减少重复代码。LinkedList上的push_*和pop_*方法，是在pre_implemented模块中依据游标的必需方法定义的。如果愿意，你目前可以先跳过Cursor结构体，直接重写这些方法，但请在最后把它们改回去。

第 2 步

使用Iter结构体实现从头到尾遍历链表。

第 3 步

补全游标的功能。它应该能移动到任意位置，并在那里插入或删除元素。

第 4 步

为你的LinkedList实现Drop trait，以清理资源。

第 5 步（进阶且可选）

最后两项的测试通过特性开关advanced有条件地编译。要启用它们，请把键default = ["advanced"]添加到Cargo.toml文件的[features]下。

为了让你的结构体的使用者拥有最大的灵活性，请确保LinkedList<T>对T是协变的。例如，这意味着LinkedList<&'static T>也可以当作LinkedList<&'a T>使用。关于 Rust 中变型的说明，请参阅 Rustonomicon。

请确保你的链表可以安全地跨线程边界发送和共享，并通过手动实现Send和Sync向类型系统表明这一点。这些 trait 通常会自动派生，但这里由于使用了裸指针而不会自动实现。关于它们的重要意义，请参阅 Send 和 Sync 的文档，以及 rustonomicon 章节。