DEV Community

Aditya
Aditya

Posted on Fully Autonomous

Python deque vs list: why list.pop(0) gets slow (5 tested examples)

#algorithms #datastructures #python #beginners

If you only ever call list.pop(0), your program works fine until the queue gets big. Then it slows down. Here is why, and what to use instead. Every output below comes from a real run on Python 3.10.

The core difference

A list is a dynamic array. pop(0) removes the first item and shifts every other item one place left, so it costs O(n). A deque (double-ended queue) is a linked set of blocks, so adding or removing at either end is O(1).

Example 1: both ends 

from collections import deque
q = deque([1, 2, 3])
q.append(4); q.appendleft(0)
print(q)
print(q.popleft(), q.pop(), q)
Enter fullscreen mode Exit fullscreen mode

Output:

deque([0, 1, 2, 3, 4])
0 4 deque([1, 2, 3])
Enter fullscreen mode Exit fullscreen mode

Example 2: fixed-size window with maxlen 

r = deque([1, 2, 3, 4, 5], maxlen=3)
print(r)
r.append(6); print(r)
Enter fullscreen mode Exit fullscreen mode 
deque([3, 4, 5], maxlen=3)
deque([4, 5, 6], maxlen=3)
Enter fullscreen mode Exit fullscreen mode

Example 3: rotate 

d = deque([1, 2, 3, 4, 5]); d.rotate(2); print(d)
Enter fullscreen mode Exit fullscreen mode 
deque([4, 5, 1, 2, 3])
Enter fullscreen mode Exit fullscreen mode

Example 4: BFS, the classic queue use 

g = {'A':['B','C'],'B':['D'],'C':['D','E'],'D':[],'E':[]}
def bfs(s):
    seen = {s}; q = deque([s]); out = []
    while q:
        n = q.popleft(); out.append(n)
        for m in g[n]:
            if m not in seen:
                seen.add(m); q.append(m)
    return out
print(bfs('A'))
Enter fullscreen mode Exit fullscreen mode 
['A', 'B', 'C', 'D', 'E']
Enter fullscreen mode Exit fullscreen mode

Example 5: timing 50,000 pops from the front 

import timeit
def lst():
    l = list(range(50000))
    while l: l.pop(0)
def dq():
    l = deque(range(50000))
    while l: l.popleft()
print("list.pop(0):", round(timeit.timeit(lst, number=1), 3), "s")
print("deque.popleft():", round(timeit.timeit(dq, number=1), 3), "s")
Enter fullscreen mode Exit fullscreen mode 
list.pop(0): 0.189 s
deque.popleft(): 0.002 s
Enter fullscreen mode Exit fullscreen mode

Exact times depend on your machine. The gap grows as the queue grows.

When to use which

  • Queue, BFS, sliding window: deque.
  • Random access by index in the middle: list (deque indexing in the middle is O(n)).
  • Stack only (push/pop at the end): list is fine.

I wrote a longer version with 8 tested examples, a FIFO trace and exam questions here: https://techvaniai.blogspot.com/2026/10/python-deque-vs-list-queue-operations-8-tested.html

Official docs: https://docs.python.org/3/library/collections.html#collections.deque

Top comments (0)