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

Question

我正在尝试了解中的单写多读双链表的实现

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

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

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

我对它的理解是

1. 传入了一个双指针。内部指针大概是我通常称之为左链接的地址
2. 由于某种原因，下一个指针（我通常称之为右链接）被设置为双指针中包含的地址
3. 对（next！=null）的调用让我非常困惑，就好像next为null，那么指向Previous的双指针就没有提供返回的链接
4. 节点指针存储在双指针中。这必须是设置Previous节点Next指针的机制，因为没有任何其他方法

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

如果第1行取消引用Previous并使用Previous.Next来分配给Next，如果第4行设置了Next，这对我来说可能是有意义的。Previ指向一个指针，该指针具有要插入的节点的地址，但即便如此，它似乎仍然不正确。

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

Answer 1

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