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.
Data structure with search, insert and delete in amortised time $O(1)$?
data structures;time complexity;asymptotics;amortized analysis
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): 932963. doi:10.1137/S0097539705447256.