掌控 Rust 双向链表：从 `LinkedList＜T＞` 源码到高阶实践的 2000 字深度剖析

2501_94038114

956人浏览 · 2025-10-30 14:59:06

2501_94038114 · 2025-10-30 14:59:06 发布

在这里插入图片描述

关键词：Raw/NonNull、cursor API、Pin<&mut T>、O(1) splice、cache miss、Miri、loom、no_std、静态池、GhostCell

1. 引言：为什么链表在 Rust 里「名声不好」

链表在 C/C++ 里随手可写，但在 Rust 却常被贴上「反模式」标签：

自引用结构体导致借用检查器报怨
频繁的堆分配破坏缓存局部性
标准库 LinkedList<T> 缺少 O(1) 随机访问

然而，在实时嵌入式、无锁队列、LRU Cache 等场景，双向链表仍是不可替代的数据结构。本文将：

逐行拆解标准库 LinkedList<T> 的内存布局与 Cursor API
手写一个 no_std、零堆分配 的静态链表
用 loom 做并发正确性验证，用 Miri 检查未定义行为
给出生产级优化清单：cache-line padding、GhostCell、SPSC 无锁队列

2. 标准库 `LinkedList<T>` 源码级剖析

2.1 节点布局

// 精简版，来自 std::collections::linked_list
struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    element: T, // 内联存储，无额外 Box
}

使用 NonNull 而非裸指针，让 Option<NonNull> 只占 1 个机器字
元素 T 直接内嵌，减少一次间接寻址（相比 Box<Node<T>>）

2.2 链表头尾

pub struct LinkedList<T> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    // 标记 !Send & !Sync，避免跨线程共享
    _marker: PhantomData<Box<Node<T>>>,
}

空链表为 head == tail == None，无需哨兵节点
长度字段 len 让 len() 为 O(1)

2.3 插入与删除：核心 unsafe 块

impl<T> LinkedList<T> {
    pub fn push_front(&mut self, elt: T) {
        let node = Box::into_raw(Box::new(Node {
            next: self.head,
            prev: None,
            element: elt,
        }));
        let node = unsafe { NonNull::new_unchecked(node) };

        match self.head {
            Some(head) => unsafe {
                head.as_ref().prev = Some(node);
            },
            None => self.tail = Some(node),
        }
        self.head = Some(node);
        self.len += 1;
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.map(|node_ptr| unsafe {
            let node = Box::from_raw(node_ptr.as_ptr());
            self.head = node.next;
            match self.head {
                Some(head) => head.as_ref().prev = None,
                None => self.tail = None,
            }
            self.len -= 1;
            node.element
        })
    }
}

思考点：

所有 unsafe 块都需保证节点始终由 Box 分配，避免 malloc/free 混用
编译器无法检查双向指针完整性，需用 loom 模型化并发访问

3. Cursor API：安全地内部可变

标准库 1.68 起提供 Cursor/CursorMut：

let mut list = LinkedList::from([1, 2, 3]);
let mut cur = list.cursor_front_mut();
cur.insert_after(99);
assert_eq!(list.into_iter().collect::<Vec<_>>(), [1, 99, 2, 3]);

CursorMut 内部持 *mut Node<T>，但通过生命周期标记 独占借用，避免别名
提供 split_before, splice 等 O(1) 操作，用于 LRU Cache 移动节点

4. 手写 no_std 静态链表：零堆分配

4.1 场景

嵌入式 MCU 禁止 alloc，但需 64 个固定节点做事件队列。

4.2 节点池

#![no_std]
use core::mem::MaybeUninit;

const POOL_CAP: usize = 64;

struct Node<T> {
    next: u8, // 索引而非指针，节省空间
    prev: u8,
    value: T,
}

pub struct StaticLinkedList<T> {
    pool: [MaybeUninit<Node<T>>; POOL_CAP],
    head: u8, // 255 表示 None
    tail: u8,
    free: u8, // 空闲链表头
    len: u8,
}

