代码之家 › 专栏 › 技术社区 › JohnPristine

Java排序的双链表:如何在正确的位置快速插入新节点?

doubly-linked-list binary-search linked-list algorithm java

JohnPristine · 技术社区 · 11 年前

我有一个需要快速插入和删除的双重链接列表。我可以在任何一个方向横向移动整个东西,找到插入或移除的位置,但是 有没有更聪明的方法可以找到插入点或移除点 ? 首先想到的是二进制搜索,但由于它是一个没有索引的链表(不是数组),我不知道如何在链表中跳转。

这里的正确方法是什么,可以使插入和删除最快?

3 回复 | 直到 11 年前

OldCurmudgeon 11 年前

明智的方法是朝着 Skip List .

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

MrSmith42 11 年前

您可以使用 B-tree 使用一个 Skip_list 对于快速搜索来说,双链表是错误的数据结构。

-1

GerritCap 11 年前

正如你所指出的,因为链表是不可索引的,所以没有办法,只能在列表上循环以找到正确的插入点。。。

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Laveen · python中的二进制搜索程序不会停止循环

7 年前

MEnnabah · 高效实现二进制搜索

7 年前

Tanay Choudhary · 如何为这个二进制搜索函数创建具有修改的最大/最小值的新数组

7 年前

user8742308 · 如果指定的数字位于排序数组的末尾或开头,则二进制搜索函数无法找到它们

7 年前

James Chavez · 二进制搜索查找不重复java的元素

7 年前

yrrah2 · 为什么我的二进制搜索使用这么多比较?

7 年前

James · 阻塞问题的一种算法设计[C++代码]

7 年前

Artemis · 为什么在二进制搜索中我们要除以2而不是其他更高的常数

7 年前

Johnny · 二进制搜索是贪婪算法吗?

7 年前