I think it's more common than not to implement deques on top of arrays. There's a meaningful performance difference at the hardware level due to the spatial locality in memory. Linked lists in general cause the CPU to jump all over the place in memory, causing pressure on the cache and whatnot.
I believe the standard C++ deque implementation consists of a vector of vectors. The purpose of the two layers is at least two-fold. It guarantees that elements stored within the deque remain at a stable memory location at all times, even during a reallocation. Also, the memory getting shifted around during a reallocation consists of relatively tiny vector metadata rather than the application data.
To speculate, I suspect the reason it's a linked list in python is due to the age of the module. It was likely written relatively early on in python's development, and the linked list implementation was simple and elegant. Now enough stuff uses it that it would be painful to change.
Dicts are hashmaps in python rather than binary trees for similar performance reasons. You can't even find any binary tree based containers in python's standard library. You can find containers with the same performance characteristics and semantics of binary trees, but under the hood they're implemented on top of arrays because it better maps to hardware.
I believe the standard C++ deque implementation consists of a vector of vectors. The purpose of the two layers is at least two-fold. It guarantees that elements stored within the deque remain at a stable memory location at all times, even during a reallocation. Also, the memory getting shifted around during a reallocation consists of relatively tiny vector metadata rather than the application data.
To speculate, I suspect the reason it's a linked list in python is due to the age of the module. It was likely written relatively early on in python's development, and the linked list implementation was simple and elegant. Now enough stuff uses it that it would be painful to change.
Dicts are hashmaps in python rather than binary trees for similar performance reasons. You can't even find any binary tree based containers in python's standard library. You can find containers with the same performance characteristics and semantics of binary trees, but under the hood they're implemented on top of arrays because it better maps to hardware.