是否已知索引链表的实现？ [英] 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我曾经实现的解决方案是2D List。我的意思是：
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），余额是正确的。在纯数组解决方案中，lookup是 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).
2D列表两者都是 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屋！
