Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time?

When I say "reasonable time", I mean that it should be equal to or better than $O(\log N)$.

I'm looking for a structure similar to a dynamic array, but I need a better behavior in the Insertion operation. When the array size grows, the time grows exponentially (Except at the end of the array).

  • 1
    $\begingroup$ Have you looked at any material about data structures? Are you familiar with search-trees? When you say "reasonable time", do you mean worst or average case? $\endgroup$ – Raphael Aug 5 '13 at 20:40
  • $\begingroup$ Yes, I am familiar with search trees, that was my first choice... but, I didn't know if there was something better. $\endgroup$ – vicentazo Aug 6 '13 at 8:49
  • $\begingroup$ @Raphael, when I say "reasonable time", I mean average case $\endgroup$ – vicentazo Aug 6 '13 at 8:51
  • 3
    $\begingroup$ This question may also be relevant. Note thought that "the best" data structure does not exist. Different ones trade off multiple metrics (availability/runtime of several operations, space, code complexity, robustness, worst-case performance, average-case performance, adaptivity, potential for concurrency, ...) so the choice depends critically on what you want "optimised" and what cost you are ready to tolerate for that. $\endgroup$ – Raphael Aug 6 '13 at 9:07

A balanced binary tree should meet your needs. You can achieve $O(\lg n)$ time for both operations, as long as the tree is kept reasonably balanced.

To support the "access by index" operation, you can augment the tree so that each internal node contains the number of children underneath it. Insert operations still take $O(\lg n)$ time (find the place where to insert a new leaf, then traverse the path from that leaf to the root, incrementing the counter in each such node). The "access by index" operation can be done using the counts in each node; they tell you at each stage whether to recurse to the left child or right child.

There are probably other data structures as well, but this should meet all of the requirements you listed.

  • 2
    $\begingroup$ Nota bene: when you read about search trees, they will typically sort by key. In this case, it seems as if we need sorting by index in the original list. An easy adaption, of course. $\endgroup$ – Raphael Aug 5 '13 at 20:41

Since you are after average efficiency, you may be interested in the following data structures (assuming amortisation is fair, too):

In fact, most dictionary data structures that are not a plain list will work for you. I recommend you do some reading, e.g. in CLRS for starters.

  • $\begingroup$ I think a hash table is what he is after $\endgroup$ – TylerAndFriends Aug 7 '13 at 1:46
  • $\begingroup$ @TylerAndFriends Assuming the hash table maps index to item at given index, how do you implement an insert operation that is better than inserting in a dynamic array (on average)? $\endgroup$ – BlackJack Dec 24 '17 at 13:43
  • $\begingroup$ @BlackJack Please don't use comments to post new questions, let alone ping people on ages old posts when it's not about those posts. Please post a question. $\endgroup$ – Raphael Dec 28 '17 at 20:52
  • $\begingroup$ @Raphael I had a specific question to a specific comment/user here. That's not material for a new general question. Maybe it's also a question for you, because you proposed hash tables in your answer without going into detail how this is an answer to vicentazo's question. Maybe you can clarify how hash tables are an answer here, because I don't see this. $\endgroup$ – BlackJack Dec 29 '17 at 23:54
  • $\begingroup$ @BlackJack The question is just as vague. The data structures I list fulfill the O(log n) upper bound for the required operations -- that much is common knowledge. $\endgroup$ – Raphael Dec 30 '17 at 1:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.