I need a data structure that has the following operation:
- $\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$
$\operatorname{prepend}$ should be in $O(1)$.
Assume that you have only randomly-accessible lists available. That is the following operations are available that are all in $O(1)$:
- $\operatorname{update}([x_n, ..., x_0], i, y) = [x_n, x_{i + 1}, y, x_{i - 1}, x_0]$
- $\operatorname{at}([x_n, ..., x_1], i) = x_i$
- $\operatorname{append}(([x_n, ..., x_1], x_0) = [x_n, ..., x_0]$
You could of course reverse the list in $O(n)$ each time but then $\operatorname{prepend}$ would also be in $O(n)$. So the list has to be reversed in real-time at each call of $\operatorname{prepend}$. Is there such data structure?