A list can represent a queue, a priority queue, or a sorted table. That does not make it the right implementation of all three. Container choice is less about what data is than about which operations the workload repeats.

Three standard-library tools cover important shapes that a plain list handles awkwardly:

  • collections.deque makes both endpoints cheap;
  • heapq keeps only the next priority cheaply available;
  • bisect searches boundaries in an already sorted sequence.

None is a universally faster list. A deque gives up cheap middle indexing. A heap gives up globally sorted iteration. Bisection accelerates the search for an insertion point, not the insertion itself. This tutorial makes those tradeoffs visible through runnable experiments.

Version note. All experiments were verified on 64-bit CPython 3.14.7. Max-heap functions with _max suffix require Python 3.14. Public behavior comes from the Python library documentation; deque blocks, block sizes, byte counts, and measured ratios are CPython details that may vary by version, build, platform, and implementation.

Start with the workload

Before choosing a container, write down the dominant operation:

| Workload | Usually choose | Cheap operation you are buying | Main cost you accept | | --- | --- | --- | --- | | stack, random access, batch sort | list | right-end append/pop, indexing | left-end changes shift references | | FIFO, sliding window, work stealing | deque | append/pop at either endpoint | middle access and insertion | | repeatedly take smallest/largest | heapq over a list | peek O(1), push/pop O(log n) | arbitrary lookup, sorted traversal | | many range/boundary queries, few writes | sorted list + bisect | search O(log n) | insertion remains O(n) | | exact key lookup | dict or set | expected O(1) membership | no range ordering |

Complexities summarize growth, not elapsed time. Small lists often win because their representation is compact and their operations are highly optimized. Measure the real workload only after selecting structures whose growth behavior makes sense.

The operation mix matters as much as asymptotic notation. A service might enqueue thousands of jobs for every priority change; an in-memory index might answer a million boundary queries between bulk refreshes. Those systems should not choose the same representation merely because both hold ordered records. Include construction, mutation, querying, and teardown when modeling the cost. Also account for semantics: automatic eviction, stable ties, and duplicate boundaries can eliminate application code and entire classes of bugs.

Deque: pay for endpoints, not positions

Experiment 1: the same FIFO semantics, different movement

A list queue works correctly, but every pop(0) moves all remaining references left. A deque removes from its left endpoint without shifting the rest.

from collections import deque
from timeit import timeit


n = 20_000
list_time = timeit(
    "while q: q.pop(0)",
    setup=f"q = list(range({n}))",
    number=1,
)
deque_time = timeit(
    "while q: q.popleft()",
    setup=f"from collections import deque; q = deque(range({n}))",
    number=1,
)

print(list_time > deque_time)
print(list(deque([1, 2, 3])) == [1, 2, 3])

Both lines print True in the test environment. The first result, not its exact ratio, is the useful observation. As n grows, repeated front deletion makes the list workload quadratic in total shifted references; deque endpoint removals remain approximately constant-time each.

Library guarantee. The collections documentation promises thread-safe, memory-efficient appends and pops from either side with approximately O(1) performance. It explicitly contrasts these with the O(n) movement of list.pop(0) and list.insert(0, value).

Experiment 2: both ends are first-class

Deque operations are deliberately symmetric. This makes one container useful for breadth-first search, producer/consumer queues, and algorithms that sometimes promote work to the front.

Pyodide / WebAssembly
from collections import deque


work = deque(["parse", "index"])
work.append("publish")
work.appendleft("urgent-fix")

print("[result] left endpoint item:", work.popleft())
print("[result] right endpoint item:", work.pop())
print("[state] remaining deque:", list(work))

urgent-fix
publish
['parse', 'index']

Individual deque endpoint methods are atomic in CPython and documented as thread-safe. That does not make a multi-step protocol atomic: if queue: queue.popleft() can race between the check and removal. Use queue.Queue when blocking, task tracking, or coordinated multi-thread behavior is required.

Why CPython uses blocks

A deque is not a linked list with one allocation per value, and it is not one resizable contiguous array. CPython 3.14 links fixed-length blocks of object pointers. Left and right indexes identify the occupied range in the endpoint blocks. Appending usually advances one index; crossing a boundary attaches another block. Popping can release or cache a now-empty endpoint block.

This hybrid avoids shifting the whole sequence and avoids a separate link allocation for every element. It also explains the access profile: an endpoint is immediately available, while reaching the middle may require walking across blocks from the nearer end.

Experiment 3: observe allocation steps, carefully

sys.getsizeof() can reveal block-shaped growth without exposing private fields:

import sys
from collections import deque


values = deque()
previous = sys.getsizeof(values)
changes = []

for value in range(200):
    values.append(value)
    current = sys.getsizeof(values)
    if current != previous:
        changes.append((len(values), current - previous))
        previous = current

print(changes[:3])
print(all(delta > 0 for _, delta in changes))

On the tested CPython build, the first line was [(33, 528), (97, 528), (161, 528)]; the second was True. A new deque starts around the center of its first block, leaving room to grow in either direction, so right-only growth reaches a boundary before 64 appends. These exact lengths and sizes are observations, not API promises. getsizeof() is shallow and does not include referenced objects.

