How can I get O(1) prepend on a random-access list?
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.