我想知道，如果二进制搜索用于排序的链表插入、搜索，它们之间的性能有什么区别吗？以及它们在哪些情况下表现不同，或者可能出于哪些目的，比如说，列表将无法使用，反之亦然。
最佳答案
您不能对链表(单链表或双链表)进行二分查找，因为如果不遍历链表的一半(从一端)就无法到达链表的中间。
毫无疑问，多级跳过列表的一种形式可以做到这一点，但在我看来，这只是模拟具有更复杂结构的二叉树。
一个排序的链表对于搜索、插入和删除往往是 O(n)(实际插入/删除本身是 O(1) 但您仍然必须找到插入或删除点首先)。
或者，二叉树(平衡树)的搜索、插入和删除操作的复杂度为 O(log n)(所有这些操作都与树的高度成正比)。
关于algorithm - 二叉搜索树与排序双向链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17694750/