Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Python deque vs list: When to Use Each

Compare Python's deque and list for append, pop, and indexing. Learn when each data structure is the right choice for queues, stacks, and random-access workloads.

~6 min readPython
#deque#list#performance#data structures
Illustration comparing Python deque and list data structures, showing a two-ended queue and a contiguous array with an index pointer.

When you need a mutable sequence in Python, list is usually the first tool that comes to mind. But the collections.deque class exists for a specific reason: it makes appending and popping from both ends efficient. The choice between deque and list comes down to which operations dominate your workload, and understanding the underlying memory and access patterns of each structure.

What deque and list Have in Common

Both deque and list are mutable, iterable containers. They support common operations like len(), in, and count(), and they both implement the sequence protocol, so you can pass either to functions that expect an iterable. A list also supports slicing directly. A deque supports indexing, but not slicing; if you need a slice, convert it to a list first. For basic operations like iterating over elements or checking membership, the difference is negligible.

However, the internal storage differs fundamentally. In CPython, a list is a dynamic array: a contiguous block of memory holding pointers to each element. A deque is a doubly-linked list of fixed-size blocks, where each block holds a small array of elements. That design gives deque its signature ability to grow and shrink from both ends without moving other elements.

Appending and Popping from the Right End

For appending to the end, both list.append() and deque.append() are amortized O(1). A list occasionally reallocates its underlying array, copying all references to a larger block, but the amortized cost remains constant. A deque allocates new blocks as needed, so it also achieves O(1) per append, with a slightly higher constant factor due to block management.

Popping from the right end is likewise O(1) for both. list.pop() removes the last element and, in CPython, shrinks the underlying array when it becomes too sparse. deque.pop() removes from the last block and frees the block when empty. For a stack (LIFO) where you only push and pop from one end, a list is usually the better choice because it has lower overhead and better cache locality.

The Critical Difference: Appending and Popping from the Left

This is where the two structures diverge sharply. list.insert(0, item) and list.pop(0) are O(n) because every existing element must be shifted one position. For a list of one million elements, inserting at the front copies all references. In contrast, deque.appendleft() and deque.popleft() are O(1) because the deque simply links a new block at the front or removes the first block.

python
from collections import deque # List: O(n) for front insertion lst = [1, 2, 3] lst.insert(0, 0) # shifts all elements # Deque: O(1) for front insertion dq = deque([1, 2, 3]) dq.appendleft(0) # no shifting

If your algorithm repeatedly adds and removes from both ends—such as a sliding window, a double-ended queue, or a breadth-first search frontier—deque is the correct choice. Using a list for these operations would turn an O(1) operation into O(n), which can degrade a linear-time solution into a quadratic one.

Inserting and Deleting in the Middle

Neither structure is optimized for arbitrary middle insertion or deletion. list.insert(i, item) and list.pop(i) are O(n) because elements after the index must shift. deque also requires O(n) work for middle insertion or deletion in the worst case, and the constant factor is typically worse than a list's shift because the implementation must work across block boundaries.

python
# Both are O(n) for middle operations lst = [1, 2, 3, 4, 5] lst.insert(2, 99) # shifts 3, 4, 5 dq = deque([1, 2, 3, 4, 5]) dq.insert(2, 99) # also linear in the worst/middle case

If your workload involves frequent insertions or deletions at arbitrary positions, neither deque nor list is ideal. Consider a specialized balanced structure instead; those are not part of the standard library. For occasional middle operations on a small sequence, the difference is negligible.

Indexing and Random Access

list provides O(1) random access because elements are stored contiguously and the address is computed directly from the index. deque supports indexing, but access in the middle is O(n) in CPython because it must walk through blocks from whichever end is closer. Indexing near either end is much cheaper, but if your algorithm relies heavily on arbitrary random access—such as binary search or sorting—a list is the clear winner.

python
lst = list(range(1000000)) dq = deque(range(1000000)) # List indexing is direct pointer arithmetic x = lst[500000] # Deque indexing traverses blocks to find the right one y = dq[500000]

deque also has no in-place sort() method. If you need to sort one, use sorted(dq) to get a sorted list, or convert to a list, sort, and convert back if you need a deque. The conversion is O(n), which is acceptable if sorting is infrequent.

