c++ - 哨兵节点如何提供优于 NULL 的好处？

Question

在 Sentinel Node wikipedia page它说哨兵节点优于 NULL 的好处是:

• 提高操作速度
• 减少算法代码大小
• 提高了数据结构的稳健性(可以说)。

我真的不明白对哨兵节点的检查如何更快(或如何在链表或树中正确实现它们)，所以我想这更多是一个两部分的问题:

1. 是什么导致哨兵节点的设计比 NULL 更好？
2. 您将如何在(例如)列表中实现哨兵节点？

Answer 1

我认为一个小代码示例会比理论上的讨论更好。

以下是在节点的双向链表中删除节点的代码，其中 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;

这是相同的代码，其中有一个特殊的虚拟节点来标记列表的末尾，并且列表中第一个节点的地址存储在特殊的 next 字段中节点和列表中的最后一个节点存储在特殊虚拟节点的 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;

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

下图表示内存中同一个列表的两种方法...