嗨！我是一名正在学习Rust的大三学生。数据结构课讲到链表时，老师提到"在Rust中实现链表是出了名的难"。我不信邪，决定自己研究一下Rust的LinkedList实现。结果发现，这确实是我学Rust以来遇到的最大挑战！今天想和大家分享我这一周的探索历程。💪
缘起：一次失败的尝试
作为数据结构课的作业，我想用Rust实现一个双向链表。凭着学C++的经验，我写下了这样的代码：
// 这段代码无法编译！
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
prev: Option<Box<Node<T>>>, // 问题在这里！
}
编译器立刻报错：
error: recursive type has infinite size
我困惑了：C++的链表不就是这样写的吗？为什么Rust不行？经过一整天的研究，我发现问题的根源在于Rust的所有权系统。
核心问题：所有权与双向引用的矛盾
让我画个图解释这个问题：
理想的双向链表：
┌─────┐ ┌─────┐ ┌─────┐
│ A │◄──►│ B │◄──►│ C │
└─────┘ └─────┘ └─────┘
Rust的困境：
- A拥有B（通过next）
- B拥有A（通过prev）← 循环所有权！
- 谁负责释放内存？
关键发现：Rust的所有权系统不允许循环引用！这是设计上的基本原则，不是bug。
那Rust标准库的LinkedList是怎么实现的呢？答案是：使用裸指针（raw pointers）。
深入源码：标准库的实现
我阅读了Rust标准库的LinkedList源码，发现它的结构是这样的：
pub struct LinkedList<T> {
head: Option<NonNull<Node<T>>>, // 头指针
tail: Option<NonNull<Node<T>>>, // 尾指针
len: usize, // 长度
marker: PhantomData<Box<Node<T>>>, // 幽灵数据
}
struct Node<T> {
next: Option<NonNull<Node<T>>>, // 下一个节点
prev: Option<NonNull<Node<T>>>, // 上一个节点
element: T, // 数据
}
画个示意图：
LinkedList结构（栈上）
┌──────────────────┐
│ head: NonNull<A> │─┐
│ tail: NonNull<C> │─┼─┐
│ len: 3 │ │ │
└──────────────────┘ │ │
↓ │
┌─────┐ next ┌─────┐ │
│ A │─────►│ B │─┼►┌─────┐
│ │◄─────│ │ ││ C │
└─────┘ prev └─────┘ │└─────┘
▲ │
└──────────────────┘
关键设计：
-
使用NonNull代替Box：不自动管理所有权
-
手动管理内存分配和释放
-
大量使用unsafe代码
实践一：理解NonNull
我写了个实验来理解NonNull：
use std::ptr::NonNull;
use std::alloc::{alloc, dealloc, Layout};
fn test_nonnull() {
unsafe {
// 分配内存
let layout = Layout::new::<i32>();
let ptr = alloc(layout) as *mut i32;
// 创建NonNull（保证非空）
let mut nn = NonNull::new(ptr).unwrap();
// 写入数据
*nn.as_mut() = 42;
// 读取数据
println!("值: {}", *nn.as_ref());
// 手动释放
dealloc(ptr as *mut u8, layout);
}
}
发现：
-
NonNull是对*mut T的包装，但保证非空
-
不拥有所有权，不会自动释放内存
-
必须手动管理生命周期
实践二：实现简化版LinkedList
为了深入理解，我尝试实现一个简化版：
use std::ptr::NonNull;
struct MyLinkedList<T> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
}
struct Node<T> {
element: T,
next: Option<NonNull<Node<T>>>,
prev: Option<NonNull<Node<T>>>,
}
impl<T> MyLinkedList<T> {
pub fn new() -> Self {
MyLinkedList {
head: None,
tail: None,
len: 0,
}
}
pub fn push_back(&mut self, element: T) {
unsafe {
// 在堆上分配新节点
let new_node = Box::new(Node {
element,
next: None,
prev: self.tail,
});
// 转换为裸指针
let new_node_ptr = NonNull::new_unchecked(Box::into_raw(new_node));
match self.tail {
None => {
// 空链表
self.head = Some(new_node_ptr);
self.tail = Some(new_node_ptr);
}
Some(mut tail_ptr) => {
// 链接到尾部
tail_ptr.as_mut().next = Some(new_node_ptr);
self.tail = Some(new_node_ptr);
}
}
self.len += 1;
}
}
pub fn pop_back(&mut self) -> Option<T> {
unsafe {
self.tail.map(|tail_ptr| {
let tail = Box::from_raw(tail_ptr.as_ptr());
self.tail = tail.prev;
match self.tail {
None => {
// 链表变空
self.head = None;
}
Some(mut new_tail) => {
new_tail.as_mut().next = None;
}
}
self.len -= 1;
tail.element
})
}
}
}
impl<T> Drop for MyLinkedList<T> {
fn drop(&mut self) {
// 必须手动清理所有节点
while let Some(_) = self.pop_back() {}
}
}
这段代码写了改、改了写，我花了整整两天才调通。期间遇到的坑包括：
坑1：忘记释放内存
// 内存泄漏！
let node = Box::into_raw(Box::new(Node { ... }));
// 没有对应的from_raw释放
// 正确做法
let ptr = Box::into_raw(box_node);
// 使用后...
let _ = Box::from_raw(ptr); // 自动释放
坑2：悬垂指针
// 危险！
let mut node = Box::new(Node { ... });
let ptr = NonNull::from(&*node);
drop(node); // node被释放
// ptr现在指向无效内存！
坑3：忘记更新链接
// ❌ 插入节点时忘记更新prev指针
new_node.next = old_next;
// 忘了：old_next.prev = new_node;
实践三：性能测试
我对比了LinkedList和Vec的性能：
use std::collections::LinkedList;
use std::time::Instant;
fn benchmark() {
const N: usize = 100000;
// Vec：尾部插入
let start = Instant::now();
let mut vec = Vec::new();
for i in 0..N {
vec.push(i);
}
println!("Vec push: {:?}", start.elapsed());
// LinkedList：尾部插入
let start = Instant::now();
let mut list = LinkedList::new();
for i in 0..N {
list.push_back(i);
}
println!("LinkedList push_back: {:?}", start.elapsed());
// Vec：头部插入
let start = Instant::now();
let mut vec = Vec::new();
for i in 0..1000 { // 数量减少，太慢了
vec.insert(0, i);
}
println!("Vec insert(0): {:?}", start.elapsed());
// LinkedList：头部插入
let start = Instant::now();
let mut list = LinkedList::new();
for i in 0..1000 {
list.push_front(i);
}
println!("LinkedList push_front: {:?}", start.elapsed());
}
测试结果：
Vec push: 0.8ms
LinkedList push_back: 4.2ms （慢5倍）
Vec insert(0): 125ms
LinkedList push_front: 0.05ms （快2500倍！）
分析：
-
尾部插入：Vec更快（连续内存，缓存友好）
-
头部插入：LinkedList完胜（O(1) vs O(n)）
深度思考：为什么LinkedList很少用？
经过一周的研究，我理解了为什么Rust社区很少用LinkedList：
- 性能通常不如Vec
// 遍历性能对比
let vec: Vec<i32> = (0..10000).collect();
let list: LinkedList<i32> = (0..10000).collect();
// Vec：缓存友好，连续内存
for x in &vec {
// 快
}
// LinkedList：缓存不友好，指针跳转
for x in &list {
// 慢
}
原因：现代CPU的缓存机制对连续内存访问优化极佳。
- 内存开销大
use std::mem;
println!("Vec<i32>元素开销: {} 字节", mem::size_of::<i32>());
// 输出：4字节
println!("LinkedList节点开销: {} 字节",
mem::size_of::<i32>() + 2 * mem::size_of::<usize>());
// 输出：20字节（数据4B + 两个指针16B）
LinkedList每个元素要额外占用16字节的指针空间！
- 实现复杂，易出bug
我的简化版实现有200行代码，标准库的完整版有1000+行。相比之下，Vec的核心实现只有300行左右。
结论：除非确实需要O(1)的头部/中间插入删除，否则优先用Vec。
实践四：LinkedList的合理使用场景
经过研究，我总结了LinkedList的适用场景：
// 场景1：LRU缓存（频繁头尾操作）
struct LRUCache<K, V> {
map: HashMap<K, *mut Node<V>>,
list: LinkedList<V>,
capacity: usize,
}
// 场景2：任务队列（FIFO）
let mut queue = LinkedList::new();
queue.push_back(task1); // 入队
queue.pop_front(); // 出队
// 场景3：中间频繁插入删除
let mut list = LinkedList::new();
let mut cursor = list.cursor_front_mut();
cursor.insert_after(element); // O(1)插入
我的学习心得
我理解了 Rust 所有权禁止循环引用的本质，掌握了 unsafe 的使用场景与安全方法，也认识到算法复杂度不等于实际性能；思维上，我意识到工具选择需务实、理解底层才能用好上层，且安全与性能、简单与灵活的权衡无处不在；实践中明确默认用 Vec，频繁头部操作选 VecDeque，中间频繁插入删除可考虑 LinkedList，也知晓实现自定义链表难度极高。最大感悟是，Rust 通过所有权强制开发者思考内存管理，虽增加了学习难度，却换来了安全性和性能，而 LinkedList 的实现难度，更体现出 Rust 设计的深思熟虑。
