Is there a known implementation of an indexed linked list?

Question

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

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."

Answer 1

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

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

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.