链表的最佳搜索算法

Question

我必须尽可能高效地编写一个程序，将给定的节点插入到已排序的 LinkedList 中。我在想二分搜索在平均和最坏情况下如何比线性更快，但是当我搜索它时，运行时间是 O(nlogn)？我应该在单链表上进行线性搜索还是在双链表上进行二分搜索，为什么那个（选择的）更快？

另外，对于双向链表，二进制搜索算法如何 > O(logn)？（没有人推荐 SkipList，我认为它们违反了规则，因为我们有另一种严格针对该数据结构的实现）

Answer 1

你有两个选择。

1. 线性搜索无序列表。这是 O(N)。
2. 线性搜索有序列表。这也是 O(N) 但它的速度是它的两倍，因为平均而言，您搜索的项目将位于中间，如果找不到，您可以在那里停下来。

您无法选择二进制搜索，因为您无法直接访问链表的元素。

但是，如果您认为搜索是决定速率的步骤，则根本不应该使用链表：您应该使用排序数组、堆、树等。