使用双向链表的哨兵方法

Question

我正在浏览 Java 中的双向链表，我正在阅读 Book 中双向链表中的 Sentinels。其中指出

In order to avoid some special cases when operating near the boundaries of a doubly-linked list, it helps to add special nodes at both ends of the list: a header node at the beginning of the list, and a trailer node at the end of the list. These “dummy” nodes are known as sentinels (or guards), and they do not store elements of the primary sequence

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

Answer 1

Wikipedia 注释简要提到使用哨兵节点来简化链表的实现。

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

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

我们也不必担心更新头指针和尾指针，因为正如我们将看到的，如果我们在哨兵节点之后插入，这会自动发生，因此将一个项目添加到列表中，或者在哨兵节点之前插入节点，因此将一个项目附加到列表中。

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

但是数据结构一般都会设计一个容器对象，作为数据结构的使用者和数据结构的实现之间的沟通中介，所以我们会保留容器对象。

@6502 在 How does a sentinel node offer benefits over NULL? 上的回答非常有帮助。

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

// 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 == &dummy 表示在最后位置插入）代码为：

// 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;

如您所见，为双向链表删除了所有特殊情况和所有条件的虚拟节点方法。

使用双向链表的哨兵方法

Sentinel approach with Doubly Linked List

java

linked-list

doubly-linked-list