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. Here 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. 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. And the whole way through we keep asking the thing 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. You'll use a bounded deque as a self-trimming history, and collapse a sliding-window problem from O(n·k) down to O(n).

Where does refusing to choose an end actually pay off? Picture a print spooler feeding one printer. Ordinary documents line up at the back, and the printer pulls the next job off the front. That's a plain queue. But now a rush job arrives, and it has to jump the line. With a deque you appendleft it onto the front, and the printer grabs it next. Same structure, both ends live: normal work flows in the back, urgent work cuts in at the front, and the worker always pulls from the front. A work-stealing scheduler leans on the same trick. A thread takes tasks off its own front, while idle threads steal from its back. Any time "add here, remove there" points at two different ends, you want a deque.

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. An 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. That is the front-shift we dissected when we first took the list apart. Watch what it 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 is roughly a thousandfold gap, and it widens with n because the list is quietly O(n²).

Where does that O(n²) actually come from? Draining from the front, the first pop(0) shifts the other 49,999 references down a slot, the next shifts 49,998, and so on down to a final lonely shift. Add that staircase up: 50,000 × 49,999 ÷ 2 ≈ 1.25 billion reference moves for a single drain. The deque does the same job in 50,000 cursor steps, one per item. That is why the gap is not a constant factor but a widening canyon.

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.

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 weighs 56 bytes, and ~344 bytes if it carries an ordinary __dict__. Worse, 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 a growth means reallocating the whole block.

Why does that scattering matter so much? The CPU doesn't read one byte from RAM at a time. It pulls a whole cache line, 64 bytes, into fast on-chip memory and hopes you'll use the neighbours next. When your data sits shoulder to shoulder, the next item is already in cache, and the read costs a few CPU cycles. When each item is a separate heap allocation somewhere random in RAM, the neighbour is useless, and the CPU stalls waiting on main memory, on the order of a hundred cycles for the miss. That's the pointer-chasing tax: not the pointer hop itself, but the stall behind it, paid on every single node. Multiply it across a million items and the node-per-item list loses badly, even though its big-O looks identical.

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. You get the linked list's flexible ends and keep most of the array's locality.

Let's make the layout concrete with a count. Each block holds 64 references, so a deque of 200 items spans about ⌈200 ÷ 64⌉ = 4 blocks. Four blocks means only three links between them, so reaching the far end is at most three pointer hops, not two hundred. Compare the two extremes. The node-per-item list would need 200 separate allocations and 199 links to cross. A single array would hold all 200 in one slab, but a front insert would shove all 200 references over by one. The deque sits in between by design: 64-wide runs you can stream through, stitched by a handful of links you can grow cheaply at either end.

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. That is 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 = s

Line by line: the first print confirms the 760-byte floor. Then we append 259 items and print only on the steps, the moments getsizeof changes. The real output was jumps at n = 33, 97, 161, 225, each adding exactly 528 bytes, which is one block. Why the first jump at 33, not 64? Because a fresh deque drops its first item in the middle of the block. An append-only run fills the right half, about ~32 cells, before it needs a second block. The steady-state 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.

So why 64, and not 8 or 1,024? The number balances two costs that pull in opposite directions. Make a block too small and you pay for a fresh link, and a possible allocation, far too often. Make it too large and even a two-item deque drags a full block of empty cells at each end. At 64, the per-item bookkeeping falls to a fraction of a byte while the wasted slack stays small. That sweet spot is the constant BLOCKLEN that CPython bakes in.

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 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. It doesn't matter whether the deque holds ten items or ten million, so the cost is O(1). Only when rightindex already sits on the block's last cell, every 64th append, does more happen. It grabs a block from the freelist, links it on the right, and resets the cursor to the new block's start. That is 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.

One detail in that derivation is worth pausing on: the freelist. Asking the operating system for memory is expensive, far pricier than a pointer write, so you don't want to do it on every 64th append. Instead CPython keeps a small stash of recently emptied blocks. When a pop drains a block, that block isn't handed back to the OS. It's parked on the freelist. When the next append needs a fresh block, it takes one off the stash instead of allocating. So a workload that churns near a block boundary, appending and popping around the same length, recycles the same blocks over and over and almost never touches the allocator. That's how the O(1) stays a cheap O(1) in practice, not just on paper.

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, and all four constant-time moves — no shifting, no reallocation, no walking. The widget below makes that claim literal, so drive it and watch the two cursors crawl outward as you push and inward as you pop. Keep an eye out for the exact moment a full block fills and 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 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 and indexes inside. That walk is proportional to how deep i sits, so it is O(n).

