Python Deque v/s List🐍

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 and deque 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. A deque, 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 the deque 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 a list, the time complexity ranges from O(1) to O(n) depending on the position of the element. In the case of deque, it ranges from O(1) to O(n/2).

If you have any feedback, then you can DM me on Twitter or Linkedin.

Comments

[Eddi Silva]

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.

[dhruv]

Thanks sc0v0ne for the valuable feedback, I would surely integrate code also