The current implementation of deque is a doubly linked list of arrays. Indexing is indeed linear, but still very efficient. It takes 1 ms to index a deque with a million items.

If that's not good enough, you should try to implement your own container using lists (which are dynamic arrays in Python). That should be easy to implement though this approach will likely be slower for everything but very large datasets.