What is a Python Deque?
A Python Deque is implemented internally using a doubly linked list. This means that every element of the link list has a pointer to the previous element and also the next element. This allows for fast appends and prepends.
The internal implementation in cpython is actually using arrays and by keeping two indexes: left index and a right index. You can look deeper into it at: https://github.com/python/cpython/blob/main/Modules/_collectionsmodule.c
When to use a Python Deque?
Because of the above characteristics complexity to add a new element at either end of the deque is O(1).
However, if you need to searching a particular element in the middle of a deque then this comes at a cost higher in the worst case: O(n) than a simple Python list: O(1). Appending and removing in the middle is also slower.
So when should you actually use a Python Deque? Find below a table summary for comparison:
| Operation | List | Deque |
| Append Left or Right | O(n) | O(1) |
| Get/Set element | O(1) | O(n) |
| Pop right | O(1) | O(1) |
| Pop left | O(n) | O(1) |
Appending near the beginning and end for Python list can be O(n) because of how memory is allocated for Python lists. When the list grows beyond the allocated size Python needs to be move everything to a new memory location.
If you are adding to the beginning and end a lot then this is when you need to consider using a Python Deque.
You can view a full list of time complexity information on Python collection list, deque, set and dictionary at https://wiki.python.org/moin/TimeComplexity
Sample usage of a Python Deque
from collections import deque
deq = deque()
#initialise
deq.appendleft(1)
print(deq) #deque([1])
deq.append(2)
print(deq) #deque([1, 2])
deq.appendleft(0)
print(deq) #deque([0, 1, 2])You need to first import it from the collections library. Then you need to initialize a deque with deque().
Python Deque Rotate Example
deq.append(3)
print(deq) #deque([0, 1, 2, 3])
deq.rotate() #same as deq.rotate(1)
print(deq) #deque([3, 0, 1, 2])
deq.rotate(-1)
print(deq) #deque([0, 1, 2, 3])
deq.rotate(2)
print(deq) #deque([2, 3, 0, 1])
deq.rotate(-2)
print(deq) #deque([0, 1, 2, 3])
By default deque.rotate will rotate to the right and 1 step (default). If you want to rotate to the left you will need to provide a negative value.
If you would like to learn more Python check out this certificate course by Google: IT Automation with Python
