c - 有效地查找元素是否存在于链表中

Question

假设有一个包含信息的链表。我的程序架构依赖于能够查明某些信息是否已经存在于此链接列表中的单个节点中。

（即，查看子整数值int example是否在某个节点中已经具有值 5。）

之后，就可以对每个节点进行系统的操作了。

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

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

谢谢！

Answer 1

如果O(N)还不够，排序数组和二进制搜索，或者BST会给你O(log(N)). 或者，您可以查看hashmap 数据结构。这种结构将为您提供基于键的几乎恒定的时间查找，但比其他选项更复杂。问题是没有 std 库实现 one。

否则，搜索每个元素是您希望使用链表做的最好的事情。