What is the best data structure (container) for fast element insertion/deletion by index?

Question

What is the best data structure (container) for fast element insertion/deletion by index?

Answer 1

Depends on whether or not you're talking about something in memory or on disk. Usually, on disk it is some variant of a B-tree, and usually, in memory, it is generally a linked list (if you know what node you need to insert at).

Answer 2

Try a hash table that dynamically resizes at fixed intervals.

Assuming a pretty good uniform distribution, you should have basically constant time [O(1)] access time.

http://www.cs.cornell.edu/courses/cs312/2006fa/lectures/lec14.html

That link seems to give a good explanation.

Answer 3

You could get O(log n) performance using a binary tree with a node structure like this:

struct Node<T>
    T value
    Node left
    int left_count
    Node right
    int right_count
end

The left_count value would hold the number of nodes in the left branch of the tree, and similarly for the right side. Lookup would be performed by starting at the top of the tree and traversing downward based on comparing the desired index value with the left and right counts. Insertion and deletion would be performed using the normal binary tree algorithms, with appropriate adjustment to the count values. More consistent performance can be achieved by requiring that the binary tree is balanced.

This kind of tree probably has a name; more information appreciated!