I've always wondered why we use deque
for working with queues in Python. After doing some research, I found out some cool things that deque
has to offer, while using list
for queues may not always be a good choice.
What is deque
, anyway?
Essentially, it's very similar to a native Python list, but better.
Elements in a list
are stored contiguously in a single block of memory and have a single pointer that points to the very first element. On the other hand, deque
is a double-ended list with pointers at both ends.
Here are some factors which make deque a better choice than list:
- Append Operation
: Both
list
anddeque
take constant time complexity for appending, as list uses pointer arithmetic (e.g.,o + length(4) = address 4
) to find the last element and then append a new item. In case of deque, it has a rear pointer at the end. So it also takes constant time complexity
Pop Operation
: Both structures have the same constant time complexity as they find the last element using the same logic and then pop the last element from the list.
Prepending Operation
: Here's where the magic of deque begins! List structures need to shift forward each element by 1 position, and insert the value at first position making the whole process O(n) time complexity or linear time complexity. Adeque
, on the other hand, with its front pointer, performs prepending in constant time complexity by using a circular buffer and shifting the front pointer to -1. In reality, the new value is stored in a higher memory address, but under the hood, it is logically the first element of thedeque
after the prepend operation.
Popping from the left
: Again,list
structures need to pop the leftmost element and shift each value by one position to the left, resulting in linear time complexity. On the other hand,deque
pops the value at the front pointer and updates the front pointer to the right. Yes, it takes only constant time complexity, making the process significantly more efficient.
Insertion/Deletion into middle
: With alist
, the time complexity ranges from O(1) to O(n) depending on the position of the element. In the case ofdeque
, it ranges from O(1) to O(n/2).
If you have any feedback, then you can DM me on Twitter or Linkedin.
Top comments (2)
I liked your explanation, but you could have the code attached to the post. So that readers can run it while reading. It would bring more engagement with what you wrote. Congratulations on the post.
Thanks sc0v0ne for the valuable feedback, I would surely integrate code also