Rust并发链表实现（从零开始构建线程安全的无锁链表）

前置知识

在开始之前，请确保你已安装 Rust（推荐使用 rustup），并了解以下概念：

• Arc<T>：原子引用计数，用于在线程间共享所有权
• AtomicPtr<T>：原子指针，支持无锁操作
• Option<Box<Node>>：表示链表节点的可选性
• CAS（Compare-And-Swap）：一种原子操作，用于实现无锁算法

第一步：定义链表节点

我们首先定义一个简单的链表节点结构体。每个节点包含一个值和一个指向下一个节点的指针。

use std::sync::atomic::AtomicPtr;use std::ptr;struct Node {    val: i32,    next: AtomicPtr<Node>,}impl Node {    fn new(val: i32) -> *mut Node {        Box::into_raw(Box::new(Node {            val,            next: AtomicPtr::new(ptr::null_mut()),        }))    }}

注意：我们使用 *mut Node 而不是 Option<Box<Node>>，因为原子操作要求使用原始指针。这是 Rust多线程编程 中常见的技巧。

第二步：实现并发链表结构

接下来，我们定义链表本身，它只保存头节点的原子指针。

use std::sync::atomic::{AtomicPtr, Ordering};pub struct ConcurrentList {    head: AtomicPtr<Node>,}impl ConcurrentList {    pub fn new() -> Self {        ConcurrentList {            head: AtomicPtr::new(ptr::null_mut()),        }    }}

第三步：实现无锁插入操作

插入是并发链表中最关键的操作。我们将使用 CAS（Compare-And-Swap）来确保线程安全。

impl ConcurrentList {    pub fn push(&self, val: i32) {        let new_node = Node::new(val);        loop {            let current_head = self.head.load(Ordering::Relaxed);            unsafe {                (*new_node).next.store(current_head, Ordering::Relaxed);            }            // 尝试将 new_node 设置为新的头节点            if self.head                .compare_exchange_weak(                    current_head,                    new_node,                    Ordering::Release,                    Ordering::Relaxed,                )                .is_ok()            {                break;            }            // 如果 CAS 失败，说明有其他线程修改了 head，重试        }    }}

这里使用了 compare_exchange_weak，它在某些架构上比 compare_exchange_strong 更高效，尤其适合循环重试场景。

第四步：实现查找操作（只读）

查找不需要修改结构，因此相对简单，但仍需注意内存顺序。

impl ConcurrentList {    pub fn contains(&self, val: i32) -> bool {        let mut current = self.head.load(Ordering::Acquire);        while !current.is_null() {            unsafe {                if (*current).val == val {                    return true;                }                current = (*current).next.load(Ordering::Acquire);            }        }        false    }}

第五步：资源清理（高级话题）

上面的实现没有处理内存释放！在真实场景中，你需要使用 Rust内存安全 机制（如 Hazard Pointers 或 Epoch-based Reclamation）来安全回收节点。这超出了本教程范围，但值得你深入研究。

完整测试示例

让我们写一个简单的多线程测试，验证并发插入是否安全：

use std::sync::Arc;use std::thread;fn main() {    let list = Arc::new(ConcurrentList::new());    let mut handles = vec![];    for i in 0..10 {        let list_clone = Arc::clone(&list);        handles.push(thread::spawn(move || {            list_clone.push(i);        }));    }    for handle in handles {        handle.join().unwrap();    }    // 检查所有值是否都被插入    for i in 0..10 {        assert!(list.contains(i));    }    println!("并发插入测试通过！");}

总结

通过本教程，你学会了如何在 Rust 中实现一个基础的 Rust并发链表。虽然我们跳过了内存回收等复杂部分，但核心的无锁插入和查找逻辑已经足够展示 Rust无锁数据结构 的强大能力。掌握这些技巧，将极大提升你在 Rust多线程编程 和 Rust内存安全 领域的实战水平。

下一步建议：尝试实现删除操作，或研究 crossbeam crate 提供的成熟无锁数据结构。