Implementation detail of lock-free single-writer multi-reader list

Question

I am attempting to understand the implementation of the single-writer multi-reader doubly linked list found in

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

on page 10 of the pdf (or 500 of the journal article).

I simply cannot understand how the Insert and Delete functionality is working

My understanding of it is

1. A double pointer is passed in. The inner pointer is presumably the address of what I would normally call the left link.
2. For some reason the Next pointer (what I would normally call right link) is set to the address contained in the double pointer.
3. The call to (next != null) has me very confused, as if next was null then the double pointer to Previous doesn't provide a link back
4. The node pointer is stored into the double pointer. This must be the mechanism where the Previous nodes Next pointer is set as there isn't any other method.

I think my basic question comes down to what does the inner pointer in the double pointer point to?

Things might would make sense to me if line 1 dereference Previous and used Previous.Next to assign to Next AND if line 4 had set next.Prev to a pointer with address of the to be inserted node, but even then it still seems incorrect.

Tagging the question C++ since the pseudo-code syntax is closest to C++ with some Pascal. If this question is better suited to the cs.stackexchange please relocate it.

Answer 1

Instead of pointing to the previous node, the Prev member points to the Next member of the previous node. It's a bit strange, but perhaps it saves some arithmetic, since we only look at the Key member during forward traversals, and it saves having to allocate a whole node for the list head.