When to prefer deque over list

Question

Accepted Answer

Removing from the front of a Python list with pop(0) is O(n) because every remaining element shifts left by one slot. collections.deque is a doubly-linked structure where both appends and pops from either end are O(1). For queue workloads - first in, first out - deque is the correct choice and the performance difference becomes visible at a few thousand iterations.