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.

  • 2
    $\begingroup$ In Optimal Algorithms for List Indexing and Subset Rank (1989) I found a $\Omega{(\frac{log\ n}{log\ log\ n})}$ solution to this problem. $\endgroup$ – A T May 21 '12 at 7:57
  • 2
    $\begingroup$ @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. $\endgroup$ – JeffE May 21 '12 at 8:51
  • 2
    $\begingroup$ Also, balanced binary trees support both operations in $O(\log n)$ time. $\endgroup$ – JeffE May 21 '12 at 8:56
  • 1
    $\begingroup$ @Raphael: Edited to clarify. $\endgroup$ – JeffE May 21 '12 at 9:13
  • 2
    $\begingroup$ @JeffE the dynamic array supports the first two in $O(1)$ amortized time (cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf) $\endgroup$ – didest May 21 '12 at 21:11


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 [1] 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).

  • 3
    $\begingroup$ @AT: That bound was never "proved wrong". There are situations where it does not apply, but that is an entirely different statement! $\endgroup$ – Raphael May 21 '12 at 15:22
  • 5
    $\begingroup$ @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. $\endgroup$ – JeffE May 21 '12 at 17:51
  • $\begingroup$ @JeffE and Raphael; please review my other answer and confirm/deny my result when you get the chance. Thanks. $\endgroup$ – A T Jan 7 '13 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 [1]. From reading that article; it is my understanding that that bound applies to the list representation problem also.

[1] Patrascu, Mihai, and Erik D. Demaine. “Logarithmic Lower Bounds in the Cell-Probe Model.” SIAM J. Comput. 35, no. 4 (April 2006): 932–963. doi:10.1137/S0097539705447256.

  • 1
    $\begingroup$ This lower bound holds for constant-sized words, whereas the earlier $\Omega(\log n/\log\log n)$ lower bound is for logarithmically-sized words. $\endgroup$ – Yuval Filmus Jan 8 '13 at 1:00
  • $\begingroup$ Indeed. Also, can you confirm that this bound applies to the list representation problem with constant-sized words? $\endgroup$ – A T Jan 11 '13 at 6:26
  • 1
    $\begingroup$ 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)$. $\endgroup$ – jbapple Mar 16 '15 at 6:05

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.