4.3 索引与指针转换

impl<T> StaticLinkedList<T> {
    const NONE: u8 = 0xFF;

    fn idx_to_ptr(&self, idx: u8) -> *const Node<T> {
        if idx == Self::NONE { return core::ptr::null(); }
        self.pool[idx as usize].as_ptr()
    }

    fn idx_to_ptr_mut(&mut self, idx: u8) -> *mut Node<T> {
        if idx == Self::NONE { return core::ptr::null_mut(); }
        self.pool[idx as usize].as_mut_ptr()
    }
}

4.4 插入示例

impl<T> StaticLinkedList<T> {
    pub fn push_back(&mut self, value: T) -> Result<(), ()> {
        if self.free == Self::NONE { return Err(()); }
        let idx = self.free;
        let free_next = unsafe { (*self.idx_to_ptr_mut(idx)).next };
        self.free = free_next;

        unsafe {
            *self.pool[idx as usize].as_mut_ptr() = Node {
                next: Self::NONE,
                prev: self.tail,
                value,
            };
        }

        if self.tail != Self::NONE {
            unsafe { (*self.idx_to_ptr_mut(self.tail)).next = idx; }
        } else {
            self.head = idx;
        }
        self.tail = idx;
        self.len += 1;
        Ok(())
    }
}

4.5 静态初始化

impl<T> StaticLinkedList<T> {
    pub const fn new() -> Self {
        const UNINIT: MaybeUninit<Node<()>> = MaybeUninit::uninit();
        let pool = [UNINIT; POOL_CAP];
        Self { pool: unsafe { core::mem::transmute(pool) }, head: Self::NONE, tail: Self::NONE, free: 0, len: 0 }
    }
}

思考点：

使用索引而非裸指针，兼容 Harvard 架构（指针可能 > 16 bit）
MaybeUninit 允许在 const fn 中构建未初始化数组

5. 并发正确性：loom 模型化测试

标准库 LinkedList<T> 不是 Sync，但手写版本若暴露 &mut 给多线程，需验证：

#[cfg(test)]
mod loom_tests {
    use loom::thread;
    use std::collections::LinkedList;
    use std::sync::Arc;

    #[test]
    fn push_pop_race() {
        loom::model(|| {
            let list = Arc::new(std::sync::Mutex::new(LinkedList::<i32>::new()));
            let t1 = {
                let list = list.clone();
                thread::spawn(move || {
                    let mut l = list.lock().unwrap();
                    l.push_back(1);
                })
            };
            let t2 = {
                let list = list.clone();
                thread::spawn(move || {
                    let mut l = list.lock().unwrap();
                    l.pop_front();
                })
            };
            t1.join().unwrap();
            t2.join().unwrap();
        });
    }
}

loom 会把线程交错枚举，发现数据竞争
若改用 GhostCell（基于 epoch 的无锁链表），还需用 loom 验证 Acquire/Release 顺序

6. 生产级优化清单

优化点	做法
False sharing	节点前后加 `#[repr(align(64))]` 填充
SPSC 无锁队列	使用 `crossbeam-queue::ArrayQueue` 替代链表
LRU Cache	用 `CursorMut::splice` 把节点移动到表头
自定义分配器	在节点上实现 `Allocator` trait，减少系统调用
内存序	无锁链表用 `AtomicPtr` + `Ordering::Acquire/Release`

7. 性能基准：链表 vs VecDeque

use criterion::{black_box, criterion_group, criterion_main, Criterion};
use std::collections::LinkedList;

fn bench_push_pop(c: &mut Criterion) {
    c.bench_function("linked_list_push_pop", |b| {
        b.iter(|| {
            let mut list = LinkedList::new();
            for i in 0..1_000 {
                list.push_back(black_box(i));
            }
            for _ in 0..1_000 {
                black_box(list.pop_front());
            }
        })
    });
}

criterion_group!(benches, bench_push_pop);
criterion_main!(benches);