C++如何实现一个简单的无锁单向链表数据结构(基于原子操作)-C++-PHP中文网

不能直接用 std::atomic 操作链表节点指针，因其仅原子读写指针本身，无法解决 aba 问题和内存提前释放导致的未定义行为，需配合内存序与安全回收机制（如 hazard pointer）或接受泄漏式实现。

c++如何实现一个简单的无锁单向链表数据结构(基于原子操作)

为什么不能直接用 `std::atomic<t></t>` 操作链表节点指针

因为 std::atomic<t></t> 只能原子地读写指针本身，但插入或删除节点时往往需要「读取当前头指针 → 计算新节点地址 → 写回新头指针」三步，这构成典型的 ABA 问题温床：中间若被其他线程修改又改回原值，compare_exchange_weak 会误判成功。更关键的是，单纯原子指针无法保证节点内存不被提前释放——比如某线程刚读到旧头节点，另一线程已将其 delete，此时解引用就是未定义行为。

所以必须配合内存序控制 + 安全内存回收机制（如 HP — Hazard Pointer），但「简单无锁链表」通常默认只实现逻辑正确插入/查找，暂不处理内存回收。这意味着：你得自己确保所有节点生命周期长于任何可能的并发访问，或者接受「泄漏式」实现（开发/测试可用，生产慎用）。

插入操作必须用 `compare_exchange_weak` 循环重试

单向链表头插是最易实现的无锁操作，核心是用 CAS 原子更新头指针。但不能只调用一次 compare_exchange_weak 就完事——失败后必须重新读取最新头指针，再构造新节点，否则会丢失并发修改。

next 字段必须声明为 std::atomic<node></node>（而非裸指针），否则其他线程看到的可能是未完全写入的指针值
插入前需对新节点的 next 字段先写入当前头指针，且该写入需用 memory_order_relaxed 即可（因后续 CAS 会带更强序）
CAS 使用 memory_order_acq_rel：既保证之前写操作对其他线程可见，也保证之后读操作能看到其他线程的写结果

struct Node {
    int data;
    std::atomic<node> next{nullptr};
};
<p>class LockFreeSinglyList {
std::atomic<node>> head{nullptr};
public:
void push(int val) {
Node newNode = new Node{val, nullptr};
Node* oldHead = head.load(std::memory_order_acquire);
do {
newNode->next.store(oldHead, std::memory_order_relaxed);
} while (!head.compare_exchange_weak(oldHead, newNode,
std::memory_order_acq_rel,
std::memory_order_acquire));
}
};</node></p></node>

查找操作可以只用 `load(memory_order_acquire)`

查找不修改结构，只需遍历。只要每个 next 读取都用 memory_order_acquire，就能保证看到该节点创建时所写的全部内容（如 data），不会读到撕裂值。注意：这里不涉及修改，所以无需 CAS，也不怕 ABA。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

不能用 memory_order_relaxed 读 next，否则可能看到陈旧的 data 值（编译器/CPU 重排导致读 data 在读 next 之前）
遍历时要检查指针非空，且每次读 next 都需独立 load，不能缓存局部变量后反复用（除非加 volatile 或显式 reload）

bool find(int val) const {
    Node* curr = head.load(std::memory_order_acquire);
    while (curr != nullptr) {
        if (curr->data == val) return true;
        curr = curr->next.load(std::memory_order_acquire);
    }
    return false;
}

删除操作在「简单实现」里几乎必然引入竞态或内存错误

真正安全的无锁删除必须解决两个问题：如何原子地标记节点为「已删除」、如何安全回收内存。简易版本常跳过标记步骤，直接 CAS 头指针，但这仅对头节点有效，且仍需处理 ABA 和释放时机。

如果你真要支持任意节点删除，就绕不开 HP 或 RCU；而若只删头节点，仍需注意：compare_exchange_weak 成功后，旧头节点可能正被其他线程遍历，立刻 delete 会导致 use-after-free。所以「简单」实现中，要么禁止删除（只 push/find），要么明确文档说明：调用 pop() 后用户需自行保证无人再访问返回节点。