前哨节点如何提供优于NULL的优势？

Question

在Sentinel Node维基百科页面上,它表明Sentinel节点优于NULL的好处是:

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

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

1. 是什么导致Sentinel节点比NULL更好的设计？
2. 你如何在(例如)列表中实现一个sentinel节点？

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;

节点插入也存在同样的简化; 例如,在节点n之前插入节点x(具有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;

正如您所看到的,对于双向链接列表,所有特殊情况和所有条件都删除了虚节点方法.

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

Answer 2

如果你只是进行简单的迭代而不是查看元素中的数据,那么哨兵就没有优势了.

但是,将它用于"查找"类型算法时会有一些实际的好处.例如,想象一下std::list您要查找特定值的链接列表x.

没有哨兵你会做的是:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

但是对于哨兵(当然,结尾实际上必须是一个真正的节点......):

iterator i=list.begin();
*list.end() = x;

while (*i != x) // just this branch!
  ++i;

return i;

您看到不需要额外的分支来测试列表的末尾 - 值始终保证在那里,因此end()如果x在"有效"元素中找不到,则会自动返回.

对于另一个很酷且实际上有用的哨兵应用,请参阅"intro-sort",这是在大多数std::sort实现中使用的排序算法.它有一个很酷的分区算法变体,它使用标记来删除一些分支.

Answer 3

您的问题(1)的答案在链接的维基百科条目的最后一句中:"由于通常链接到NULL的节点现在链接到"nil"(包括nil本身),它消除了对昂贵的分支操作的需要检查是否为NULL."

通常,您需要在访问节点之前测试其为NULL.相反,如果您有一个有效的nil节点,那么您不需要进行第一次测试,保存比较和条件分支,否则当分支被错误预测时,现在的超标量CPU可能会很昂贵.