First of all, a definition of the operations:
- Insert by index: insert element
n, increasing the index of all subsequent elements,
- Delete by index: delete element at index
n, decreasing the index of all subsequent elements,
- Access by index: access element at index
The interface, therefore, is that of a Dynamic Array.
The simplest implementation of a Dynamic Array is to use an array with exponential growth. The performance of the various operations are:
- Insert/Delete by index: O(N),
- Access by index: O(1).
Which is great for frequent access, but not so for frequent modifications.
An Order Statistics Tree, that is a binary tree with each node augmented with the number of elements in the sub-tree it roots, has more balanced performance:
- Insert/Delete/access by index: O(log N).
It can be implemented using an Eytzinger (BSF) layout for cache friendliness.
Are there more efficient data-structures for insert/delete by index?
Notably, keeping all 3 operations sub-linear, is it possible to improve on O(log N)?