继续 Rust 标准库 学习系列， 这次是 LinkedList<T>。注意，实现来自 Rust stable v1.33.0.

拥有节点的双向列表。

LinkedList 永许在常量时间内从两端 push和pop 元素。

大多数情况最好用 Vec 或 VecDeque 替代 LinkedList。通常，基于数组的容器更快，内存效率更高，并且更好的利用 CPU 缓存。

Rust std doc

与 Vec<T> 不同的是

  1. 通过索引访问一个元素需要对列表进行线性迭代。
  2. append is O(1)。
  3. 有趣的是 linked_list::Iter 与 linked_list::IterMut 的不同之处。IterMut的不可变性用 &mut 和 PhantomData<&a Node<T>> 确保健全性 (更多关于 PhantomData，稍后说明)。

这儿有 一本书 (如果你没读过这本书，我强烈建议你去阅读它的细节) 向读者解释了为什么单链表难以实现，而且对于 Rust 新用户来说不是个好主意。

由于 Rust 的类型系统/所有权，实际上很难实现双向列表。 主要原因是一个节点似乎需要来自相邻节点的两个所有者。然而， 不过，这对于 NonNull<T> 是可能的，我们在 Vec<T> 学习 中讨论过。

这是简化的定义

// Note: NonNull<T> does NOT own the referent
#[repr(transparent)] // <-- enforces the same type representation as *const T
struct NonNull<T: ?Sized> {
pointer: *const T,
}
struct Node<T> {
next: Option<NonNull<Node<T>>>, // Not Option<Box<Node<T>>>
prev: Option<NonNull<Node<T>>>,
element: T,
}
struct LinkedList<T> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
marker: PhantomData<Box<Node<T>>>, // <-- sound dropck
}

为什么不是 Option<Box<Node<T>>> ?

如果我们用 Box<Node<T>> 来代替，看看有什么不同，这可能是个好主意。 我们讨论了什么是 Unique<T> 以及它与 NonNull<T> 有何不同，但作为一个快速提醒， Unique<T> 拥有 referent 而 NonNull<T> 没有， 实际上， Box<T> (用于堆分配的指针类型) 包装了 Unique<T> 提供了与 Unique<T> 交互的新的介面。

让我们考虑 Node<T> 使用 Box (playpen link)

struct Node<T> {
prev: Option<Box<Node<T>>>,
next: Option<Box<Node<T>>>,
element: T,
}
fn main() {
let mut head_node = Node {
prev: None,
next: None,
element: 1,
};

let next_node = Node {
prev: Some(Box::new(head_node)), // <-- head_node is moved here
next: None,
element: 2,
};

head_node.next = Some(Box::new(next_node)); // Not good!
}

这要求 Use-After-Free (UAF) 所以我们直到我们不应该进一步推进 Undefined Behavior (UB) 的行为。 不过, 使用一个 non-owning NonNull<T> 可以解决以下问题 (playpen link)

use std::ptr::NonNull;
struct Node<T> {
prev: Option<NonNull<Node<T>>>,
next: Option<NonNull<Node<T>>>,
element: T,
}
fn main() {
let mut head_node = Node {
prev: None,
next: None,
element: 1,
};

let next_node = Node {
prev: NonNull::new(&mut head_node as *mut _),
next: None,
element: 2,
};

head_node.next = NonNull::new(&next_node as *const _ as *mut _);
}

但是我们如何确保这是合理的， 特别是把它用于 LinkedList<T>。确切的说

然而 PhantomData 和 dropck 有什么关系?

我一直在试图理解 PhantomData 和 dropck 之间的深层关系(LinkedList<T> 也是如此)，但是找不到任何明确的解释，所以我在用户频道问了它并得到了一个 令人惊奇的答案 可以被推广到 Vec, LinkedList 等。

本文翻译自 Rust std study series: LinkedList

推荐阅读：

相关文章