I measured it on a million-item deque. Reaching dq[n//2] took about 47 microseconds, while list[n//2] took about 0.17 microseconds — roughly 280× slower, and that gap only widens as n grows. This is not a small constant you can shrug off; it is a different complexity class altogether. The deque is a specialist for the ends, and paying for the middle is exactly how you misuse it.

It helps to count the hops. To land on dq[500000] in that million-item deque, the walk starts at the nearer end and crosses one block at a time, 64 items per hop. That is about 500000 ÷ 64 ≈ 7,800 hops before it arrives. Each hop follows a next pointer into a block sitting elsewhere in memory, so most of them are a fresh cache miss. Seven-odd thousand misses is where those 47 microseconds live, while a list skips every one of them with a single address computation.

INPUTfrom collections import deque

up_next = deque(["Levels", "Strobe"])

up_next.append("Faded")            # BACK  - "add to queue"
up_next.appendleft("Encore")       # FRONT - "play next"
print(list(up_next))

print("plays now  ->", up_next.popleft())   # FRONT out
print("undo add   ->", up_next.pop())       # BACK  out
print(list(up_next))

up_next.rotate(1)                  # in place, right by 1 - and returns None
print("rotate(1)  ->", list(up_next))
print("rotate returns:", up_next.rotate(-1))
print("rotate(-1) ->", list(up_next))

up_next.extend(["A", "B"])         # bulk, at the back, in order
up_next.extendleft(["Y", "Z"])     # bulk, at the front - ONE AT A TIME, so it flips
print("after extends:", list(up_next))

history = deque(maxlen=3)          # a self-trimming window
for page in ["home", "docs", "api", "faq", "blog"]:
    history.append(page)
print("last 3 pages:", list(history), "| maxlen =", history.maxlen)

# both ends at once: a palindrome check that never slices
def is_pal(s):
    d = deque(s)
    while len(d) > 1:
        if d.popleft() != d.pop():   # one from each end, O(1) each
            return False
    return True
print("is_pal('racecar'):", is_pal("racecar"), "| is_pal('deque'):", is_pal("deque"))

OUTPUT['Encore', 'Levels', 'Strobe', 'Faded']
plays now  -> Encore
undo add   -> Faded
['Levels', 'Strobe']
rotate(1)  -> ['Strobe', 'Levels']
rotate returns: None
rotate(-1) -> ['Levels', 'Strobe']
after extends: ['Z', 'Y', 'Levels', 'Strobe', 'A', 'B']
last 3 pages: ['api', 'faq', 'blog'] | maxlen = 3
is_pal('racecar'): True | is_pal('deque'): False

"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. That gives you a rolling "last N" in one line: newest kept, oldest evicted for free. There's no manual trimming, and crucially no O(n) pop(0).

This is the shape behind a lot of everyday plumbing. A live dashboard that shows the last 100 latency samples is a deque(maxlen=100). Each new measurement appends, the hundred-and-first push quietly drops the oldest, and the window slides forward on its own. A chat client keeping the last 50 messages in memory works the same way. So does a moving average: sum the deque and divide by its length, and because the oldest sample fell off for free, you never pay to trim. Without maxlen you'd write the eviction by hand with pop(0), and that's the exact O(n) front-shift we started the chapter warning against.

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.

Here is the payoff made concrete. Say you keep the last three sensor readings in a deque(maxlen=3) holding [10, 20, 30], whose mean is 20. A new reading of 40 arrives, you append it, and the deque becomes [20, 30, 40] — the oldest value, 10, fell off the far end for free. Now the mean is 30, and you never paid an O(n) shift to drop the stale sample. That is a moving average that trims itself, and it is why sensor feeds and dashboards reach for a bounded 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 running sum current in O(1), adding the value that entered and subtracting the one that left. Maximum is nastier. When the current maximum slides out of the window, there is no cheap way to recover the next one, and re-scanning the whole window is O(k) — which makes the entire pass O(n·k). The fix is a monotonic deque, and it is the deque's signature move.

Before the mechanism, sit with the one idea that makes it work. Say a new value x enters at index j, and some earlier index p still in the deque holds a value ≤ x. Then p is finished. It lies to the left of j, so every future window that still holds p also holds the newer, at-least-as-big x. The older value can never win as a maximum again, so we discard it the instant x arrives. That one observation is why the deque stays short and the whole pass stays O(n).

Keep a deque of indices whose values are strictly decreasing from front to back. For each new element, 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, 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.

Let's watch the invariant hold on a real array. Take a = [1, 3, -1, -3, 5, 3, 6, 7] with a window of k = 3, and track the deque of indices. We push index 0, value 1. At index 1, value 3, the newcomer beats the tail value 1, so we evict index 0 and push 1. The deque now reads [1]. At index 2, value -1, the newcomer doesn't beat 3, so it just joins the back: [1, 2]. The window is full now, and the front value a[1] = 3 is the first maximum. Push to index 4, value 5, after index 3 (value -3) has joined the back. Now 5 beats the tail values -3, -1, and 3 in turn, so every index pops and 5 stands alone at the front. Each index entered once and left once, and the front was always the answer. That's the O(n) you were promised, traced by hand.

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, keeping 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 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]): 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, 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. A palindrome check pops a character off each end and compares the pair. Balanced-parenthesis checks and BFS frontiers — the breadth-first search we walked through in Volume 3 — lean on the same two-ended access. So does rotate(k), which quietly powers round-robin scheduling. Run deque([1,2,3,4,5]).rotate(2) and you get [4,5,1,2,3] in O(k), no reshuffle.

