10
$\begingroup$

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?

$\endgroup$
17
  • 1
    $\begingroup$ 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. $\endgroup$ – usul Feb 26 '13 at 1:27
  • 1
    $\begingroup$ @usul, assume RAM model if you need. $\endgroup$ – Kaveh Feb 26 '13 at 1:33
  • 1
    $\begingroup$ @usul, no, it's constant time AFAIK. $\endgroup$ – Kaveh Feb 26 '13 at 6:15
  • 4
    $\begingroup$ This question seems to be related. $\endgroup$ – Raphael Feb 26 '13 at 10:40
  • 1
    $\begingroup$ Cuckoo hashing (mentioned by Suresh a propos of a somewhat related problem) may be of interest here. $\endgroup$ – Gilles 'SO- stop being evil' Feb 26 '13 at 19:55