Deque random acces O(n) in python while O(1) in C++, why? [duplicate]

Question

C++ deque:

Random access - constant O(1)

Python deque:

Indexed access is O(1) at both ends but slows to O(n) in the middle.

If I'm not missing anything, everything else is equally fast for deques in python and in C++, at least complexity-wise. Is there anything that makes python's deque better for some cases? If not, why don't they just switch to what C++ has?

Answer 1

Disclaimer: this answer is largely inspired from Jeff's comment and the answer already posted at Why is a deque implemented as a linked list instead of a circular array ?

Your question is different in nature but the title above is an answer in itself: in Python, the module collections.deque has a linear time complexity when accessing items in the middle because it is implemented using a linked list.

From the pydoc:

A list-like sequence optimized for data accesses near its endpoints.

Now if you're wondering why this implementation was chosen, the answer is already available in the post pointed out by Jeff.