Experiment 4: endpoint indexing is not middle indexing

The docs specify O(1) indexed access at both ends and O(n) access in the middle. A list provides direct positional access throughout.

from collections import deque
from timeit import timeit


n = 100_000
d = deque(range(n))
items = list(range(n))

edge = timeit("d[0]; d[-1]", globals=globals(), number=50_000)
middle = timeit("d[n // 2]", globals=globals(), number=50_000)
list_middle = timeit("items[n // 2]", globals=globals(), number=50_000)

print(middle > edge)
print(middle > list_middle)

Both comparisons were True in the test environment. Timing noise and constants matter, but the design lesson does not: if arbitrary positions dominate, keep the list. A deque is a queue that happens to support subscripting, not a faster general sequence.

Experiment 5: bounded history encodes eviction

maxlen turns retention policy into a container invariant. Appending to a full deque discards from the opposite end.

Pyodide / WebAssembly
from collections import deque


recent = deque(maxlen=3)
for event in ("connect", "read", "write", "close"):
    recent.append(event)

print("[state] retained bounded history:", list(recent))
print("[check] history capacity:", recent.maxlen)

['read', 'write', 'close']
3

That is ideal for tail buffers and sliding windows. Notice a subtle difference: append() evicts automatically, but insert() into a full bounded deque raises IndexError. Also, extendleft(iterable) repeatedly appends left, so it reverses the iterable's visible order.

Heapq: maintain one winner, not a total order

heapq is not a heap container class. It is a set of algorithms that mutate a normal list. In a min-heap, every parent at index k is no greater than children at 2*k + 1 and 2*k + 2. Therefore the minimum is always at index zero. Siblings and distant subtrees need not be ordered.

Experiment 6: a heap is not a sorted list

Pyodide / WebAssembly
import heapq


heap = [9, 1, 7, 3, 2, 8]
heapq.heapify(heap)

print("[state] heap arrangement:", heap)
print("[check] root is minimum:", heap[0] == min(heap))
print("[check] heap is globally sorted:", heap == sorted(heap))
print("[result] heap removal order:", [heapq.heappop(heap) for _ in range(len(heap))])

On CPython 3.14 this prints a valid arrangement such as [1, 2, 7, 3, 9, 8], then True, False, and [1, 2, 3, 7, 8, 9]. Do not rely on the exact internal arrangement. heapify() establishes the invariant in linear time; repeated heappop() restores it after each O(log n) removal.

Sorting after every insertion maintains far more order than a scheduler needs. Conversely, if consumers repeatedly traverse all values in order, sorting once is generally clearer and faster than draining a heap.

Experiment 7: Python 3.14 has real max-heaps

Older code often negates numeric priorities to emulate a max-heap. Python 3.14 added a complete public max-heap family: heapify_max, heappush_max, heappop_max, heappushpop_max, and heapreplace_max.

Pyodide / WebAssembly
from heapq import heapify_max, heappop_max, heappush_max


scores = [41, 12, 99, 63]
heapify_max(scores)
heappush_max(scores, 75)

print("[result] maximum at heap root:", scores[0])
print("[result] max-heap removal order:", [heappop_max(scores) for _ in range(len(scores))])

99
[99, 75, 63, 41, 12]

The max APIs work for any mutually orderable values and avoid negation's semantic awkwardness. Code supporting Python 3.13 or earlier still needs another strategy.

Experiment 8: replacement operations are not interchangeable

For a min-heap, heappushpop(heap, x) returns the smaller of x and the old root, leaving the larger in the heap. heapreplace(heap, x) always removes the old root first, even when x is smaller.

Pyodide / WebAssembly
import heapq


left = [10, 20, 30]
right = left.copy()

print("[result] heappushpop returned and retained:", heapq.heappushpop(left, 5), left)
print("[result] heapreplace returned and retained:", heapq.heapreplace(right, 5), right)

5 [10, 20, 30]
10 [5, 20, 30]

This distinction matters in fixed-size top-k processing. To retain the largest k values seen, keep a min-heap of size k and use heappushpop() when a candidate arrives. The root is the smallest retained value, the threshold for entering the top group.

Experiment 9: tie-break before Python compares tasks

Tuple entries compare field by field. (priority, task) fails when equal priorities expose non-orderable task objects. A monotonic counter both prevents that comparison and gives first-in, first-out behavior among ties.

Pyodide / WebAssembly
import heapq
import itertools


counter = itertools.count()
queue = []

for task in ({"name": "compile"}, {"name": "test"}, {"name": "deploy"}):
    heapq.heappush(queue, (5, next(counter), task))

print("[result] equal-priority task order:", [heapq.heappop(queue)[2]["name"] for _ in range(len(queue))])

['compile', 'test', 'deploy']

Heaps are not stable by themselves. Stability here is an entry design. Updating arbitrary priorities is also not directly supported: production priority queues commonly keep a dictionary from task to entry, mark obsolete entries, and skip them when popped. Trying to locate and remove an arbitrary list cell is linear and risks breaking the invariant.

