53The deque — fast at both ends
In Chapter 52 we built the queue — first in, first out. It was cheap at both ends only because we picked the right structure underneath. Now we meet the container that refuses to choose an end at all. A deque — say "deck", short for double-ended queue — is a stack and a queue fused into one. You push and pop at the front and the back, and all four of those moves cost O(1). Here's the plan. First we'll open up the memory to find the one trick that buys both-ends speed: a chain of small blocks. Then we'll find the single caveat that tells you when not to reach for it. All the way through, we keep asking the question that separates a tool from a toy — what access pattern makes a deque exactly right, and where does that same shape quietly betray you? By the end you'll spot an "ends-only" pattern on sight, use a bounded deque as a self-trimming history, and collapse a sliding-window problem from O(n·k) down to O(n).
01Both ends, for free
Let's start with the list you already know, because the deque is a direct answer to something the list does badly. From Volume 1, a list is a contiguous block of 8-byte references. That makes it cheap at the back: append is amortized O(1), because it just drops a reference into a spare slot. But the front is a trap. pop(0) and insert(0, x) have to shift every remaining reference one slot over to keep the block gap-free — the front-shift we dissected when we first took the list apart. Watch what that costs. I timed it. Draining 50,000 items one at a time with list.pop(0) took about 4.7 seconds; the same drain with a deque took about 4 milliseconds. That's roughly a thousandfold gap, and it widens with n because the list is quietly O(n²).
append at the back, pop(0) at the front — looks innocent and is quietly quadratic: each pop(0) shifts all remaining references one slot, so serving n items costs about n²/2 moves. That's the ~4.7 s I measured draining 50,000 items, versus ~4 ms on a deque. It is one of the most common reasons a Python service that "worked in testing" seizes up under load. If items leave from the front, reach for a deque.A deque is engineered so both ends are as cheap as a list's back — O(1) at the front and the back alike. The whole secret is the layout. So let's look at the memory before we look at the code.
append or appendleft is one reference write; a fresh block is hooked on only when an end block fills.
pop(0) slides all survivors left) but a deque exactly N. That's the O(n²) trap from the danger box above — push N past a million and a one-line queue quietly asks the CPU for half a trillion moves.Why 64? Why blocks at all — why not one node per item like a textbook linked list, or one big array like a list? →
02Link blocks, not items
Here's the design insight, and it's the kind of "aha" worth stealing. A textbook doubly-linked list gives you O(1) ends, but it pays a whole node object per item. I measured a minimal Python node — a class with __slots__ for value/next/prev. Each one is 56 bytes, or ~344 bytes if it carries an ordinary __dict__, and every node is a separate heap allocation scattered across RAM. Walking such a list is pure pointer-chasing, and each hop is a fresh cache miss — the pointer-chasing tax we clocked back in Volume 3. A plain array is the opposite. Its 64 references sit shoulder to shoulder and stream through cache, but the front is O(n), and growing it means reallocating the whole block.
The deque's author refused to choose. Link the blocks, not the items. Inside one block, 64 references are contiguous: one allocation feeds 64 items, and they scan cache-friendly. Between blocks, prev/next pointers give the front the exact same cheap, local growth the back already had. So you get the linked list's flexible ends and keep most of the array's locality.
The numbers back it up (all RAN on CPython 3.12). A block is 64 × 8 = 512 bytes of cells plus two 8-byte links, so 528 bytes in all. An empty deque already weighs 760 bytes: a ~232-byte header plus one pre-allocated block, because a deque is never truly without a block to write into. Append into it and watch sys.getsizeof climb in flat +528-byte steps, one per new block, while the list next to it grows in fine-grained overallocation steps.
import sys
from collections import deque
print(sys.getsizeof(deque())) # 760 (header + one 528 B block)
d = deque()
prev = sys.getsizeof(d)
for i in range(1, 260):
d.append(i)
s = sys.getsizeof(d)
if s != prev: # print only when a new block is hooked on
print(i, prev, "->", s) # 33 760 -> 1288 ; 97 1288 -> 1816 ; ...
prev = sLine by line: the first print confirms the 760-byte floor. Then we append 259 items and print only on the steps, the moments when getsizeof changes. The real output showed jumps at n = 33, 97, 161, 225, each adding exactly 528 bytes — one block. Why the first jump at 33, not 64? Because a fresh deque drops its first item in the middle of the block, so an append-only run fills the right half (~32 cells) before it needs a second block. In steady state the cost is about 8.25 bytes per element, versus a list's flat 8.00. The block links cost roughly a quarter-byte per item, plus up to one block of slack riding at each end.
append or appendleft has somewhere to land without allocating. The deque pays a higher fixed entry fee to guarantee O(1) at both ends from item one. For a handful of items, a list is lighter; the deque earns its keep at scale and at the front.The deeper cut
_collectionsmodule.c the constant is BLOCKLEN = 64, and a fresh deque starts its two cursors near CENTER = (BLOCKLEN - 1) / 2 = 31 — mid-block, not at an edge. That centering is exactly why an append-only run spills into a second block after roughly 32 items, the +528-byte jump we measured at n = 33. Each block is a struct of PyObject *data[64] plus leftlink and rightlink. To avoid hammering the allocator, CPython keeps a small freelist of up to 16 spent blocks: when an end block empties it's parked on the freelist, and the next block that's needed is grabbed from there instead of a fresh malloc. So the "hook on a new block" step is usually just a pointer relink, not a heap allocation — the amortized reasoning we built in Volume 3, made physical.So an append is cheap. But how cheap, and what does it physically do to those cells? →
03What one append actually does
Let's derive the O(1) instead of just asserting it. To append(x), CPython looks at the rightmost block and rightindex, the cursor sitting on the last used cell. If there's a free cell to its right, it writes the reference to x into that cell and bumps rightindex by one. That's it: one pointer write, one integer increment. The work doesn't depend on how many million items the deque holds, so it's O(1). Only when rightindex is already on the block's last cell — every 64th append — does it grab a block from the freelist, link it on the right, and reset the cursor to the new block's start. That's still constant work. appendleft is the mirror image on the left. pop and popleft read an end cell, step the cursor inward, and unhook a block once one empties. Nothing between the two ends is ever read or moved.
append is a single reference write into the next free cell plus a cursor bump. Because a block's 64 cells are contiguous, a run of appends streams through the same cache lines — O(1) and cache-friendly.from collections import deque
up_next = deque(["Levels", "One More Time", "Strobe"])
up_next.append("Titanium") # add at the back O(1)
up_next.appendleft("Encore") # cut in at the front O(1)
first = up_next.popleft() # serve the front O(1) -> "Encore"
last = up_next.pop() # drop the back O(1) -> "Titanium"Four operations, four constant-time moves — no shifting, no reallocation, no walking. The widget below makes this literal. Drive it and watch the two cursors crawl outward as you push and inward as you pop, and catch the moment a full block hooks a fresh one on.
Both ends are O(1). So is a deque just a better list you should use everywhere? Try to grab the middle element and the answer arrives fast. →
04The catch: the middle is O(n)
Ask a list for a[i] and it computes one address, base + i × 8, and jumps straight there. That's the payoff of a contiguous block: O(1) random access, the same one-multiply-and-add we proved when we built the array. A deque can't do that, because its cells are scattered across linked blocks with no single base. To reach dq[i] it starts at the nearer end and walks the chain block by block — 64 items per hop — until it lands in the right block, then indexes inside. That walk grows with how deep i sits, so it's O(n).
I measured it on a million-item deque. dq[n//2] took about 47 microseconds, while list[n//2] took about 0.17 microseconds — roughly 280× slower, and the gap grows with n. This isn't a small constant. It's a different complexity class. The deque is a specialist for the ends, and paying for the middle is how you misuse it.
Myth
"A deque is just a faster list — swap it in anywhere you use a list."
Reality
A deque is an ends specialist. Front and back are O(1); indexing, slicing, or inserting in the middle is O(n). If your access is "reach element i", that's a list. If it's "add/remove at the ends", that's a deque.
for i in range(len(dq)): use(dq[i]) is a hidden O(n²) — each dq[i] re-walks the chain. If you must scan a deque, iterate it (for x in dq), which the C code walks block by block in one O(n) pass. And if you find yourself wanting random access at all, you probably wanted a list."Ends-only" sounds like a limitation. It's the opposite — a whole family of features you use daily are pure ends games. Start with the one running in your browser right now. →
05A history that forgets — maxlen
Build a deque with maxlen=N and it becomes a fixed-size window on a stream. Once it holds N items, every append silently drops one off the other end to make room. It's a rolling "last N" in one line: newest kept, oldest evicted for free, no manual trimming, and crucially no O(n) pop(0).
from collections import deque
recent = deque(maxlen=3) # keep only the 3 most recent
for page in ["A", "B", "C", "D", "E"]:
recent.append(page)
print(list(recent))
# ['A'] -> ['A','B'] -> ['A','B','C'] -> ['B','C','D'] -> ['C','D','E']I ran it. Once the deque is full at three, appending "D" shoulders out "A", and "E" shoulders out "B". You're always looking at the three newest, and the eviction is an O(1) drop at the far end, not a whole-array shuffle. That single line is the skeleton of a surprising amount of software.
tail -f), a moving average over the last N samples in a trading or sensor feed — all bounded deques. And in the guts of parallel runtimes, work-stealing schedulers (Go, Java's ForkJoin, Rust's Tokio) give each worker its own deque of tasks: the worker pops from one end while idle threads steal from the other — two ends, two customers, zero contention in the common case. You reach for Back in your browser without a thought; you were using a deque.maxlen uses a deque as a rolling buffer. Now use both ends at once, as deliberate scratch space, and an O(n·k) problem collapses to O(n). →
06The killer app: sliding-window maximum in O(n)
Back in Volume 3 we slid a window across an array and kept its sum current in O(1), by adding the entering value and subtracting the leaving one. Maximum is nastier. When the current maximum slides out of the window, you can't cheaply recover the next one, and re-scanning the whole window is O(k), for O(n·k) overall. The fix is a monotonic deque, and it's the deque's signature move.
Keep a deque of indices whose values are strictly decreasing from front to back. For each new element, do three steps. (1) Pop indices off the back whose values are ≤ the newcomer: while this bigger, newer value stands, they can never again be a window maximum, so discard them. (2) Append the new index at the back. (3) If the front index has slid out of the window, popleft it. After those steps, the front index always holds the current window's maximum. Every index is appended once and removed once across the whole run, so the total work is O(n) — amortized, exactly the reasoning we built in Volume 3.
from collections import deque
def max_sliding_window(a, k):
dq = deque() # holds INDICES, values decreasing front->back
out = []
for i, x in enumerate(a):
while dq and a[dq[-1]] <= x: # (1) evict smaller tails: they can't be max
dq.pop()
dq.append(i) # (2) newcomer joins the back
if dq[0] <= i - k: # (3) front slid out of the window?
dq.popleft()
if i >= k - 1:
out.append(a[dq[0]]) # front index = this window's maximum
return out
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)) # [3, 3, 5, 5, 6, 7]Walk it. dq never holds values, only indices — that's how it also knows when a candidate expires. The while loop (1) clears every tail index whose value the newcomer x beats or ties, which keeps the deque decreasing. Step (2) appends the newcomer at the back. Step (3) checks the front: if its index is ≤ i - k it has fallen off the window's left edge, so we popleft. From i = k-1 on, a[dq[0]] — the value at the front index — is the window maximum, emitted in O(1). I ran it against a brute-force max(a[i:i+k]) and got identical output, [3, 3, 5, 5, 6, 7]. On a bigger case (n = 200,000, k = 1000) the deque version took about 80 ms versus the brute force's ~4.8 s, roughly 59× faster here. The gap grows with k. Wall-clock varies by machine, but the O(n) vs O(n·k) shape does not.
That is the deque's reason to exist, generalized: it is O(1) scratch space with two working ends. Palindrome checks (pop a character from each end and compare), balanced-parenthesis checks, BFS frontiers (the breadth-first search we walked through in Volume 3), and rotate(k) for round-robin scheduling all lean on cheap access at both ends. Run deque([1,2,3,4,5]).rotate(2) and you get [4,5,1,2,3] in O(k), no reshuffle.
i, that "yes" turns to "no" — and you want a list.Every linear structure so far — array, stack, queue, deque — reaches its data by walking: to a position, or to an end. The next family throws walking out. Hand it a key — a title, a name, a label — and it computes the address and lands on the value in a single hop, no matter how many million entries sit inside. How can a key become an address? →
A deque refuses to choose between the front and the back; it makes both ends equally cheap. So these twelve tiny programs let you feel that symmetry first, then watch it earn its keep as a self-trimming window, and finally in the deque's signature sliding-window-maximum trick.