algorithm - binary search tree vs sorted doubly linked list

Question

I'm wondering, is there any difference between performance of those, provided binary search is used for sorted linked list insertion, search. And in which situations they perform differently or maybe for which purposes, say, list will be unusable or vice versa.

Answer 1

您不能对链表（单或双）进行二分搜索，因为如果不遍历链表的一半（从一端），就无法到达链表的中间。

毫无疑问，一种多级跳过列表可以做到这一点，但在我看来，这只是模拟具有更复杂结构的二叉树。

排序链表的搜索、插入和删除往往是 O(n)（实际插入/删除本身是 O(1)，但您仍然必须先找到插入或删除点）。

或者，二叉树（平衡树）是 O(log n) 的搜索、插入和删除（所有这些操作都与树的高度成正比）。