我不太明白针对哨兵节点的检查如何更快（或者如何在链表或树中正确实现它们），所以我想这更像是一个由两部分组成的问题：
我认为一个小的代码示例比理论讨论更好地解释了问题。
以下是删除双向链表节点的代码，其中使用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;
如您所见，虚拟节点方法为双向链表消除了所有特殊情况和条件判断。
下面的图片表示了同一列表在内存中两种方法的不同实现...
如果只是简单迭代而不查看元素数据，则使用哨兵没有优势。
但是，如果用于“查找”类型的算法，则会有一些真正的收益。例如，假设有一个链接列表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;
x，则会自动返回end()。std::sort实现中使用的排序算法。它有一种很酷的分割算法变体，使用哨兵来消除一些分支。find()会改变数据结构的想法，比如说使用find时的规则是禁止从多个线程中访问，即使所有线程只是在搜索元素。 - 6502end同样可以是一个空指针。因此它并没有回答这个问题。 - n. m.你的问题 (1) 的答案在链接维基百科条目的最后一句话中："由于通常连接到NULL的节点现在连接到“nil”（包括nil本身），因此它消除了检查NULL所需的昂贵分支操作。"
通常需要在访问节点之前测试其是否为NULL。如果有一个有效的 nil 节点，那么您就不需要进行这个测试，从而节省比较和条件分支，否则在现代超标量CPU上，分支预测错误时开销是很大的。
我将尝试在标准模板库的上下文中回答：
1）在调用“next（）”时，NULL并不一定表示列表结束。如果发生内存错误怎么办？返回一个哨兵节点是明确指示列表结束而不是其他结果的方法。换句话说，NULL可能表示各种各样的事情，而不仅仅是列表结束。
2）这只是一种可能的方法：当您创建列表时，请创建一个私有节点，该节点不与类外共享（例如称为“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;
}
首先，让我们搁置哨兵。就代码复杂度而言，在ltjax的答案中，他为我们提供了以下代码
for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
if (*i == x) // second branch here
return i;
}
return list.end();
代码可以更好地编写为：
auto iter = list.begin();
while(iter != list.end() && *iter != x)
++iter;
return iter;
由于循环终止条件的混乱（分组），当通过循环体进行正确性推理时，可以轻松地看到循环终止条件，而无需记住所有循环终止条件，并且输入更少。但要注意这里的布尔电路。
关键是这里使用的哨兵不是为了减少代码复杂性，而是帮助我们在每个循环中减少索引检查。对于线性搜索，我们从检查索引是否在有效范围内开始，如果在，则检查值是否为所需值，而不使用哨兵。但是，使用放置在末尾的期望值的哨兵，我们可以省去索引边界检查，仅检查值，因为循环保证终止。这属于哨兵控制的循环：重复直到看到所需值。
推荐阅读：《算法导论》第三版，如果您有PDF格式，请搜索关键字“哨兵”以获取全部内容。实际上，这个例子非常简洁和有趣。如何狩猎大象和开罗象可能会引起您的兴趣。当然，我并不是在谈论真正的狩猎大象。
std::list 只会产生误导。这不是 std::list 允许操作的方式。如果你需要最佳性能，有一个更好的选择：首先不要使用链表。 - n. m.特别是在使用哨兵的情况下，如果侵入式列表是一个重要的可能性，那么列表元素可以在不知道它所属的列表的情况下将自己从列表中移除。该元素只需从循环链中删除即可。哨兵元素始终保留在那里，因此不存在列表指向不再存在于列表中的元素的可能性。