Stop Using Python Lists as Queues — Use collections.deque

A Python list is a great stack but a terrible queue. Every time you call list.pop(0) (or list.insert(0, x)), Python has to shift every remaining element one slot over. That makes queue operations O(n). collections.deque gives you O(1) appends and pops from both ends. If you need a FIFO queue, reach for deque.

What actually happens on list.pop(0)

A Python list is a contiguous array of pointers in memory. Indexing (list[i]) and appending/popping at the end are cheap because nothing else has to move.

But popping from the front is a different story. When you remove index 0, every other element has to slide down by one position to keep the array contiguous:

Before pop(0):  [A][B][C][D][E]
Remove A:       [ ][B][C][D][E]
Shift left:     [B][C][D][E]

That shift is O(n). Do it once, no big deal. Do it in a loop for a queue, and you get O(n²) behavior overall — which falls off a cliff as the data grows.

Proving it with a benchmark

Here's a stripped-down version of the experiment I ran. We fill a list, then time a single pop(0) at increasing sizes:

import random
import time

data = []

for size in (1_000_000, 10_000_000, 100_000_000):
    while len(data) < size:
        data.append(random.randint(0, 10000))

    start = time.perf_counter()
    data.pop(0)          # remove from the FRONT
    elapsed = time.perf_counter() - start

    print(f"pop(0) with {size:>12,} elements: {elapsed:.6f}s")

The exact numbers depend on your machine, but the shape of the result is the point: the time to pop(0) grows with the number of elements, because Python is shifting all of them. Meanwhile, pop() from the end stays flat no matter how big the list gets.

A subtle trap: pop(0) on a huge list dominated my timings so badly it was easy to think the append loop was the slow part. It isn't — appending to the end of a list is O(1) amortized. The front operation is the culprit.

What deque does differently

collections.deque ("double-ended queue") is implemented as a doubly linked list of fixed-size blocks. Because it keeps references to both the head and the tail, adding or removing at either end never requires shifting anything.

To make it concrete, here's the core idea behind it — a minimal FIFO queue built on a doubly linked list, which is essentially what deque does under the hood:

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None
        self.prev = None

class LinkedQueue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):          # add to the tail — O(1)
        new_node = Node(value)
        if self.head is None:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def dequeue(self):                 # remove from the head — O(1)
        if self.head is None:
            return None
        value = self.head.data
        self.head = self.head.next
        if self.head:
            self.head.prev = None
        else:
            self.tail = None           # queue is now empty
        return value

Notice there's no shifting anywhere. Adding to the tail and removing from the head each touch only a couple of pointers, regardless of how many elements are in the queue. That's the whole reason it stays O(1).

Writing this yourself is a great learning exercise — but in real code you don't have to. The standard library already gives you a battle-tested, C-optimized version.

Just use collections.deque

from collections import deque

queue = deque()

queue.append("first")     # enqueue at the tail  — O(1)
queue.append("second")

front = queue.popleft()   # dequeue from the head — O(1)
print(front)              # -> "first"

Operation	list	deque
Append at end	O(1) amortized	O(1)
Pop from end	O(1)	O(1)
Append at front	O(n)	O(1)
Pop from front	O(n)	O(1)
Random index access	O(1)	O(n)

The trade-off: deque gives up fast random indexing (queue[i] is O(n)). For a queue, you almost never index into the middle — you only touch the ends — so that trade is exactly the one you want.

A real use case: BFS

Breadth-first search is the classic place this matters. BFS is defined by a FIFO queue: you keep pulling the oldest node off the front and pushing its neighbors onto the back. With a list, every pop(0) would be O(n); with deque it's O(1).

from collections import deque

def breadth_first_search(graph, start_node):
    visited = {start_node}
    queue = deque([start_node])      # O(1) FIFO queue

    while queue:
        current = queue.popleft()    # pop the front — O(1)
        print(current, end=" ")

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

breadth_first_search(graph, 'A')     # -> A B C D E F

Swap the deque for a list with pop(0) and the algorithm still works — it just silently degrades from O(V + E) toward O(V²) on large graphs.

Bonus: deque extras you get for free

• appendleft(x) and popleft() — O(1) operations on the front.
• deque(maxlen=N) — a bounded queue that automatically drops the oldest item when full (great for sliding windows and "last N events" buffers).
• Thread-safe append/popleft, which makes deque handy for simple producer/consumer patterns.

Takeaways

1. A list is a stack, not a queue. append + pop() (both ends = the right end) are fast.
2. list.pop(0) and list.insert(0, x) are O(n) because of element shifting — avoid them in loops.
3. collections.deque is the built-in FIFO queue with O(1) operations at both ends.
4. Understanding why (linked blocks vs. a contiguous array) is what lets you pick the right tool next time.