deque for O(1) Append and Pop on Both Ends
A `collections.deque` (double-ended queue) supports O(1) `append`, `appendleft`, `pop`, and `popleft`, while a Python `list` is O(n) for left-side operations. This snippet covers the deque-as-queue pattern that powers BFS, the deque-as-rolling-buffer pattern with `maxlen`, and the rotate trick for cyclic processing.
920 views
9
from collections import deque
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': []}
def bfs(start):
visited = {start}
order = []
queue = deque([start])
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if nxt in visited:
continue
visited.add(nxt)
queue.append(nxt)
return order
print(bfs('A')) # ['A', 'B', 'C', 'D', 'E']BFS needs a FIFO queue: append to the end, popleft from the front. A Python list supports append in O(1) but pop(0) in O(n) because every other element must shift. deque makes both O(1), which is what makes a BFS on a million-node graph feasible. Always reach for deque when the algorithm needs a real queue; using a list 'because it works' is one of the most common Python performance bugs in graph code.
from collections import deque
last_5_temps = deque(maxlen=5)
for t in [21.1, 21.4, 21.7, 22.0, 22.3, 22.6, 22.4, 22.1]:
last_5_temps.append(t)
print(list(last_5_temps)) # [22.0, 22.3, 22.6, 22.4, 22.1]
print(round(sum(last_5_temps) / len(last_5_temps), 2)) # 22.28Setting maxlen=N on a deque turns it into a fixed-size ring buffer: appends past the limit silently drop the oldest entry from the other end. This is the cleanest implementation of 'last N values' for monitoring dashboards, moving averages, and chat-history caches. Both appendleft and append honour maxlen. The deque is bounded, so memory usage stays predictable regardless of how long the producer runs.
from collections import deque
seats = deque(['Ada', 'Bo', 'Cal', 'Di', 'Eve'])
seats.rotate(1) # rotate right by 1
print(list(seats)) # ['Eve', 'Ada', 'Bo', 'Cal', 'Di']
seats.rotate(-2) # rotate left by 2
print(list(seats)) # ['Bo', 'Cal', 'Di', 'Eve', 'Ada']
# Useful for round-robin schedules
schedule = deque(['mon', 'tue', 'wed', 'thu', 'fri'])
for _ in range(5):
today = schedule[0]
schedule.rotate(-1)
print(today)rotate(n) cyclically shifts every element: positive n moves entries to the right (with the tail wrapping to the front), negative n moves them to the left. Both directions are O(min(n, len)) which is essentially constant for the typical small rotation. This is the right primitive for round-robin scheduling, calendar shifts, and any sliding-window structure where the boundary is a wrap-around. Slicing a list to achieve the same effect would copy the whole list every iteration.