collections.deque

collections.deque

collections.deque (pronounced “deck”) is a list-like sequence optimized for fast appends and pops from both ends — O(1) at the front and the back. A plain list is only fast (O(1) amortized) at the end; operations at the front are O(n) because every remaining element has to shift.

              LEFT end                     RIGHT end
               ┌────┐    ┌────┐    ┌────┐
appendleft ──► │ A  │ ←→ │ B  │ ←→ │ C  │ ◄── append
popleft    ◄── │    │    │    │    │    │     pop ──►
               └────┘    └────┘    └────┘

Before this feature

queue = [1, 2, 3]

queue.insert(0, 0)   # O(n) -- every element shifts right to make room
first = queue.pop(0)  # O(n) -- every remaining element shifts left

After this feature

from collections import deque

queue = deque([1, 2, 3])

queue.appendleft(0)   # O(1)
first = queue.popleft()  # O(1)

queue.append(4)        # O(1) -- still fast at the right end too
last = queue.pop()      # O(1)

print(queue)  # deque([1, 2, 3, 4])

# A common real use: a sliding window / recent-history buffer
recent = deque(maxlen=3)   # bounded — oldest item auto-evicted once full
for i in range(5):
    recent.append(i)
print(recent)  # deque([2, 3, 4], maxlen=3)

Why this is better

• O(1) at both ends: list.insert(0, x) and list.pop(0) are O(n) because the whole list shifts; deque.appendleft/popleft are O(1) because a deque is a doubly-linked block structure, not a single contiguous array.
• Built-in bounded buffer: deque(maxlen=N) automatically drops from the opposite end once full — a ready-made “keep the last N items” structure without manual trimming.
• Standard tool for queues and BFS: implementing a FIFO queue or breadth-first search’s frontier with a plain list and pop(0) is a classic performance mistake; deque is the correct structure for both.

How it works internally

Python’s deque is implemented as a doubly-linked list of fixed-size blocks (not a simple linked list of individual nodes) — each block holds a small array of elements (64 by default). Growing either end allocates a new block instead of reallocating the whole structure, which is what gives both ends O(1) amortized cost.

  Block 0          Block 1          Block 2
┌──────────┐    ┌──────────┐    ┌──────────┐
│ [_,_,A,B]│◄──►│ [C,D,E,F]│◄──►│ [G,H,_,_]│
└──────────┘    └──────────┘    └──────────┘
 ▲ left end                       right end ▲

Deque vs. list — performance

Operation          list        deque
──────────────     ──────      ──────
append (right)     O(1)*       O(1)
pop (right)        O(1)        O(1)
insert (left)      O(n) ⚠️     O(1) ✅
pop (left)         O(n) ⚠️     O(1) ✅
index access [i]   O(1) ✅     O(n) ⚠️
slicing [a:b]      O(k) ✅     ❌ not supported
len()              O(1)        O(1)
contains (in)      O(n)        O(n)

* O(1) amortized — occasional resize is O(n)

Core methods

Method	Description	Time
append(x)	Add x to the right	O(1)
appendleft(x)	Add x to the left	O(1)
pop()	Remove and return from right	O(1)
popleft()	Remove and return from left	O(1)
extend(iterable)	Extend right from iterable	O(k)
extendleft(iterable)	Extend left (reverses order)	O(k)
rotate(n)	Rotate n steps right (negative = left)	O(n)
clear()	Remove all elements	O(n)
count(x)	Count occurrences of x	O(n)
index(x)	Find first position of x	O(n)
insert(i, x)	Insert at position i	O(n)
remove(x)	Remove first occurrence of x	O(n)

Use cases

Queue (FIFO)

Use append to enqueue and popleft to dequeue. Never use list.pop(0) for this — it’s O(n).

queue = deque()
queue.append("task-A")
queue.append("task-B")
queue.popleft()  # "task-A" — processed in order

Breadth-first search

BFS requires a queue. Using list.pop(0) in BFS makes it O(n²); deque.popleft() keeps it O(V + E).

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

Sliding window

maxlen automatically drops old items as new ones arrive — useful for a moving average or “last N events” buffer:

def moving_average(data, window_size):
    window = deque(maxlen=window_size)
    averages = []
    for value in data:
        window.append(value)
        averages.append(sum(window) / len(window))
    return averages

print(moving_average([1, 2, 3, 4, 5, 6], 3))
# [1.0, 1.5, 2.0, 3.0, 4.0, 5.0]

Rotate

rotate(n) shifts all elements n positions to the right (negative = left) — useful for round-robin scheduling and circular buffers:

d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)   # deque([4, 5, 1, 2, 3])

C# equivalent

Python	C# equivalent	Notes
deque (general)	LinkedList<T>	Doubly-linked, O(1) at both ends
deque as queue	Queue<T>	Enqueue/Dequeue → append/popleft
deque as stack	Stack<T>	Push/Pop → append/pop
deque(maxlen=n)	Queue<T> + manual trim	No built-in bounded queue in C#

Key notes / edge cases

• deque does not support fast indexed access into the middle — deque[500] is O(n), unlike list[500] which is O(1). Use a deque when you mostly push/pop from the ends, and a list when you need random access by index.
• deque does not support slicing (d[1:3] raises TypeError) — convert to a list first (list(d)[1:3]) if you need a slice.
• extendleft reverses order: deque([1,2,3]).extendleft([4,5,6]) gives deque([6, 5, 4, 1, 2, 3]), not [4, 5, 6, 1, 2, 3], because each appendleft shifts existing items right one at a time.
• deque(maxlen=N) silently discards the oldest item from the opposite end when a new item is added past capacity — there’s no error, so an unintended maxlen can quietly lose data if you’re not expecting the eviction.
• deque is thread-safe for individual append/pop operations from either end (an implementation detail of CPython that many use for simple producer/consumer patterns), though it’s not a substitute for proper synchronization in more complex cases like check-then-pop.

Quick practice

1. What’s the time complexity of list.pop(0) versus deque.popleft()?

   Answer

   `list.pop(0)` is `O(n)` (every remaining element shifts); `deque.popleft()` is `O(1)`.

2. Why is deque a poor choice if you need frequent random access by index?

   Answer

   Indexed access into the middle of a `deque` is `O(n)`, unlike a `list`'s `O(1)` — `deque` is optimized for the ends, not the middle.

3. What happens when you append() to a deque(maxlen=3) that already has 3 items?

   Answer

   The oldest item (at the opposite end) is automatically and silently discarded to make room — no error is raised.