# Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

### Background:

In this question we care only about worst-case running-time.

Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the following three operations:

• $$Location(i)$$: returns a pointer to the $$i$$th item in the list of items in the array.
• $$Insert(k,x)$$: insert the item $$k$$ in the list after the item pointed to by $$x$$.
• $$Delete(x)$$: remove the item in the list pointed to by $$x$$.

The main operation that an array provides is location which can be computed in constant time. However delete and insert are inefficient.

On the other hand, in a doubly linked list, it is easy to perform insert and delete in constant time, but location is inefficient.

### Questions:

Can there be a data structure to store a list of items where all three operations are $$O(1)$$? If not, what is the best worst-case running-time that we can achieve for all operations simultaneously?

Note that a balanced binary search tree like red-black trees augmented with size of subtrees would give $$O(\lg n)$$, is it possible to do better? Do we know a non-trivial lower-bound for this problem?

• I wonder if a precise answer to this question requires a more precise definition of the model of computation. For instance, in the operation $Location(i)$, $i$ must be of size $\log n$ in general, so we must be making some assumption to be able to say that $Location(i)$ is $O(1)$ for an array.
– usul
Feb 26 '13 at 1:27
• @usul, assume RAM model if you need. Feb 26 '13 at 1:33
• @usul, no, it's constant time AFAIK. Feb 26 '13 at 6:15
• This question seems to be related.
– Raphael
Feb 26 '13 at 10:40
• Cuckoo hashing (mentioned by Suresh a propos of a somewhat related problem) may be of interest here. Feb 26 '13 at 19:55