## DEV Community

\144\150\162\165\166(dhruv)

Posted on

# 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.