无锁单写者多reader列表的实现细节

Question

我正在尝试了解在

中找到的单作者多 reader 双 linked 列表的实现

http://web.cecs.pdx.edu/~walpole/class/cs510/papers/11.pdf

pdf 第 10 页（或期刊文章的第 500 页）。

我根本无法理解插入和删除功能是如何工作的

我的理解是

1. 传入一个双指针。内部指针大概是我通常所说的左边的地址link。
2. 出于某种原因，Next 指针（我通常称之为正确 link）被设置为包含在双指针中的地址。
3. 对 (next != null) 的调用让我很困惑，好像 next 是 null 那么指向 Previous 的双指针不提供 link back
4. 节点指针存入双指针。这必须是设置 Previous 节点 Next 指针的机制，因为没有任何其他方法。

我认为我的基本问题归结为双指针中的内部指针指向什么？

如果第 1 行取消引用 Previous 并使用 Previous.Next 分配给 Next 并且如果第 4 行将 next.Prev 设置为具有要插入节点地址的指针，那么事情对我来说可能有意义, 但即便如此，它似乎仍然不正确。

标记 C++ 问题，因为伪代码语法最接近带有一些 Pascal 的 C++。如果这个问题更适合 cs.stackexchange 请重新定位它。

Answer 1

Prev 成员指向前一个节点的 Next 成员，而不是指向前一个节点。这有点奇怪，但也许它节省了一些算术，因为我们在前向遍历期间只查看 Key 成员，并且它不必为列表头分配整个节点。