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?
Is there a data-structure which is more efficient than both arrays and linked lists?
data structures;arrays;lower bounds;linked lists