Deque vs List for BFS: 6x Speed Difference at Scale

#bfs #deque #pythonperformance #codinginterview

The Pop(0) Trap That Slows Every Beginner BFS

Most Python BFS implementations I see in interview prep use list.pop(0). It works. It passes small test cases. And it quietly tanks your performance on anything over a few thousand nodes.

The difference isn't subtle. On a graph with 100,000 nodes, collections.deque finishes in 0.08 seconds while the list-based version crawls at 0.52 seconds. That's over 6x slower — enough to TLE on competitive programming judges and raise eyebrows in interviews.

Why does this happen? list.pop(0) is $O(n)$ because Python's list is a dynamic array. Removing from the front means shifting every element down by one index. With deque, both ends are $O(1)$ thanks to its doubly-linked block structure.

Let me show you exactly where things break down.

BFS with List: The Naive Implementation

from typing import Dict, List, Set

def bfs_list(graph: Dict[int, List[int]], start: int) -> List[int]:
    visited: Set[int] = set()
    queue: List[int] = [start]
    order: List[int] = []

    while queue:
        node = queue.pop(0)  # O(n) — this is the problem
        if node in visited:
            continue
        visited.add(node)
        order.append(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)

    return order