deque Double-Ended Operations

Concepts covered: Stack & Queue

A Python list stores its items as a contiguous row of references. Adding or removing at the end touches the last slot and nothing else. At index 0 the work changes: every other reference shifts over by a slot to open or close the gap at the front.

The insert moved 4 references to make room for 1 item. On a list of 1,000,000 items, a front insert moves 1,000,000 references, and a queue drained with pop(0) pays that again on every call, each a little shorter than the last. Over a whole drain the moves add up:

How a deque avoids the shift

collections.deque, pronounced "deck" and short for double-ended queue, stores items in a chain of fixed-size blocks, 64 references each in CPython, with each block linked to the blocks on both sides. Adding at either end writes into the end block, or links a new block when that one is full. No stored item moves, so a front operation costs the same on 10 items as on 10,000,000.

The methods mirror each other. append and pop work on the right end, and their left-end twins are appendleft and popleft. Predict the last line before you play it, keeping in mind that extendleft adds its items to the front item by item.

from collections import deque

d = deque([1, 2, 3])
print("Initial:", d)

d.append(4)
d.appendleft(0)
print("After appends:", d)

d.pop()
d.popleft()
print("After pops:", d)

d.extend([4, 5])
d.extendleft([-1, -2])
print("After extends:", d)
Initial: deque([1, 2, 3])
After appends: deque([0, 1, 2, 3, 4])
After pops: deque([1, 2, 3])
After extends: deque([-2, -1, 1, 2, 3, 4, 5])

extendleft([-1, -2]) put -1 at the front and then -2 in front of it, so the batch landed reversed. Pass reversed(batch) when its order has to survive.

maxlen: a buffer that forgets

A deque built with maxlen=n never holds more than n items. Adding to a full one drops an item from the opposite end, with no error. That makes it the usual holder for recent history, whether the last few events are retries or readings.

from collections import deque

recent = deque(maxlen=3)
for event in ["e1", "e2", "e3", "e4", "e5"]:
    recent.append(event)
    print(list(recent))

recent.appendleft("e0")
print(list(recent))
['e1']
['e1', 'e2']
['e1', 'e2', 'e3']
['e2', 'e3', 'e4']
['e3', 'e4', 'e5']
['e0', 'e3', 'e4']

The last line shows the rule from the other side: appendleft on a full deque pushed e5 off the right. A rolling average of the last 3 latency readings needs nothing more:

from collections import deque

latencies = [120, 80, 100, 300, 90]
window = deque(maxlen=3)
for ms in latencies:
    window.append(ms)
    print(ms, round(sum(window) / len(window), 1))

Output:

120 120.0
80 100.0
100 100.0
300 160.0
90 163.3

What a deque gives up

Blocks make the ends fast and the middle slower. d[0] and d[-1] read an end block directly, while d[500000] on a 1,000,000-item deque walks block by block from the nearer end. Slicing raises an error:

from collections import deque

d = deque(["a", "b", "c", "d"])
print(d[0], d[-1])
try:
    print(d[1:3])
except TypeError as err:
    print("TypeError:", err)
print(list(d)[1:3])

Output:

a d
TypeError: sequence index must be integer, not 'slice'
['b', 'c']

rotate(-1) moves the front item to the back, which gives a round-robin over workers with no index arithmetic:

from collections import deque

workers = deque(["w1", "w2", "w3"])
for batch in ["b1", "b2", "b3", "b4"]:
    print(batch, "->", workers[0])
    workers.rotate(-1)
b1 -> w1
b2 -> w2
b3 -> w3
b4 -> w1
list
  • Fast append and pop at the end
  • insert(0, x) and pop(0) move every other item
  • Fast lst[i] anywhere, plus slicing
  • Grows without a size limit
deque
  • Fast adds and removes at both ends
  • appendleft and popleft move nothing
  • Fast at the ends, slower toward the middle, no slicing
  • Optional maxlen that drops from the far end

The limit is set once, when the deque is built. d.maxlen reads it back, and assigning to it raises AttributeError, so a buffer that must grow is rebuilt as deque(d, maxlen=new_size). Building from a long iterable applies the rule from the start: deque([1, 2, 3, 4, 5], maxlen=3) keeps [3, 4, 5]. Each item was appended in turn, and the oldest fell off the left as each new one arrived.

What does this program print?

from collections import deque

d = deque([1, 2], maxlen=3)
d.append(3)
d.appendleft(0)
d.append(4)
print(list(d))

About this lesson

This section is part of the Collections: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.