collections.deque
Overview
`collections.deque` ('deck') is a double-ended queue: appending and popping at *either* end is O(1). A Python `list` is O(1) at the right end but O(n) at the left, because `list.pop(0)`/`insert(0, x)` shift every remaining element. from collections import deque q = deque([1, 2, 3]) q.append(4) # right end q.appendleft(0) # left end -> [0,1,2,3,4] q.popleft() # O(1) from the front q.pop() # O(1) from the back That makes deque the correct structure for FIFO queues and BFS. It also takes `maxlen`: a bounded deque that automatically discards from the opposite end when full — perfect for 'last N items' / sliding windows. Trade-off: no fast random access — indexing the middle is O(n), so use a list when you need `d[i]` in the interior.
BFS (graph/tree level-order traversal) and any producer/consumer queue need O(1) pops from the front. Using `list.pop(0)` there turns an O(n) algorithm into O(n^2) — a classic performance bug and interview gotcha.
Where used: BFS queue in graph/tree traversal, Sliding-window / last-N buffers (maxlen), Producer-consumer task queues
Why learn this
- BFS and queue-based algorithms require O(1) front removal — deque is the right tool, `list.pop(0)` is the trap.
- The `maxlen` bounded deque is an elegant one-liner for sliding windows and 'keep the last N' buffers.
Code walkthrough
from collections import deque
q = deque()
q.append('a')
q.append('b')
q.appendleft('z')
print(q)
print(q.popleft())
print(q)Focus: q.popleft() (removes 'z' from the front in O(1))
Common mistakes
- Using list.pop(0) as a queue: `list.pop(0)` is O(n) because every remaining element shifts left one slot. In a loop that's O(n^2) and silently slow on large inputs. `deque.popleft()` is O(1).
- Indexing into the middle of a deque: deque is optimized for the ends; `d[len(d)//2]` is O(n), not O(1). If you need fast interior random access, a list is the right structure.
- Forgetting maxlen discards silently: A `deque(maxlen=3)` drops an element from the opposite end each time you append past the limit — no error, no warning. That's the feature, but it will quietly lose data if you didn't intend a bounded buffer.
Glossary
- amortized O(1)
- An operation that is constant-time on average across many calls, even if a rare individual call costs more. deque appends/pops at both ends are O(1).
Recall questions
- Why is `deque.popleft()` better than `list.pop(0)` for a queue?
- What does a `deque(maxlen=n)` do when you append beyond n items?
- What is deque worse at than a list?
Understanding checks
What does this print?
[2, 3]
With maxlen=2, appending 3 pushes the deque over its limit, so the oldest element (1) is discarded from the left. Only the two most recent values remain.
You're implementing BFS and repeatedly remove the next node from the front of a collection of thousands of nodes. Do you use a list with `.pop(0)` or a deque with `.popleft()`?
A deque with `.popleft()`.
Front removal happens once per node; `list.pop(0)` is O(n) each time, making BFS O(n^2), while `deque.popleft()` is O(1), keeping BFS O(n).
Practice tasks
Keep the last 3 readings
Feed the numbers 1..6 one at a time into a bounded deque that keeps only the 3 most recent values, then print the final deque.
Continue learning
Previous: Lists: indexing, slicing, methods