是否有索引链表的已知实现? [英] Is there a known implementation of an indexed linked list?

问题描述

我的直觉告诉我没有好的方法可以实现这一目标，但是，与 Stephen Colbert 先生不同的是，我宁愿相信开发人员社区而不是我的直觉......

My gut tells me there is no good way to achieve this, but, unlike Mr. Stephen Colbert, I'd rather trust a community of developers than my gut...

是否有一种已知的方法可以有效地实现两全其美"列表，该列表通过索引和像链表一样提供 O(1) 插入/删除的随机访问?

Is there a known way to efficiently implement a "best of both worlds" list, one that provides random access by index and O(1) insertion/removal like a linked list?

我预见了两种可能的结果:不，这是不可能的，原因如下……"或嗯，是的，这已经完成了；见这里、这里和这里."

I foresee two possible outcomes: either "No, this is impossible, for the following obvious reasons..." or "Uh, yes, this has been done; see here, here, and here."

推荐答案

我认为插入和查找都不可能获得 O(1).一旦你添加了一个数组(甚至是花哨的、可拆分的向量)，插入就变成了 O(n).

I don't believe it will be possible to get O(1) for both insertion and lookup. The minute you add an array (or even fancy, splittable vectors), the insertion becomes O(n).

根据列表的预期行为，有多种方法可以减轻损害.如果查找比插入/删除要多得多，那么只使用向量(可变大小的数组)可能会更好 - 这些是相当有效的，不太像数组，但比遍历列表要好(因为这些往往是列表数组，从技术上讲它仍然是遍历一个列表，但是列表中的每个元素通常都有自己的大小，这使得它更高效).

There are ways to mitigate the damage depending on the expected behavior of your list. If there will be a lot more lookups than insertions/deletions, it may be better to just use vectors (variable-sized arrays) - these are reasonably efficient, not quite like arrays, but better than traversing lists (since these tend to be lists of arrays, it's still technically traversing a list, but each element in the list typically has its size, which makes it more efficient).

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

If insertions and deletions are more frequent, you can make the index build a lazy one so that it's only done when required. For example, inserts and deletes will only change the linked list portion (and mark the index as dirty) - only when someone tries to use the index will it be rebuilt and marked as clean.

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

You can even optimize the rebuild by keeping a record of the first dirty entry. This will mean if you only insert or delete in the last half of the list, you don't need to rebuild the entire index when someone wants to use it.

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

A solution I once implemented was a 2D List. By this, I mean:

        +-----------+    +-----------+    +-----------+
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).

While this made both insertion and lookup O(n), the balance was right. In a pure array solution, lookup is O(1) and insertion is O(n). For a pure linked list, insertion is O(1) (once you've found the insertion point, of course, an operation that is itself O(n)) and lookup is O(n).

二维列表对于两者都是O(n)，但因子较低.如果您要插入，只需检查每列的第一行即可找到正确的列.然后你遍历列本身寻找正确的行.然后插入该项目并增加该列的计数.类似的删除操作，尽管在这种情况下计数会减少，并且当其计数为零时整列将被删除.

The 2D list is O(n) for both but with a lower factor. If you're looking to insert, you can find the right column simply by examining the first row of each column. Then you traverse the column itself looking for the right row. Then the item is inserted and the count for that column is increased. Similarly for deletions although in that case the count is decreased, and the entire column is removed when its count reaches zero.

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

For an index lookup, you traverse the columns to find the correct column, then traverse the items in the column to get the right item.

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

And, it can even be auto-adjusting by trying to keep the maximum height and width roughly the same.

这篇关于是否有索引链表的已知实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！