消除搜索链表中的 NULL 检查

Question

如何在搜索链表的 while 循环的每次迭代中消除 NULL 检查？

Answer 1

您可以使用哨兵元素 - 附加您搜索的元素。如果您发现哨兵返回未找到;在这两种情况下都删除哨兵。

添加：

请参阅Sentinel搜索示例;我对语言表示歉意。我想起了N. Wirth的"Algorithmen und Datenstrukturen"中的策略;我为语言道歉。

Answer 2

你根本做不到。

只要您正在迭代任何数据结构，您总是希望您的算法在到达结构的末尾时以不同的方式运行，因此需要任何类型的检查。无论您的数据结构是什么，都是如此，并且不依赖于您正在迭代的"方式"：for（int i = 0 ;i ;++i）， for（iterator it = myList.begin（） ;它！= mylist.end（）;it++）， while（currentNode.hasChildren（））， while（javaIterator.hasNext（）） ...

尽管如此，无论您的循环做什么，检查可访问对象是否为 NULL 永远不会成为算法的瓶颈。甚至很难减少耗时...

您可能避免检查的唯一方法是避免循环本身，因此在循环中编写每个步骤，但它要求您在编译时知道链表的大小，在这种情况下，您的编译器可能比您自己更好地优化了您的代码;-）

Answer 3

您可以使用循环（循环）链表，其中最后一个元素与第一个元素链接。

Answer 4

您可以跟踪列表中的元素数量。如果您始终知道列表中有多少元素以及您当前所处的位置，那么当您要前进到下一个元素时，无需检查NULL。