I'm curious about how Python's deque efficiently allows both push and pop operations to be done in O(1) time. It's typically understood that queues are implemented using either linked lists or arrays. However, with an array, using popleft() would generally be O(n), and removing the last item from a linked list could be O(n) too if you don't have a pointer to the end. So what's the trick here?
4 Answers
Python's deque is implemented as a doubly-linked list that consists of fixed-size arrays. This design minimizes the overhead linked with maintaining pointers while boosting performance. It also sidesteps the need for reallocating memory, which would slow things down.
When you're working with linked lists, both pushing and popping can be O(1) since you can quickly add or remove nodes from either end if you're using a doubly-linked list. You might think popping from the back could be O(N), but actually, if you maintain a pointer to the end, it stays O(1).
The original question is focused on how Python's deque does it, not just any deque. It's worth noting that with a doubly-linked list, you can operate at both ends in O(1). Deques can also be utilized as a circular buffer, meaning no items need to be moved when you push or pop, unless you're increasing the buffer size during a reallocation.
In a doubly-linked list, you always keep track of both ends, which is why push/pop from either end can be done in O(1). Arrays can also be adapted to act like deques when you manage them as ring buffers and maintain indices for the start and end.
Is that something specific to Python's implementation? Do they handle linked lists differently compared to how other languages might?