# 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?

• Why do you need to reverse the list in every operation? Why can't you just define a reversed list as your data structure? Jun 10, 2016 at 19:40

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.