A deque (double-ended queue) is a specialized data structure from Python's collections module that allows fast O(1) appends and pops from both ends, unlike lists which have O(n) time complexity for operations at the start.
A deque is an optimized list-like container that allows:
* Fast insertion/removal from both ends (O(1) time complexity).
* Thread-safe (supports locking for multi-threading).
* Efficient memory usage (implemented as a doubly linked list).
You need to import collections.deque to use it.
from collections import deque
# Creating a deque
dq = deque([1, 2, 3])
# Append elements (to the right)
dq.append(4) # [1, 2, 3, 4]
# Append elements (to the left)
dq.appendleft(0) # [0, 1, 2, 3, 4]
print(dq) # Output: deque([0, 1, 2, 3, 4])
* Faster than list.append() and list.insert(0, x).
| Feature | Deque | List |
|---|---|---|
Appending at end (.append()) |
O(1) | O(1) |
Appending at start (.appendleft()) |
O(1) | O(n) |
Popping from end (.pop()) |
O(1) | O(1) |
Popping from start (.popleft()) |
O(1) | O(n) |
| Memory Usage | More efficient (linked list) | Less efficient for frequent inserts/deletes |
| Thread-Safe | Yes | No |
dq.pop() # Removes from right
dq.popleft() # Removes from left
dq.rotate(2) # Moves last two elements to front
print(dq)
* Useful for circular buffers!
dq = deque(maxlen=3) # Fixed size of 3
dq.extend([1, 2, 3])
dq.append(4) # Removes 1 automatically
print(dq) # Output: deque([2, 3, 4], maxlen=3)
* Great for implementing caches and sliding windows!
* Fast insert/remove at both ends (e.g., queues, caching).
* Efficiently handle large datasets (e.g., log files, sliding windows).
* Ideal for FIFO (first-in, first-out) and LIFO (last-in, first-out) structures.