Python deque vs list: Queue Operations and 8 Tested Examples
Use collections.deque for queues that repeatedly add and remove at either end. Use a list when positional access and slicing are central. A deque is a double-ended queue, not a sorted container or a replacement for every list. These eight tested Python examples explain FIFO, bounded history, extendleft, rotation, copying and a breadth-first search trace.
1. Deque vs list: choose by operation
| Operation or need | deque | list |
|---|---|---|
| Add/remove right | append/pop, approximately O(1) | append amortized O(1), pop at end O(1) |
| Add/remove left | appendleft/popleft, approximately O(1) | insert(0,x)/pop(0), O(n) shifting |
| Middle index | Slows to O(n) | O(1) positional access |
| Slicing | Not supported directly | Supported; copying k items costs O(k) |
| Bounded recent history | maxlen with automatic discard | Manage capacity explicitly |
| Sort | sorted produces a separate list | sort method or sorted |
The complexity descriptions are the documented deque behavior and typical CPython list costs, not timing promises. Hashing, copying or processing the stored objects has its own cost. Both containers allow repeated elements and keep sequence order. Neither makes nested objects independent copies.
2. Trace a FIFO queue
| Step | Operation | Returned value | Queue afterward |
|---|---|---|---|
| 0 | deque([A,B]) | New deque | [A,B] |
| 1 | append(C) | None | [A,B,C] |
| 2 | popleft() | A | [B,C] |
3. Eight tested examples
Example 1: A FIFO queue uses opposite ends
from collections import deque
q = deque(["A", "B"])
q.append("C")
print(q.popleft())
print(list(q))
q.appendleft("X")
print(q.pop())
print(list(q))Output
A ['B', 'C'] C ['X', 'B']
append adds on the right; popleft removes on the left. That pair implements FIFO. append and pop on the same right end implement a stack. appendleft and pop form FIFO from the other direction when used consistently.
Example 2: An empty removal raises IndexError
from collections import deque
q = deque()
try:
q.popleft()
except IndexError:
print("empty queue")
q.append(0)
while q:
print(q.popleft())
print(bool(q))Output
empty queue 0 False
Use the container truth value to test whether a single-threaded queue has elements. A zero stored inside is still an element; q is True until it is empty. An empty pop or popleft raises IndexError. This check is not an atomic check-and-remove operation across threads.
Example 3: extendleft reverses the input order
from collections import deque
q = deque([3, 4])
q.extendleft([1, 2])
print(list(q))
r = deque([3, 4])
r.extendleft(reversed([1, 2]))
print(list(r))Output
[2, 1, 3, 4] [1, 2, 3, 4]
Each incoming element is inserted at the left. Inserting1 then2 therefore puts2 before1. Reverse a finite sequence first when the desired prefix is1,2. This is an insertion-order effect, not sorting.
Example 4: A bounded deque silently discards the opposite end
from collections import deque
q = deque([1, 2, 3], maxlen=3)
q.append(4)
print(list(q))
q.appendleft(0)
print(list(q))
try:
q.insert(1, 9)
except IndexError:
print("full bounded deque")
print(q.maxlen)Output
[2, 3, 4] [0, 2, 3] full bounded deque 3
Right appends on a full deque discard leftmost items; left appends discard rightmost items. insert is different: it raises IndexError if insertion would exceed maxlen. A bounded deque is useful for recent history, but dangerous as a work queue if dropping tasks is unacceptable.
Example 5: Rotation is not reversal
from collections import deque
q = deque([1, 2, 3, 4])
q.rotate(1)
print(list(q))
q.rotate(-2)
print(list(q))
q.reverse()
print(list(q))
print(q[0], q[-1])Output
[4, 1, 2, 3] [2, 3, 4, 1] [1, 4, 3, 2] 1 2
Positive rotation moves items toward the right end; negative rotation moves them left. reverse flips the sequence itself. For a nonempty deque, one right rotation is equivalent to appendleft(pop()), but rotating an empty deque is harmless while pop would fail.
Example 6: Copying the container does not copy nested objects
from collections import deque
original = deque([[1], [2]])
copy = original.copy()
copy[0].append(9)
copy.append([3])
print(list(original))
print(list(copy))Output
[[1, 9], [2]] [[1, 9], [2], [3]]
copy creates another deque container, but its elements are still references to the same nested lists. The new third element belongs only to copy. A deliberate deep-copy policy is a separate decision, just as with ordinary lists.
Example 7: Breadth-first search marks nodes when enqueued
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"],
"C": ["D"], "D": []}
q = deque(["A"])
distance = {"A": 0}
order = []
while q:
node = q.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
q.append(neighbor)
print(order)
print(distance)Output
['A', 'B', 'C', 'D']
{'A': 0, 'B': 1, 'C': 1, 'D': 2}The distance dictionary doubles as a visited set. Marking a node as soon as it is enqueued prevents D being queued twice through B and C. FIFO processes layers in order. These distances count edges in an unweighted graph; this is not a weighted shortest-path algorithm.
Example 8: A zero-length deque retains no elements
from collections import deque
q = deque([1, 2], maxlen=0)
q.append(3)
q.extend([4, 5])
print(list(q))
print(q.maxlen)
try:
q.popleft()
except IndexError:
print("nothing retained")Output
[] 0 nothing retained
maxlen0 is legal: input is consumed but no elements remain. A negative maxlen is invalid. maxlen is read-only after construction; create a new deque if the capacity requirement changes.
4. BFS: follow layers, not weights
In Example7, A starts at distance0. Removing A adds B and C at distance1. Removing B adds D at distance2. When C sees D, D is already in distance, so it is not enqueued again. Finally D leaves the queue. The order is A,B,C,D because this graph lists B before C; another neighbor order can change the traversal order while preserving shortest edge-count distances.
| Removed node | Newly queued | Queue afterward |
|---|---|---|
| A | B,C | [B,C] |
| B | D | [C,D] |
| C | None; D already visited | [D] |
| D | None | [] |
For an adjacency-list graph, BFS visits each reachable vertex and examines each outgoing edge once. Its usual cost is O(V+E) with constant-average visited-key lookup, where V and E refer to the visited subgraph. The queue and visited data require O(V) entries. The example assumes every referenced node is a graph key. A bounded deque must not silently discard BFS frontier nodes: dropping one can lose reachable vertices and invalidate distances.
5. Bounded history is not task backpressure
A deque with maxlen keeps at most that many recent items. Appending to a full deque discards an item instead of blocking. This is useful for a sliding history of observations when the intended contract is to forget old values. It is wrong when every submitted task must eventually run.
Individual deque end appends and pops are documented as thread-safe, but a sequence of operations is not automatically atomic. Checking if q then removing can race with another consumer. For synchronized worker handoff, blocking waits and capacity backpressure, consider queue.Queue instead of assuming maxlen provides a blocking queue. This lesson uses single-threaded examples.
6. Common mistakes and fixes
| Mistake | Fix |
|---|---|
| Use list.pop(0) repeatedly for a large FIFO | Use deque.popleft when end operations are the workload |
| Expect extendleft([1,2]) to preserve prefix order | Trace each insertion; reverse the input when appropriate |
| Set maxlen on a work queue to avoid growth | Do not silently drop work; choose an explicit overflow policy |
| Assume every deque index is O(1) | End access is fast, middle access can be linear |
| Assign q = q.append(x) | append mutates and returns None; keep the container name |
| Use bounded deque for BFS frontier | Use an unbounded deque or an explicit safe memory policy |
| Assume copy clones nested items | Separate shallow container copying from deep-copy requirements |
7. Practice and exam Q&A
append on the right and popleft on the left. Consistently using appendleft and pop implements FIFO from the opposite direction.
None. It changes the existing deque.
Later elements shift left. In typical CPython, that operation is linear in the number of remaining elements.
The deque contains [2,1,3,4]. extendleft returns None.
It drops a corresponding item from the opposite end to stay within maxlen.
No. An insertion that would exceed maxlen raises IndexError.
No. Appends discard old entries on overflow. Use a suitable synchronized queue when blocking/backpressure is required.
It prevents the same node being queued by several parents before it is processed.
No. Its distances count edges in an unweighted graph. Weighted edges need an algorithm matched to their constraints.
No. maxlen0 is legal but retains no elements. Empty removal still raises IndexError.
8. Revision tasks with checks
Predict deque([10,20,30], maxlen=3) after append(40), then appendleft(5). Answers: [20,30,40], then [5,20,30]. Explain which item leaves at each step. Next rotate that final deque once right: [30,5,20]. Reversing it instead would give [30,20,5].
For the BFS graph in Example7, swap A's neighbor order to C,B. Traversal becomes A,C,B,D; distances remain A:0, C:1, B:1, D:2. Add an isolated node E and explain why it is absent from a traversal starting at A. Finally make A's neighbors repeat B and confirm that marking on enqueue still processes B only once.
Before choosing a container, write the actual workload: ends or middle, repeated values or unique membership, silent discard or guaranteed delivery, shallow references or independent data. Then test empty input, full capacity and one-element cases before scaling.
Official sources and related lessons
- Python collections: deque operations, bounded behavior and costs
- Python queue: synchronized queues and blocking operations
- Python wiki: typical CPython container costs
Continue with dict vs set and visited-key lookup, sorting and stable ties, or the Exam Notes hub. These are universal learning and exam-practice notes, not an official university syllabus or paper.
Comments
Post a Comment