How can I get O(1) prepend on a random-access list? 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?
A deque with growing arrays provides the operations you need in (amortized) constant time. Reversing a deque is simple, you don't move data around, you just switch the meaning of prepend and append and massage the index for at and update.

But you don't seem to want to reverse the list anyway.