deque¶

A Python list is brilliant at the end — append and pop are fast — but slow at the front. Inserting or removing at index 0 forces every other element to shift along, which costs time proportional to the list's length. When you need a queue, a buffer, or anything that works at both ends, collections.deque ("deck", a double-ended queue) gives you fast operations at either end.

Both ends are fast¶

deque adds appendleft and popleft to the familiar append and pop. All four are O(1) — constant time regardless of size.

In [ ]:

from collections import deque

d = deque([1, 2, 3])
d.append(4)         # add on the right
d.appendleft(0)     # add on the left
print(d)            # deque([0, 1, 2, 3, 4])

print(d.pop())      # 4  — remove from the right
print(d.popleft())  # 0  — remove from the left
print(d)            # deque([1, 2, 3])

from collections import deque d = deque([1, 2, 3]) d.append(4) # add on the right d.appendleft(0) # add on the left print(d) # deque([0, 1, 2, 3, 4]) print(d.pop()) # 4 — remove from the right print(d.popleft()) # 0 — remove from the left print(d) # deque([1, 2, 3])

Why not just use a list?¶

For a stack (work at the end only) a list is perfect. The difference appears at the front: list.pop(0) and list.insert(0, x) are O(n) because everything shifts; deque's left operations are O(1). Over many front operations that's the difference between linear and quadratic time. Here's the gap on a modest workload — the exact numbers vary, but the ratio is the point.

In [ ]:

from collections import deque
import time

N = 50_000

lst = list(range(N))
start = time.perf_counter()
while lst:
    lst.pop(0)          # O(n) each time -> O(n^2) overall
list_time = time.perf_counter() - start

dq = deque(range(N))
start = time.perf_counter()
while dq:
    dq.popleft()        # O(1) each time -> O(n) overall
deque_time = time.perf_counter() - start

print(f'list.pop(0): {list_time:.3f}s   deque.popleft(): {deque_time:.4f}s')
print(f'deque was ~{list_time / deque_time:.0f}x faster here')

from collections import deque import time N = 50_000 lst = list(range(N)) start = time.perf_counter() while lst: lst.pop(0) # O(n) each time -> O(n^2) overall list_time = time.perf_counter() - start dq = deque(range(N)) start = time.perf_counter() while dq: dq.popleft() # O(1) each time -> O(n) overall deque_time = time.perf_counter() - start print(f'list.pop(0): {list_time:.3f}s deque.popleft(): {deque_time:.4f}s') print(f'deque was ~{list_time / deque_time:.0f}x faster here')

A bounded deque with maxlen¶

Give a deque a maxlen and it becomes a fixed-size window: once full, each new item on one end pushes the oldest off the other. This is a ring buffer in one argument — perfect for "the last N things".

In [ ]:

from collections import deque

last_three = deque(maxlen=3)
for n in range(6):
    last_three.append(n)
    print(list(last_three))    # window slides: [0] [0,1] [0,1,2] [1,2,3] [2,3,4] [3,4,5]

print(last_three)              # deque([3, 4, 5], maxlen=3)

from collections import deque last_three = deque(maxlen=3) for n in range(6): last_three.append(n) print(list(last_three)) # window slides: [0] [0,1] [0,1,2] [1,2,3] [2,3,4] [3,4,5] print(last_three) # deque([3, 4, 5], maxlen=3)

Using it as a queue or a stack¶

A deque is the idiomatic FIFO queue: append to add, popleft to take the oldest. (It also works as a stack with append/pop, though a list is fine for that.)

In [ ]:

from collections import deque

queue = deque()
queue.append('first')
queue.append('second')
queue.append('third')

print(queue.popleft())   # 'first'  — oldest out first (FIFO)
print(queue.popleft())   # 'second'
print(queue)             # deque(['third'])

from collections import deque queue = deque() queue.append('first') queue.append('second') queue.append('third') print(queue.popleft()) # 'first' — oldest out first (FIFO) print(queue.popleft()) # 'second' print(queue) # deque(['third'])

rotate, and an extendleft surprise¶

rotate(n) shifts items around the ends — positive n moves them right, negative moves them left. And a gotcha worth knowing: extendleft appends items one at a time on the left, so the result ends up reversed relative to the input.

In [ ]:

from collections import deque

d = deque([1, 2, 3, 4, 5])
d.rotate(2)             # last two wrap to the front
print(d)                # deque([4, 5, 1, 2, 3])
d.rotate(-2)            # and back
print(d)                # deque([1, 2, 3, 4, 5])

e = deque()
e.extendleft([1, 2, 3]) # each is appendleft-ed -> order flips
print(e)                # deque([3, 2, 1])

from collections import deque d = deque([1, 2, 3, 4, 5]) d.rotate(2) # last two wrap to the front print(d) # deque([4, 5, 1, 2, 3]) d.rotate(-2) # and back print(d) # deque([1, 2, 3, 4, 5]) e = deque() e.extendleft([1, 2, 3]) # each is appendleft-ed -> order flips print(e) # deque([3, 2, 1])

Recap¶

• deque gives O(1) append/appendleft/pop/popleft — fast at both ends.
• A list is fine as a stack but slow at the front (pop(0) is O(n)); use deque for queues and front-work.
• maxlen makes a fixed-size sliding window / ring buffer that drops the oldest item automatically.
• It's the natural FIFO queue: append + popleft.
• rotate(n) shifts around the ends; extendleft reverses its input.

Next: namedtuple and friends — named records, plus OrderedDict and ChainMap.