I've recently gotten into investigating how various data structures are implemented in Python in order to make my code more efficient. In investigating how lists and deques work, I found that I can get benefits when I want to shift and unshift reducing the time from O(n) in lists to O(1) in deques (lists being implemented as fixed-length arrays that have to be copied completely each time something is inserted at the front, etc...). What I can't seem to find are the specifics of how a deque is implemented, and the specifics of its downsides v.s. lists. Can someone enlighten me on these two questions?
https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c
A
dequeobjectis composed of a doubly-linked list ofblocknodes.
So yes, a deque is a (doubly-)linked list as another answer suggests.
Elaborating: What this means is that Python lists are much better for random-access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists.