When would you use collections.deque instead of a list, and why?
deque is for O(1) operations at both ends; list is for random access
collections.deque is a doubly linked list of fixed-size blocks. It provides O(1) append and pop from both ends, and it supports an optional maxlen for bounded buffers. A list is better for O(1) random access and memory locality, but its front operations are O(n) because elements shift. Use deque for queues, BFS frontiers, sliding windows, and ring buffers. Use list when you mostly index, iterate, and append/pop at the end.
- 1
deque.popleft() and deque.appendleft() are O(1); list.pop(0) and list.insert(0, x) are O(n).
- 2
deque indexing in the middle is O(n) in CPython, so do not use it as a random-access array.
- 3
maxlen gives automatic eviction of the oldest item, which is useful for bounded caches and windows.
- 4
Common mistake: assuming deque is always faster. For iteration and indexing, list is often faster due to contiguous memory.
- 5
Version note: deque has been available since Python 2.4; maxlen is stable and widely supported.
Scenario Questions
0-2 years experience
- 1You need a queue. Why not use list.pop(0)?
- 2You need to keep last 10 items. Which collection?
2-5 years experience
- 1You implement BFS. Which collection for frontier and why?
- 2You need both stack and queue behavior. List or deque?
5-8 years experience
- 1You process a high-throughput stream with a sliding window. Deque or list?
- 2You need O(1) indexing in the middle. Would deque work?
8+ years experience
- 1Design a lock-free-ish queue for a producer-consumer pipeline using Python built-ins. Discuss deque and alternatives.
- 2You need bounded deque with backpressure. How do you implement?
Follow-up Questions
- What is the complexity of indexing into the middle of a deque?
- How does maxlen help implement a sliding window?