双链表哨兵法

Question

我正在浏览Java中的双链接列表，我正在阅读来自书的双链接列表中的哨兵信息。上面说

为了避免在双链接列表边界附近操作的特殊情况，它有助于在列表的两端添加特殊节点:列表开头的头节点和列表末尾的预告片节点。这些“虚拟”节点被称为哨兵(或守卫)，它们不存储主序列的元素。

那些特殊情况是什么？为什么我们需要哨兵进场？这是强制性的吗？如果我们对双链接列表使用正常的方法(没有前哨)，这难道不节省这些额外节点的内存吗？当用循环的方法制作双链接列表时，我们必须删除哨兵吗？

Answer 1

维基百科简要地提到使用一个哨位节点来简化链表的实现。

前哨节点是位于列表前面的虚拟节点。

在双链接列表中，哨兵节点指向列表的第一个和最后一个元素。我们不再需要为列表的头和尾保留单独的指针，就像我们对单链接列表所做的那样。

我们也不必担心更新头和尾指针，因为正如我们所看到的，如果我们在一个哨兵节点之后插入，从而在列表中预先加上一个项，或者在一个哨兵节点之前插入，那么就会自动发生这种情况，从而将一个项追加到列表中。

我们可以消除用于单链接列表的容器对象，因为哨兵节点可以跟踪列表中的第一个和最后一个元素。如果这样做，那么我们将把指向哨兵节点的指针返回给用户。

然而，数据结构通常是用一个容器对象来设计的，该容器对象可以协调数据结构的用户与数据结构的实现之间的通信，因此我们将保留容器对象。

@6502在哨兵节点如何提供比NULL更多的好处？上的回答是非常有用的。

以下是节点双链接列表中的节点删除代码，其中NULL用于标记列表的结束，其中两个指针首先和最后两个指针用于保存第一个和最后一个节点的地址：

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

这是相同的代码，其中有一个特殊的虚拟节点来标记列表的结束，其中列表中第一个节点的地址存储在特殊节点的下一个字段中，其中列表中的最后一个节点存储在特殊虚拟节点的prev字段中：

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

对于节点插入也存在同样的简化；例如，在节点x之前插入节点n(具有x == NULL或x == &在最后位置插入虚拟含义)，代码如下：

// Using NULL and pointers for first and last

n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

和

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

如您所见，对于双链接列表，所有特殊情况和所有条件都删除了虚拟节点方法。