Why is `list.pop(0)` O(n) while `collections.deque.popleft()` is O(1)?
answer
- One shifts everything, one unlinks
- Contiguous array versus chained blocks
- What removing the front element really costs
- list.pop(0) memmoves the remaining pointers
- deque holds pointers to both ends
basics
~20 sA list keeps its items in one contiguous array, so removing index 0 shifts every remaining element down one slot. A deque is a doubly linked chain of small blocks, so popleft just unlinks the front item.
solid answer
~40 s`list` is a dynamic array: the items sit in one contiguous block of pointers, and `list.pop(0)` (like `list.insert(0, x)`) has to memmove every remaining pointer one slot, so it costs O(n) per call. `collections.deque` is a doubly linked list of fixed-size blocks, and it keeps pointers to both ends, so `append`, `appendleft`, `pop` and `popleft` are all O(1) with no reshuffling. The difference is not a constant factor: draining an n-item list front-first is O(n²), while draining a deque is O(n). Use a deque whenever items enter one end and leave the other — a breadth-first frontier, a work backlog, a sliding window. Keep `list` when you need random indexing or slicing, which a deque does not do cheaply.
code
python · 8 linesfrom collections import deque
q = deque([1, 2, 3])
q.append(4) # O(1) on the right
q.appendleft(0) # O(1) on the left
print(q.popleft()) # 0
print(q.pop()) # 4
print(list(q)) # [1, 2, 3]go deeper
Be ready to say which end of a list is cheap and which is expensive, and to name collections.deque as the fix for popping from the front. Knowing popleft exists and costs O(1) is the whole bar here.
Explain the mechanism, not just the cost: a list is one contiguous array so index 0 removal memmoves the rest, while a deque is a chain of blocks with pointers to both ends. Show that draining a list front-first is quadratic overall.
Demonstrate that you spot the pattern in review before it reaches production, and that you know the trade you are making — no cheap middle indexing, no slicing, more memory per item — so you do not swap every list for a deque reflexively.
Own the guidance: pick the container from the access pattern rather than from folklore, and be able to say when the quadratic drain is genuinely irrelevant (small, bounded collections) versus when it is a latency cliff waiting for a bigger input.
## Two different memory layouts The whole answer is layout. A Python `list` is a **dynamic array**: the object owns one contiguous C array of `PyObject*` pointers plus a length and a capacity. Indexing is a single pointer arithmetic step, which is why `lst[i]` is O(1) for any `i`. But that same contiguity is what makes the front expensive: the invariant is *element k lives at slot k*, so deleting slot 0 means every one of the remaining n-1 pointers must move down one slot. CPython does this with a single `memmove`, which is fast per byte but still linear in the number of items. `list.insert(0, x)` is the mirror image, shifting everything up. `collections.deque` is a **doubly linked list of fixed-length blocks** — in CPython each block holds 64 item pointers, and the blocks are linked to their neighbours. The deque object holds a pointer to the leftmost block and the rightmost block plus the index of the first and last used slot inside them. Appending on the right writes into the next free slot of the right block, allocating a fresh block and linking it in when that block fills. Popping on the left reads the leftmost used slot and bumps the index, freeing the block when it empties. Nothing else moves, at either end, ever. That is why all four of `append`, `appendleft`, `pop` and `popleft` are documented as O(1), and why `deque` is the structure the standard library gives you for anything FIFO-shaped. ## The cost that bites in practice A single `list.pop(0)` on a short list is unmeasurable, which is exactly why the mistake survives code review. The damage is in the loop: ```python while work: # work is a list item = work.pop(0) # O(n) each time process(item) ``` Each pop shifts what is left, so the total is n + (n-1) + (n-2) + ... = O(n²). At a thousand items that is a million pointer moves and nobody notices; at a million items it is 10^12 and the process appears to hang. Swapping `work = list(...)` for `work = deque(...)` and `pop(0)` for `popleft()` makes the same loop O(n) with no other change, because `deque` supports the same iteration, `len`, `in` and truth-testing that the loop relied on. ## What you give up A deque is not a better list; it is a different trade. Because the items live in a chain of blocks, there is no formula from index to address, so `d[i]` must walk block by block from whichever end is nearer. Reading `d[0]` or `d[-1]` is O(1), but reading somewhere in the middle is O(n). A deque also does **not** support slicing at all: `d[1:3]` raises `TypeError`, and you reach for `itertools.islice` instead. `deque.insert`, `deque.remove` and `deque.index` exist but are linear. Per item, a deque also costs a little more memory than a tightly packed list. So the rule of thumb is about access pattern, not about which type is “faster”. If the code indexes or slices, keep the list. If the code pushes and pops at the ends — a queue of pending jobs, a stack, an undo trail, a window of recent samples — use `collections.deque`. If it pops from the *right* only, a plain list is already O(1) amortised and a deque buys you nothing: `list.pop()` with no argument does not shift anything. ## Related properties worth knowing The documentation guarantees that a single `append` or `pop` from either end of a deque is atomic, so several threads can push and pop without corrupting it — though a compound sequence like “check `len`, then `popleft`” is still a race, and a blocking producer/consumer handoff wants `queue.Queue` instead. A deque also accepts `maxlen`, turning it into a bounded buffer that discards from the far end as you push. And `deque` is registered as a `collections.abc.Sequence`, so it iterates, reverses and compares like the sequence it is — just without the random access. ## Why appending to a list is still fine The asymmetry is worth stating explicitly, because "lists are slow" is the wrong lesson to take away. `list.append` is O(1) *amortised*: CPython over-allocates the backing array, so most appends write into spare capacity and only occasionally does the list grow, copying the pointers to a larger block. Spread over many appends that copy costs a constant per item. `list.pop()` with no argument is likewise O(1) — it drops the last reference and shrinks the length, moving nothing. So a list is already an excellent stack, and rewriting `stack.append(x)` / `stack.pop()` as a deque buys nothing measurable. The deque earns its place precisely when the *front* is involved: FIFO order, a batch pushed on one side and consumed from the other, or a window that grows at one end while it shrinks at the other.
- If both ends are O(1) on a deque, why not use `collections.deque` instead of `list` everywhere?Because random access is the price. A deque has no index-to-address formula, so `d[i]` walks blocks from the nearer end and is O(n) in the middle, and slicing is not supported at all — `d[1:3]` raises `TypeError`. Lists also pack more tightly in memory. Use a deque when the access pattern is push and pop at the ends; keep a list when you index, slice or sort.
- Is `list.pop()` with no argument also O(n)?No. `list.pop()` removes the last item, which needs no shifting — it just decrements the length and drops one reference, so it is O(1) amortised. Only removals and insertions near the front are linear. That is why a plain list is a perfectly good stack, and why the deque advantage shows up specifically in FIFO code.
- Can several threads push and pop the same `collections.deque` without a lock?A single `append` or `pop` from either end is documented as atomic, so the deque itself will not be corrupted. But a compound sequence — test `len(d)`, then `popleft()` — is still a race, because another thread can drain it in between. For blocking handoff with backpressure use `queue.Queue`, which adds the waiting and the size bound on top.
A list is a row of numbered seats: take the person out of seat 0 and everyone else shuffles down one. A deque is a train of carriages: unhook the front one and nothing else moves.
saying these in an interview costs you the question
- Claims list.pop(0) is O(1) like list.pop()
- Thinks deque is a subclass of list
- Says a deque gives O(1) access to any index
- Uses list.insert(0, x) in a hot loop
- Cannot say what a list stores contiguously
- Thinks the difference is only a constant factor