是否已知索引链表的实现？

Question

我的直觉告诉我没有好办法实现这一目标,但是,与Stephen Colbert先生不同,我宁愿相信一个开发者社区而不是我的直觉......

有没有一种已知的方法来有效地实现"两个世界中最好的"列表,一个通过索引提供随机访问并且像链接列表一样提供O(1)插入/删除？

我预见到两种可能的结果:要么"不,这是不可能的,出于以下明显的原因......"或"呃,是的,这已经完成了;请看这里,这里和这里."

Answer 1

我不相信O(1)插入和查找都是可能的.添加数组(甚至是花哨的,可分割的向量)的那一刻,插入就变成了O(n).

有一些方法可以根据列表的预期行为来减轻损害.如果将有比插入/删除更多的查找,那么使用向量(可变大小的数组)可能更好 - 这些是相当有效的,不像数组,但比遍历列表更好(因为这些往往是列表对于数组而言,它仍然在技术上遍历列表,但列表中的每个元素通常都有其大小,这使得它更有效率.

如果插入和删除更频繁,您可以使索引构建为惰性索引,以便仅在需要时才进行.例如,插入和删除只会更改链接列表部分(并将索引标记为脏) - 只有当有人尝试使用索引时,才会重建并标记为干净.

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

我曾经实现过的解决方案是2D List.通过这个,我的意思是:

        +-----------+    +-----------+    +-----------+
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)于两者但具有较低因子.如果您要插入,只需检查每列的第一行即可找到正确的列.然后你遍历列本身寻找正确的行.然后插入该项目并增加该列的计数.类似地,对于删除,尽管在那种情况下计数减少,并且当其计数达到零时移除整个列.

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

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