我必须尽可能高效地编写程序，将给定节点插入到已排序的LinkedList中。我正在考虑二进制搜索在平均和最差情况下如何比线性更快，但是当我用谷歌搜索它时，运行时是O（nlogn）？我应该对双链接列表上的单链接列表或二进制搜索进行线性处理，为什么那个（选择的那个）更快？
另外，对于双重链接列表，二进制搜索算法> O（logn）如何？ （没有人推荐SkipList，我认为他们违反规则，因为我们有严格的数据结构的另一个实现）
你有两个选择。
您无法选择二进制搜索，因为您无法直接访问链接列表的元素。
但是如果你认为搜索是一个速率决定步骤，你根本不应该使用链表：你应该使用一个排序数组，一个堆，一个树等。
二进制搜索在数组上非常快，因为它可以非常快速和简单地访问数组中任意两个给定元素索引之间的中间索引。这使得运行时间复杂度为O（log n），同时占用恒定的O（1）空间。
对于链表，它是不同的，因为为了访问中间元素，我们需要逐个遍历它，因此找到中间节点可以按O（n）的顺序运行
因此，二进制搜索在链表上很慢而在阵列上很快
因此，LL上的二进制搜索基本上是O（n log n），因为您需要遍历列表n次以搜索项目，然后记录n次以拆分搜索的集合。但是，只有每次从头开始遍历LL时才会出现这种情况。
理想情况下，如果你找出一些方法（它可能！）从其他地方开始，比如...搜索集的中间，那么你就不需要总是遍历列表n次以开始搜索并且可以优化你的算法到O（log n）。