детали Реализации безблокировочный одного писателя список мульти-ридер

Question

Я пытаюсь понять осуществление одного писателя мульти-ридер двусвязному список найден в

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

на странице 10 из pdf (или 500 статей журнала).

Я просто не могу понять, как вставлять и удалять функциональность работает

Мое понимание этого является

1. Двойной указатель передается в. Внутреннего указатель предположительно адрес, что я бы нормально вызовите левую ссылку.
2. По какой-то причине указатель Next (как правило, я бы назвал нужную ссылку) был установлен на адрес, содержащийся в двойном указателе.
3. Звонок на (next! = Null) меня очень смутил, как если бы следующий был пустым, то двойной указатель на предыдущий не предоставляет ссылку назад
4. Указатель узла хранится в двойном указателе. Это должен быть механизм, в котором предыдущие узлы Следующий указатель задан как нет другого метода.

Я думаю, что мой основной вопрос сводится к тому, что указывает внутренний указатель в точке двойного указателя?

Для меня может возникнуть смысл, если строка 1 разыменовывается Предыдущая и использованная Previous.Next назначить Next AND, если строка 4 была установлена ​​next.Prev указателю с адресом вставленного узла, но даже тогда все еще кажется неправильным.

Пометка вопроса C++, поскольку синтаксис псевдокода ближе всего к C++ с некоторым Pascal. Если этот вопрос лучше подходит для cs.stackexchange, пожалуйста, переместите его.

Answer 1

Вместо того, чтобы указывать на предыдущий узел, член Prev указывает на член Next предыдущего узла. Это немного странно, но, возможно, это экономит некоторую арифметику, поскольку мы рассматриваем только элемент Key во время прямых обходов, и это экономит необходимость выделения целого узла для заголовка списка.