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

在Sentinel Node维基百科页面上，它指出了一个超过NULL的哨兵节点的好处是：

• 运营速度加快
• 减lessalgorithm代码大小
• 增加了数据结构的鲁棒性（可以说）。

我真的不明白如何对前哨节点的检查会更快（或如何正确地实现它们在一个链表或树），所以我想这是更多的两个部分的问题：

1. 什么导致哨兵节点比NULL更好的devise？
2. 你将如何实现（例如）列表中的哨兵节点？

Answer 1

如果你只是做简单的迭代而不是在元素中查看数据，那么哨兵没有任何优势。

但是，将其用于“查找”types的algorithm时有一些真正的收获。 例如，想象一个链表列表std::list ，你想要find一个特定的值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; 

您看到没有必要额外的分支来testing列表的末尾 – 值总是保证在那里，所以如果在“有效”元素中找不到x ，您将自动返回end() 。

对于另一个很酷且实用的标记应用程序，请参见“intro-sort”，它是大多数std::sort实现中使用的sortingalgorithm。 它有一个很酷的分区algorithm变种，它使用标记去除一些分支。

Answer 2

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

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

正如你所看到的虚拟节点的方法删除了一个双向链表的所有特殊情况和所有条件。

下面的图片展示了内存中同一列表的两种方法。

Answer 3

您的问题（1）的答案在链接的Wikipedia条目的最后一句中： “由于通常链接到NULL的节点现在链接到”nil“（包括nil本身），因此不需要昂贵的分支操作检查NULL“。

通常你需要在访问它之前testing一个节点的空值。 如果你有一个有效的无节点，那么你不需要做这个第一个testing，保存一个比较和一个条件分支，否则在错误预测分支时，现代超标量CPU可能会花费很多。

Answer 4

我将尝试在标准模板库的环境中回答：

1）在对“next（）”的调用中，NULL不一定表示列表结束。 如果发生内存错误怎么办？ 返回一个哨兵节点，是一个明确的方式来表明列表已经发生，而不是其他的结果。 换句话说，NULL可以指示各种各样的事情，而不仅仅是列表的结束。

2）这只是一个可能的方法：当你创build你的列表时，创build一个不在该类之外共享的私有节点（比如叫做“lastNode”）。 在检测到你已经迭代到列表的末尾时，让“next（）”返回对“lastNode”的引用。 还有一个叫做“end（）”的方法返回对“lastNode”的引用。 最后，根据你如何实现你的类，你可能需要重写比较运算符才能正常工作。

例：

 class MyNode{ }; class MyList{ public: MyList () : lastNode(); MyNode * next(){ if (isLastNode) return &lastNode; else return //whatever comes next } MyNode * end() { return &lastNode; } //comparison operator friend bool operator == (MyNode &n1, MyNode &n2){ return (&n1 == &n2); //check that both operands point to same memory } private: MyNode lastNode; }; int main(){ MyList list; MyNode * node = list.next(); while ( node != list.end() ){ //do stuff! node = list.next(); } return 0; }