Python List vs deque: Choosing the Right Data Structure
Compare Python's list and deque for common use cases, focusing on indexing, append/pop operations, memory, and when each structure is the right fit.

When deciding between a list and a deque, the choice usually comes down to the access and mutation patterns your code needs. list is built into Python, and deque is available from the collections module in the standard library. The two are implemented differently and excel in different scenarios.
The Core Difference Between List and deque
In CPython, a list is a dynamic array. It stores object references in a contiguous block of memory, which makes indexing by position extremely fast. Appending to the end is amortized O(1), but inserting or deleting at the front requires shifting all subsequent elements, making it O(n).
In CPython, a deque is a doubly-linked list of blocks. It is optimized for append and pop operations at both ends, each O(1). However, accessing an arbitrary element by index requires traversing from the nearest end, so indexing is O(n) in the worst case.
from collections import deque
# list
lst = [1, 2, 3]
lst.append(4) # O(1) amortized
lst.pop(0) # O(n) - shifts all elements
# deque
dq = deque([1, 2, 3])
dq.append(4) # O(1)
dq.popleft() # O(1)This fundamental difference drives most practical decisions.
When List Is the Right Choice
Use a list when your code frequently accesses elements by index, slices the sequence, or needs to iterate over the entire collection in order. The contiguous memory layout also provides better cache locality, which can improve performance in tight loops.
Common list-friendly operations include:
- Random access:
lst[i] - Slicing:
lst[start:stop] - In-place sorting:
lst.sort() - Iteration with
for x in lst
If you are building a lookup table, a matrix, or any structure where positional access dominates, a list is almost always the better choice.
When deque Is the Right Choice
A deque is the right choice when you need O(1) append and pop operations at both ends. Typical use cases include:
- Implementing a FIFO queue with
appendandpopleft - Sliding window algorithms
- Breadth-first search, where you pop from the front and append to the back
- Keeping a bounded history buffer where older items are discarded from the left
A plain LIFO stack can use either structure; list.append and list.pop are already O(1), so a list is a natural stack unless you also need left-end operations.
Here is a simple queue implementation:
from collections import deque
queue = deque()
queue.append("task1")
queue.append("task2")
next_task = queue.popleft() # "task1"Using a list for this would require pop(0), which is O(n) and becomes a performance bottleneck as the queue grows.
Performance Characteristics and Memory Tradeoffs
The time complexity of common operations differs significantly between the two structures:
| Operation | list | deque |
|---|---|---|
| Index access | O(1) | O(n) |
| Append at end | O(1) amortized | O(1) |
| Pop from end | O(1) | O(1) |
| Insert at front | O(n) | O(1) |
| Pop from front | O(n) | O(1) |
| Slicing | O(k) | Not supported |
Memory usage also differs. A list stores references in a contiguous block, with some spare capacity for growth. A deque uses separate blocks linked together, which adds per-block overhead. For a large number of small elements, a list is usually more memory-efficient. For very large collections where you frequently add and remove from both ends, the deque's per-block overhead is often acceptable given the O(1) operations.
Practical Code Examples: Queue and Sliding Window
Queue with deque
A deque provides a clean, efficient queue interface:
from collections import deque
def process_tasks(task_list):
pending = deque(task_list)
while pending:
task = pending.popleft()
# process taskSliding Window Maximum
A classic sliding window problem benefits from deque because you need to maintain a monotonic queue with O(1) pops from both ends:
from collections import deque
def max_sliding_window(nums, k):
dq = deque()
result = []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return resultHere, arbitrary indexing is avoided; the only index accesses are at the ends (dq[0] and dq[-1]), which are O(1).
List for Random Access
When you need to retrieve elements by index frequently, a list is straightforward:
lst = [10, 20, 30, 40]
for i in range(len(lst)):
print(lst[i]) # O(1) per accessCommon Pitfalls and Misconceptions
One of the most common mistakes is using list.pop(0) in a loop. This is O(n) per operation, turning what should be a linear algorithm into a quadratic one. Use a deque instead if you need to remove from the front.
Another misconception is that deque is always faster than list. For indexing and iteration, a list is often faster because of its contiguous memory layout and cache behavior. A deque should not be used as a general-purpose replacement for list.
Thread safety is also worth noting. In CPython, the GIL protects individual atomic operations such as append, pop, and popleft when they are called from multiple threads. It does not protect compound sequences: for example, checking whether a deque is non-empty and then popping from it can race with another thread and needs external synchronization.
Finally, be aware that deque does not support slicing, and arbitrary indexing is O(n). If you find yourself indexing into a deque frequently, you likely need a list.
How to Choose Based on Your Data Access Pattern
Make the decision based on the dominant operations in your code:
- Use
listwhen you need random access, slicing, or in-place sorting. - Use
dequewhen you need O(1) append/pop from both ends, especially for queues or sliding windows. - If you are unsure, profile with realistic data. The theoretical complexity differences only matter when the collection is large and the operation is hot.
For example, a breadth-first search on a graph typically uses a queue. Using a list with pop(0) would degrade performance, while a deque keeps each vertex insertion and removal at O(1). On the other hand, a list of configuration values that you read by index is better served by a list.
The choice is not about which structure is "better" overall; it is about matching the structure to the access pattern your algorithm actually requires.
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.