1

我有一个需要快速插入和删除的双链表。我可以在任何一个方向上横穿整个东西来找到插入或移除的位置，但是有没有更聪明的方法来找到插入或移除点？首先想到的是二分搜索，但由于它是一个没有索引的链表（不是数组），我不知道如何在我的链表中跳转。

在这里以最快的速度进行插入和删除的正确方法是什么？

4

3 回答 3

5

聪明的方法是转向跳过列表。

其他方法包括缓存最近的访问并智能猜测从哪里开始搜索，最后，开始或最近的位置。

于 2013-09-13T09:48:36.557 回答
0

您可以使用B 树而不是双链表，或者如其他答案中所述，使用Skip_list。对于快速搜索，双链表是错误的数据结构。

于 2013-09-13T09:59:40.637 回答
-1

正如您自己指出的那样，因为链表不可索引，所以没有办法遍历列表以找到正确的插入点......

于 2013-09-13T09:44:36.350 回答