Why is that rotate O(k) rather than O(n)? Rotating right by k only has to move k references from one end to the other — pop from the back, appendleft onto the front, k times over. The other n − k items never move. The two cursors do all the walking, which is why round-robin scheduling can advance a whole rota by a step and touch only the few items at the edges.

from collections import deque
import random

class RollingMean:
    """Mean of the last N readings. The window trims itself."""
    def __init__(self, n):
        self._w = deque(maxlen=n)     # the ENTIRE eviction policy

    def add(self, x):
        self._w.append(x)             # the (n+1)th append drops the oldest, O(1)
        return self.mean

    @property
    def mean(self):
        return sum(self._w) / len(self._w) if self._w else None

    def __len__(self):
        return len(self._w)


def naive_means(xs, n):
    """The version with no deque - kept honest by slicing a plain list."""
    seen, out = [], []
    for x in xs:
        seen.append(x)
        w = seen[-n:]                 # the last n, recopied every single time
        out.append(sum(w) / len(w))
    return out


readings = [12.5, 13.0, 11.75, 14.25, 13.5, 12.0, 15.5, 11.0]
r = RollingMean(3)
mine = [r.add(x) for x in readings]
theirs = naive_means(readings, 3)

for x, a, b in zip(readings, mine, theirs):
    print(f"  add {x:6}  ->  rolling {a:.6f}   naive {b:.6f}   {'ok' if a == b else 'DIFFER'}")
print("identical:", mine == theirs)
print("window after 8 readings:", list(r._w), "| len", len(r))

#   add   12.5  ->  rolling 12.500000   naive 12.500000   ok
#   add   13.0  ->  rolling 12.750000   naive 12.750000   ok
#   add  11.75  ->  rolling 12.416667   naive 12.416667   ok
#   add  14.25  ->  rolling 13.000000   naive 13.000000   ok
#   add   13.5  ->  rolling 13.166667   naive 13.166667   ok
#   add   12.0  ->  rolling 13.250000   naive 13.250000   ok
#   add   15.5  ->  rolling 13.666667   naive 13.666667   ok
#   add   11.0  ->  rolling 12.833333   naive 12.833333   ok
# identical: True
# window after 8 readings: [12.0, 15.5, 11.0] | len 3


# THE TWIST - the "clever" O(1) incremental version.
class DriftingMean:
    def __init__(self, n):
        self._w, self._total = deque(maxlen=n), 0.0
    def add(self, x):
        if len(self._w) == self._w.maxlen:
            self._total -= self._w[0]      # subtract the one about to fall off
        self._w.append(x)
        self._total += x
        return self._total / len(self._w)

random.seed(7)
stream = [random.random() * 1e6 for _ in range(200_000)]
d, e = DriftingMean(50), RollingMean(50)
for x in stream:
    a, b = d.add(x), e.add(x)
print(f"after 200,000 readings: incremental {a!r}")
print(f"                        re-summed   {b!r}")
print("equal:", a == b, "| absolute gap:", abs(a - b))

# after 200,000 readings: incremental 474253.99073524325
#                         re-summed   474253.9907352406
# equal: False | absolute gap: 2.6775524020195007e-09

# WHAT JUST HAPPENED. The deque half is exact: maxlen dropped the right
# value at the right moment, 200,000 times, with no bookkeeping from us.
# The arithmetic half is not. Every float add and subtract rounds to the
# nearest representable number, and the running total carries all 200,000
# of those roundings forward forever. The re-summed version throws its
# total away and rebuilds it from the 50 values actually in the window,
# so it can only ever be 50 roundings deep. After 200,000 readings the two
# have drifted apart by ~2.7e-09 - tiny, real, and growing.
#
# So which do you ship? Neither, blindly:
#   - re-summing is O(n) per reading but its error never accumulates. For
#     a window of 50 that is 50 adds - nothing. Default to this.
#   - the incremental total is O(1) and pays for it in drift. Reach for it
#     only when n is large enough that O(n) hurts, and then either use
#     math.fsum for the periodic rebuild or re-sum every few thousand
#     readings to reset the error.
# The deque was never the risky part. The float was.

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? →