Memory and Cache Behavior

A list stores references in a contiguous array, which makes iteration and access cache-friendly. A deque stores references in separate blocks, so iterating over a large deque may incur cache misses when jumping between blocks. In CPython, blocks hold 64 elements, so the overhead is minimal for small deques; for large ones, the memory layout can affect performance.

Memory usage also differs. A list overallocates its array to amortize appends, so it may use more memory than the number of elements. A deque allocates blocks on demand, but each block has fixed overhead. For many small elements, a deque may use more memory per element than a list due to block metadata. If memory footprint is critical and you only need stack-like behavior, a list is usually more compact.

Practical Decision Guide

Use deque when you need O(1) appends and pops from both ends. Typical scenarios include:

  • Implementing a queue (FIFO) where you popleft() and append().
  • Sliding window algorithms that add to the right and remove from the left.
  • BFS traversal where you maintain a frontier.
  • Keeping a bounded history of recent items, using maxlen to automatically discard old items.

Use list when you need:

  • Random access by index, especially for algorithms like binary search.
  • Sorting, because list.sort() is in-place and efficient.
  • Slicing, which returns a new list and is not available for deque.
  • Stack behavior (LIFO) where you only append and pop from the same end.
  • Interoperability with code that requires a list or serializes a list, such as json.dumps() (a deque must be converted first).
python
from collections import deque # Queue using deque q = deque() q.append("task1") q.append("task2") first = q.popleft() # "task1" # Bounded history dq = deque(maxlen=3) for i in range(5): dq.append(i) # dq is now deque([2, 3, 4])

The maxlen parameter is a unique feature of deque that automatically discards items from the opposite end when the deque is full. This is useful for keeping a rolling window of recent events without manual checks.

Performance Measurement and Big-O vs Constants

When comparing deque and list, it's tempting to rely solely on Big-O notation. Big-O tells you how an operation scales, but it doesn't tell you the constant factor. For small collections, a list's cache-friendly contiguous storage often outperforms a deque even for front operations, because the overhead of block management can outweigh the O(n) shift. Conversely, for large collections, the O(n) shift becomes dominant and deque wins clearly.

A practical approach is to profile with realistic data sizes. Use the timeit module to measure your specific workload. For example, compare list.pop(0) and deque.popleft() on a list of 100,000 elements:

python
from timeit import timeit from collections import deque lst = list(range(100000)) dq = deque(range(100000)) list_time = timeit(lambda: lst.pop(0), number=1000) deque_time = timeit(lambda: dq.popleft(), number=1000) print(f"list pop(0): {list_time:.4f}s") print(f"deque popleft: {deque_time:.4f}s")

The exact numbers depend on your hardware and Python version, but for a large list you'll typically see deque.popleft() finish far faster than list.pop(0). For small collections, the difference may be negligible, so don't over-optimize prematurely.

Compatibility and Edge Cases

deque is part of the standard library's collections module. It does not support slicing, and it does not accept slice objects in indexing. If you need to slice, convert to a list first. Also, deque is not a subclass of list, so functions that explicitly check isinstance(x, list) will reject it. In most contexts, duck typing makes this irrelevant, but be aware if you're using type annotations.

Threading behavior deserves care. The docs describe deques as supporting thread-safe, memory-efficient appends and pops from either side. In CPython, individual method calls are protected by the GIL, so simple producer-consumer use of append() and popleft() works without a lock. For multi-step operations, such as checking whether the deque is non-empty before popping, use a lock. A list has no documented thread-safety guarantee; concurrent modifications require external synchronization.

When you need to serialize a deque, json.dumps() cannot handle it directly because it is not a list. Convert to a list first: list(dq). The pickle module can handle a deque, but if the serialized format matters, convert to a list for predictability.

Ultimately, the choice between deque and list should be driven by the dominant operations in your algorithm. If you find yourself using insert(0, ...) or pop(0) on a list, switch to a deque. If you're doing heavy random access or sorting, stick with a list. Understanding the internal mechanics of each structure lets you make that decision with confidence rather than guessing.

Try matching browser tools

All tools

Small utilities that fit Python work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Python guides

More in Python

All Python guides

The guides filed next to this one in Python, in library order.