language-agnostic - 有索引链表的已知实现吗？

Question

我的直觉告诉我，没有什么好方法可以实现这一目标，但是与Stephen Colbert先生不同，我更愿意信任一个开发人员社区，而不是我的直觉。

有没有一种已知的方法可以有效地实现“两全其美”列表，该列表可以像链表一样通过索引和O（1）插入/删除提供随机访问？

我预见了两种可能的结果：“不，出于以下明显的原因，这是不可能的……”或“嗯，是的，这已经完成；请在此处，此处和此处查看。”

Answer 1

我认为插入和查找都不可能得到O(1)。添加数组（甚至是漂亮的可拆分向量）的那一刻，插入将变为O(n)。

有多种方法可以减轻损坏，具体取决于列表的预期行为。如果查找的次数比插入/删除的次数多，则最好使用向量（可变大小的数组）-它们的效率较高，虽然不像数组，但比遍历列表更好（因为它们通常是列表）数组，但从技术上讲，它仍在遍历列表，但列表中的每个元素通常都有其大小，这使其效率更高）。

如果插入和删除操作更为频繁，则可以使索引建立一个惰性索引，以便仅在需要时才执行。例如，插入和删除将仅更改链接列表部分（并将索引标记为脏）-仅当有人尝试使用索引时，它才会被重建并标记为干净。

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

我曾经实现的一个解决方案是2D列表。我的意思是：

        +-----------+    +-----------+    +-----------+
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)，但系数较低。如果要插入，只需检查每列的第一行即可找到合适的列。然后，您遍历该列本身以查找右行。然后插入该项目，并增加该列的计数。与删除操作类似，尽管在这种情况下计数会减少，并且当计数达到零时会删除整个列。

对于索引查找，您遍历各列以找到正确的列，然后遍历该列中的项以获取正确的项。

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