是否存在索引链接列表的已知实现?

我不相信 O(1) 用于插入和查找。当你添加一个数组(甚至是花哨的可分割向量)时,插入就变成了 O(n) .

有几种方法可以减轻损害,具体取决于您列表中的预期行为。如果查找的次数要比插入/删除的次数多得多,那么只使用向量(可变大小的数组)可能会更好——这些向量效率相当高,与数组不同,但比遍历列表要好(因为这些向量往往是数组列表,所以从技术上讲,它仍在遍历列表,但列表中的每个元素通常都有其大小,这使得效率更高)。

如果插入和删除更频繁,您可以使索引构建一个懒惰的索引,这样它只在需要时完成。例如,插入和删除只会更改链接列表部分(并将索引标记为脏的)-只有当有人试图使用索引时,才会重新生成该索引并将其标记为干净。

您甚至可以通过保存第一个脏条目的记录来优化重建。这意味着,如果只在列表的后半部分中插入或删除,则当有人想要使用整个索引时,不需要重新构建它。

我曾经实现的一个解决方案是一个二维列表。我的意思是:

        +-----------+    +-----------+    +-----------+
List -> | count = 7 | -> | Count = 4 | -> | Count = 6 | -> null
        +-----------+    +-----------+    +-----------+
              |                |                |
              V                V                V
        +-----------+    +-----------+    +-----------+
        |    [0]    |    |    [7]    |    |   [11]    |
        +-----------+    +-----------+    +-----------+
              |                |                |
              V                V                V
        +-----------+    +-----------+    +-----------+
        |    [1]    |    |    [8]    |    |   [12]    |
        +-----------+    +-----------+    +-----------+
              |                |                |
              :                :                :
              :                :                :
              |                |                |
              V                V                V
        +-----------+    +-----------+    +-----------+
        |    [6]    |    |   [10]    |    |   [16]    |
        +-----------+    +-----------+    +-----------+
              |                |                |
              V                V                V
             null             null             null

虽然这使得插入和查找都是O(N),但平衡是正确的。在纯数组解决方案中,查找是 O(1) 插入是 o(n) . 对于纯链接列表,插入是 O(1) (当然,一旦找到了插入点,操作本身就是 o(n) 和查找是 o(n) .

2D列表是 o(n) 两者都有,但系数较低。如果要插入,只需检查每列的第一行即可找到正确的列。然后遍历列本身,查找正确的行。然后插入该项并增加该列的计数。同样,对于删除,尽管在这种情况下,计数会减少,并且当其计数达到零时,整个列将被删除。

对于索引查找,可以遍历列以查找正确的列,然后遍历列中的项以获取正确的项。

而且,它甚至可以通过尝试保持最大高度和宽度大致相同来自动调整。

如果你认为 O(log N) == O(1) ,
退房:

• Red-black tree ,o(logn),每次操作
• Skip list ,o(logn),每次操作

在类中实现链接列表时,我考虑通过存储3个附加字段来优化访问时间:列表中间的节点、最近访问的节点的索引和最近访问的节点本身。

为了按索引检索一个节点,我首先查看所有可用的路径,以到达给定索引处的节点,然后选择最便宜的方法。方法很简单:

1. 从开始到所需的索引
2. 从最近访问的节点转到所需索引(转发)
3. 从最近访问的节点转到所需索引(向后)
4. 从中间节点转到所需索引(向前)
5. 从中间节点转到所需索引(向后)
6. 从节点的末尾到所需索引

我们期望的指数和起始指数差异最小的路径是最便宜的选择。如果尚未访问任何节点,则可以将最近访问的节点设置为中间节点。当然,对于偶数元素,没有实际的中间部分,所以我只选择n/2的楼层。

不管怎样,我从未真正实现过这种优化,甚至 真的? 分析一下,但我希望我能帮上忙。

你的直觉是正确的。

链接列表是O(1)插入/删除,因为您执行的插入或删除某个内容的操作只是切换几个指针(一个或两个指针位于要插入的对象上,一个或两个指针位于其他一个或两个对象上)。显然,这不会随列表的大小而改变。

跳过列表将为您提供O(logn)查找,但由于您要维护索引,它还意味着O(logn)插入/删除,因为该索引需要保持最新。

您用于查找的任何并行数据结构都需要维护,因此您的复杂性将根据索引的复杂性进行扩展。

你有什么特别的问题要解决吗?

例如,如果可以保证一个完美的哈希值,那么您可以获得O(N)插入、删除和查找。但是你需要提前知道一些关于你的数据的事情,这样才能工作。

哈希表怎么样?您可以通过键获得O(1)随机访问和O(1)插入/删除。关键是条目无序。

为了有效地实现有序序列,请检查 finger trees . 他们让你有机会 head 和 last O(log n)随机访问内部节点。在O(1)的任一端插入或删除。值得注意的是,手指树的反转需要恒定的时间。

我不知道插入时的确切Bigo(因为根据样本大小和增长而变化),但是Java java.util.LinkedList 会立刻想到的。

http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html

编辑:是的,显然在它下面仍然是一个真正的链表,因此索引的gets可以是o(n/2),这当然是形式上的o(n)。

您可以一直浪费大量的空间,并实现一个列表实现,该实现保留一个带有延迟插入/删除的并行链接列表和数组。

虽然我认为您不能获得整数索引,但是如果您使用的是“引用”类型,支持哈希表可能会工作。

爪哇 LinkedList 对索引获取具有O(N)访问权限。 链表 延伸 AbstractSequentialList 以显示它不提供O(1)索引获取。

我建议你看看 Apache's TreeList . 它提供O(log n)插入/删除和O(1)索引查找。