Bisect: cheap boundaries over an expensive insertion

The bisect functions assume the input is already sorted. They use <, not ==, to return insertion boundaries. bisect_left points before equal values; bisect_right points after them.

Experiment 10: duplicates define a range

Pyodide / WebAssembly
from bisect import bisect_left, bisect_right


values = [10, 20, 20, 20, 30, 40]
left = bisect_left(values, 20)
right = bisect_right(values, 20)

print("[result] duplicate range boundaries:", left, right)
print("[result] duplicate range values:", values[left:right])
print("[result] duplicate count:", right - left)

1 4
[20, 20, 20]
3

This pattern answers range questions without scanning from the beginning: count equal values, find the first timestamp at or after a cutoff, or isolate records in an interval. For exact membership, verify the candidate because a bisection always returns a position:

Pyodide / WebAssembly
from bisect import bisect_left


values = [10, 20, 30]
i = bisect_left(values, 25)
found = i != len(values) and values[i] == 25
print("[result] insertion index and exact match:", i, found)

This prints 2 False.

Experiment 11: logarithmic search, linear insertion

insort() first bisects, then calls list.insert(). Finding the middle is O(log n); opening a cell there still shifts roughly half the references.

from bisect import bisect_left, insort
from timeit import timeit


n = 100_000
search = timeit(
    "bisect_left(values, target)",
    setup=f"from bisect import bisect_left; values=list(range({n})); target={n // 2}",
    number=10_000,
)
insert = timeit(
    "insort(values, target); values.pop(target)",
    setup=f"from bisect import insort; values=list(range({n})); target={n // 2}",
    number=1_000,
)

print(search / 10_000 < insert / 1_000)

The result was True in the test environment. Comparing per-operation averages avoids the misleading raw totals, but this is still an illustrative microbenchmark. The structural conclusion is official: O(n) insertion dominates O(log n) search.

A sorted list plus bisect is attractive when reads greatly outnumber writes, data comfortably fits in memory, and range queries matter. If insertions are frequent and collections are large, consider batching and sorting, a database index, or a purpose-built sorted collection.

Experiment 12: key applies asymmetrically

Since Python 3.10, bisection accepts key. During bisect_left(records, x, key=...), the key is applied to sequence elements but not to x; pass the already extracted search key. During insort_left(records, record, key=...), the key is applied to the new record for searching, then the original record is inserted.

Pyodide / WebAssembly
from bisect import bisect_left, insort_left
from operator import itemgetter


by_time = itemgetter(0)
events = [(10, "start"), (30, "stop")]

index = bisect_left(events, 20, key=by_time)
insort_left(events, (20, "checkpoint"), key=by_time)

print("[result] insertion index:", index)
print("[state] events after sorted insertion:", events)

1
[(10, 'start'), (20, 'checkpoint'), (30, 'stop')]

The search functions are stateless and may recompute keys for the same elements across calls. If key extraction is expensive, maintain a parallel sorted list of precomputed keys or cache a pure key function. Keep parallel arrays synchronized on every mutation.

Concurrency boundary. The bisect documentation says its functions are not thread-safe when multiple threads operate on the same sequence, or when another thread mutates that sequence during bisection. External synchronization must cover both search and insertion.

A practical decision sequence

Ask these questions in order:

  1. Do you need arbitrary indexing or a stack? Start with a list.
  2. Do you repeatedly add or remove at the left edge? Use a deque.
  3. Do you need only the next smallest or largest item as values arrive? Use a heap.
  4. Do you retain sorted order mainly for many boundary and range queries? Use bisect over a sorted list.
  5. Do you need exact lookup rather than ordering? Use a dict or set.

Then inspect secondary requirements. A heap does not find or update arbitrary jobs efficiently. A deque does not provide slicing and is slow in its middle. Bisect assumes ordering is maintained and does not make writes cheap. A list remains the right default when the collection is small, mutations happen at the right edge, or full sorting is done in batches.

Container changes should follow evidence about operation frequency, collection size, and latency requirements. A benchmark that repeatedly performs an operation your application rarely uses answers the wrong question.

Exercises

  1. Implement breadth-first search with deque. Replace it with a list using pop(0), verify identical traversal, and compare growth at 1,000 and 100,000 nodes.
  2. Build a fixed-size top-10 tracker with a min-heap. Explain why the smallest retained item, not the largest, belongs at index zero.
  3. Extend the priority queue experiment with cancellation by marking entries removed. Ensure canceled tasks never escape and equal priorities remain FIFO.
  4. Given sorted timestamps with duplicates, write functions returning all events in the half-open interval [start, stop) using two bisections.
  5. Maintain records and precomputed keys in parallel. Add insertion and deletion operations, then assert after every mutation that keys are sorted and correspond to records.
  6. Design a benchmark from one of your real workloads. State the operation mix and size distribution before reporting results.

Primary sources

The documentation defines the supported interface. Source code explains one implementation. Keeping those categories separate is part of choosing containers responsibly: depend on documented behavior, reason from implementation details when useful, and remeasure details that your performance claims depend on.