When do you use collections.deque instead of list?

Short answer

Use deque when you need to add or remove elements at both ends in O(1), such as queues and sliding windows, and use list for indexed access and appending at the end.

Explanation

A list is a contiguous array, so list.pop(0) and insert(0, x) shift all the elements and cost O(n). A deque is a linked list of blocks that supports appendleft and popleft in constant time, but indexed access in the middle is O(n). The maxlen option turns the deque into a ring buffer that automatically keeps the last N elements. For queues between threads use queue.Queue, and for priorities use heapq.

Code example

from collections import deque

queue = deque()
queue.append("job-1")
queue.append("job-2")
first = queue.popleft()      # O(1) Instead of list.pop(0)

recent = deque(maxlen=3)
for value in [1, 2, 3, 4, 5]:
    recent.append(value)
print(recent)  # deque([3, 4, 5], maxlen=3)

Common mistakes

• Using list.pop(0) in a large queue inside a loop.
• Repeatedly accessing elements in the middle of a deque by index.

Follow-up questions

• How does the choice of data structure change a program's performance?

Sources

• Python documentation — collections.deque