LANGUAGE REFERENCE · /python/deque/

deque in Python

4 min read Last verified August 19, 2026 CPython 3.12

ANSWER

Use a deque when you append or pop at both ends. A Python list is O(n) on the left, because removing the first item shifts every remaining element down one place.

IN PLAIN TERMS

You can couple or uncouple a carriage at either end of a train in one move, and a deque works the same way. A list is more like a numbered row of chairs: take the front one away and everybody has to shuffle up a seat.

Fit the whole diagram on screen Show it at full size, and pan

FIG 1 A deque is a doubly linked list of fixed-size blocks, not a ring buffer over one array — which is exactly why both ends are cheap and the middle is not.

CPython 3.12

from collections import deque

q = deque([1, 2, 3], maxlen=4)
q.appendleft(0)     # deque([0, 1, 2, 3])
q.append(4)         # deque([1, 2, 3, 4]) — 0 fell off the left
q.rotate(1)         # deque([4, 1, 2, 3])

The Python-specific detail

Because those blocks are linked rather than contiguous, indexing into the middle is O(n) while both ends are O(1). That is the reason q[len(q)//2] inside a loop is the classic way to make a deque slower than the list it replaced — the mirror image of the cost a level-order tree walk pays when it takes from the front of a plain list instead.

The second surprise is maxlen : it discards silently from the opposite end. Perfect for a rolling window, quietly destructive if you expected an exception — the same kind of silent wrong outcome as an API that replays a stored response and sends the confirmation email a second time, because the email was never part of the record.

Checked against CPython 3.12's collections documentation — which states that indexed access slows to O(n) in the middle, and that a bounded deque discards from the opposite end — and Modules/_collectionsmodule.c, whose own comment describes the doubly-linked list of fixed-length blocks, 19 August 2026.