# Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

• GetElement(k): Return the $k$th element of the list.

• InsertAfter(x,y): Insert the new element y into the list immediately after x.

• Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

• InsertAfter(NULL, a) $\implies$ [a]
• InsertAfter(NULL, b) $\implies$ [b, a]
• InsertAfter(b, c) $\implies$ [b, c, a]
• InsertAfter(a, d) $\implies$ [b, c, a, d]
• Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should return an error.

• In Optimal Algorithms for List Indexing and Subset Rank (1989) I found a $\Omega{(\frac{log\ n}{log\ log\ n})}$ solution to this problem.
– A T
May 21, 2012 at 7:57
• @Raphael: I think he means the element that would be called $A[k]$ if the data structure were an array. Arrays support the first operation in $O(1)$ time but not the second; linked lists support the second operation in $O(1)$ time but not the first. May 21, 2012 at 8:51
• Also, balanced binary trees support both operations in $O(\log n)$ time. May 21, 2012 at 8:56
• @Raphael: Edited to clarify. May 21, 2012 at 9:13
• @JeffE the dynamic array supports the first two in $O(1)$ amortized time (cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf) May 21, 2012 at 21:11

NO.

Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation. (This is reference  in the paper by Dietz that you mention in your first comment.) The lower bound holds in the very powerful cell probe model of computation, which only considers the number of distinct memory addresses accessed by the update and query algorithms.

Without some additional assumptions about the update and query operations, Dietz's data structure is the best possible (at least up to constant factors).

• @AT: That bound was never "proved wrong". There are situations where it does not apply, but that is an entirely different statement!
– Raphael
May 21, 2012 at 15:22
• @AT: The sorting lower bound was proved in a much weaker model of computation, namely binary decision trees. The bound was "proved wrong" by developing faster algorithms that cannot be described as binary decision trees. In order to prove Fredman and Saks' lower bound wrong, you'll have to design a faster algorithm that doesn't access memory. Best of luck. May 21, 2012 at 17:51
• @JeffE and Raphael; please review my other answer and confirm/deny my result when you get the chance. Thanks.
– A T
Jan 7, 2013 at 4:27

Looks like the $\Omega(\dfrac{\log n}{\log\log n})$ barrier has been overcome by modifying the analysis from the chronogram technique.

The new [lower] $\Omega(\log n)$ bound has been proved for similar problems in the cell-probe model . From reading that article; it is my understanding that that bound applies to the list representation problem also.

• This lower bound holds for constant-sized words, whereas the earlier $\Omega(\log n/\log\log n)$ lower bound is for logarithmically-sized words. Jan 8, 2013 at 1:00
• Indeed. Also, can you confirm that this bound applies to the list representation problem with constant-sized words?
– A T
Jan 11, 2013 at 6:26
• I can confirm that, because of the Dietz bound (hdl.handle.net/1802/5694) that you yourself mentioned. This makes the complexity exactly $\Theta(\log n/\log \log n)$, and therefore not $\Omega(\log n)$. Mar 16, 2015 at 6:05