How can I get O(1) prepend on a random-access list?

Question

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?

Answer 1

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.

Answer 2

The data structure: To represent an array with n elements, you have a backing array with N ≥ n elements, which contains for some k the elements a(k) to a (n-1), then a gap, then the elements a(0) to a (k-1). Inserting and removing elements both at the start and the end of the array is quick (linear in either distance to the start or the end of the array).

After inserting enough elements to remove the gap completely, the array needs to be resized in amortized constant time.

If an operation were to insert / remove at the start of the backing array (that is close to index k), then k will likely need to be changed. Inserting / removing in the middle of the array takes linear time.