哨兵节点如何提供优于 NULL 的好处?

问题描述

在 哨兵节点维基百科页面上，它说哨兵节点相对于 NULL 的好处是:

On the Sentinel Node wikipedia page it says that the benefits of a sentinel node over NULL are :

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

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

I don't really understand how the checks against a sentinel node would be faster (or how to properly implement them in a linked list or tree), so I suppose this is more of a two part question:

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

推荐答案

如果您只是进行简单的迭代而不查看元素中的数据，那么使用哨兵就没有任何优势.

There's no advantage with sentinels if you're just doing simple iteration and not looking at the data in the elements.

但是，将其用于查找"类型算法时会获得一些实际收益.例如，想象一个链表列表 std::list，您想在其中查找特定值 x.

However, there's some real gain when using it for "find" type algorithms. For example, imagine a linked list list std::list where you want to find a specific value x.

没有哨兵你会做什么:

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

但是有了哨兵(当然，end 实际上必须是一个真正的节点……):

But with sentinels (of course, end actually has to be a real node for this...):

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

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

return i;

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