A Python list is a contiguous array of pointers. Appending to the right is
amortised $O(1)$. Inserting at the left is $O(n)$, because every existing
element has to move up one slot. The same asymmetry applies to pop(0).
That is invisible at small $n$ and fatal at large $n$: 100,000 calls to
list.insert(0, i) measured 1157 ms, and the same work through
deque.appendleft measured 1.04 ms — roughly 1,100x. The shape of the
bug is the giveaway: it is not slow, it is quadratically slow, so it passes
every test at fixture size and melts the first time production hands it a real
queue.
collections.deque is a doubly-linked list of fixed-size blocks. Both ends
are $O(1)$:
| Operation |
list |
deque |
|---|---|---|
append / pop (right) |
$O(1)$ | $O(1)$ |
insert(0, x) / pop(0) |
$O(n)$ |
$O(1)$ via appendleft / popleft |
d[i] (middle) |
$O(1)$ | $O(n)$ |
| slicing | yes |
TypeError |
The trade is random access. A deque supports indexing but walks the blocks to
get there, and it does not support slicing at all — d[1:3] raises
TypeError. If your algorithm indexes into the middle, you want a list.
The three things people actually use it for
A queue. BFS, work queues, anything FIFO. append on one end,
popleft on the other.
A last-N buffer. deque(maxlen=n) silently discards from the opposite
end when it is full. This is the entire implementation of a ring buffer:
recent: deque[Event] = deque(maxlen=100)
recent.append(event) # never grows past 100
And deque(iterable, maxlen=n) consumes the whole iterable while retaining
only the last n — the canonical way to read the tail of a stream you cannot
seek in, in constant memory.
A rotation. d.rotate(k) moves the right end to the left, k steps, in
$O(k)$. Round-robin scheduling, cyclic buffers, and “shift the window” all
fall out of it.
💡extendleft looks like the mirror of extend. Why does
click to reveal
deque([3]).extendleft([1, 2]) give deque([2, 1, 3]) and not
deque([1, 2, 3])?
Because extendleft is defined as a loop of appendleft. It takes 1, puts
it at the front ([1, 3]), then takes 2 and puts that at the front
([2, 1, 3]). Each element goes in front of the one before it, so the input
order is reversed.
This is documented and still surprises everyone, because the name suggests
symmetry with extend. If you want the input order preserved on the left,
reverse first:
d.extendleft(reversed(items))
The same reasoning explains rotate(1): it moves the rightmost element to
the front, which is a right rotation, not a left one.
The typing detail
deque is generic (deque[float]), and maxlen is typed int | None —
because an unbounded deque genuinely has no maximum. So this fails:
def headroom(buffer: deque[float]) -> int:
return buffer.maxlen - len(buffer)
# error: Unsupported operand types for - ("None" and "int")The fix is a narrowing branch, and writing it forces you to decide what an unbounded buffer’s headroom means — a question the untyped version never made you answer:
def headroom(buffer: deque[float]) -> int:
limit = buffer.maxlen
if limit is None:
return -1 # unbounded: no meaningful headroom
return limit - len(buffer)💡You need a rolling median over a stream of 10 million floats with click to reveal
a window of 500. A deque(maxlen=500) plus statistics.median is $O(w \log w)$
per step. When is that the right answer anyway?
Almost always, at these numbers. $500 \log 500 \approx 4500$ comparisons per
step is a few microseconds; ten million steps is well under a minute, and the
code is four lines that a reviewer can verify by reading.
The asymptotically better structure — two heaps, or an order-statistic tree, giving $O(\log w)$ per step — is several dozen lines with a lazy-deletion scheme for the elements leaving the window, and every one of those lines is a place to be subtly wrong. Reach for it when the profile says this loop is the bottleneck and the window is large (tens of thousands), not before.
The part you should not compromise on is the buffer: doing the window with
values[i - w : i] copies w floats per step and turns a linear pass into a
quadratic one. The deque is free; the clever median is not.