1
$\begingroup$

First of all, a definition of the operations:

  • Insert by index: insert element e at index 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 n.

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

$\endgroup$
  • $\begingroup$ I don't know of data structures that have better worst-case running time for at least one of these three operations, while keeping the other two at $O(\log N)$. If you care about efficiency in practice, and there is some locality among accesses, B-trees or finger trees might provide improvements, but you'd have to measure. $\endgroup$ – D.W. Apr 20 '18 at 17:59
  • $\begingroup$ @D.W.: Updates are more likely to be close to the head (lower indices). I've thought about using a dynamic array and index from the end, which improves the average case, but does nothing for the worst case. $\endgroup$ – Matthieu M. Apr 20 '18 at 18:32
  • $\begingroup$ Google for the implementation of NSMutableArray, which does operations at the beginning and end of an array fast. That should give you some ideas to handle slightly more complex cases, like a series of operations passing through an array. While reasonably good worst case behaviour is nice to have, performing the operations that you actually require fast is nicer. $\endgroup$ – gnasher729 Apr 20 '18 at 18:33
  • $\begingroup$ @gnasher729: Thanks for the tip. While reasonably good worst case behaviour is nice to have, performing the operations that you actually require fast is nicer. => Actually, in this particular case, a bound on the worst-case matters; a lot. I have already implemented efficient double-ended arrays in the past... but they still have O(N) worst-case insertion/deletion in the middle. $\endgroup$ – Matthieu M. Apr 20 '18 at 18:41
  • $\begingroup$ @D.W.: By the way, I am not necessarily hung up on O(log N). I am looking for better than linear (otherwise the dynamic array does the job), but would consider solutions with O(log² N) insert/delete and O(log log N) for example (or vice-versa). $\endgroup$ – Matthieu M. Apr 20 '18 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.