高效地查找元素是否存在于链接列表中

Question

预设有一个包含信息的链接列表。我的程序体系结构取决于能够找出某个信息是否已存在于此链接列表中的单个节点中。

（即，看看孩子整数值int example已经在某些节点中的值5。）

在此之后，每个节点可以系统上操作。

我可以想出各种方法来做到这一点，但我希望有人更有经验可能会显示相当有效的东西。

此外，这是一个好的做法，还是应该有另一个更合适的数据结构呢？

谢谢！

Answer 1

如果O(N)是不够的，排序数组和二进制搜索，或BST会给你O(log(N))。或者，你可以看看hashmap data structure。这种结构会给你几乎恒定的时间查找基于一个关键，但比其他选项更复杂。问题是那里有is no std library implementation of one。

否则搜索每个元素是最好的，你可以希望做一个链表。