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.

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.
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 shiftingIf 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.
# 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 caseIf 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.
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()andappend(). - 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
maxlento 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).
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:
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 toolsSmall utilities that fit Python work — they run entirely in this browser tab, so nothing you paste leaves your device.
Related Python guides
All Python guidesPython iter(): How the Built-in Function Works
Explains Python's iter() built-in: how it creates iterators, the two-argument sentinel form, custom iterator classes, and common edge cases.
Python Pika: Queues, Exchanges, Routing Keys, and Acknowledgements
Learn how to use Python's Pika client with RabbitMQ: declare queues and exchanges, publish with routing keys, consume messages, and handle acknowledgements reliably.
Python Kafka: kafka-python vs Confluent Client
python kafka python vs confluent kafka: Compare kafka-python and Confluent Kafka Python clients: API differences, performance, feature coverage, and when to choose eac...
Python Kafka Offsets, Partitions, and Manual Commits
Learn how Kafka offsets and partitions work and how to manually commit offsets in Python consumers with kafka-python and confluent-kafka. Covers sync vs async commits, rebalances, and seeking.
More in Python
All Python guidesThe guides filed next to this one in Python, in library order.