Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

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.

~4 min readPython
#python#deque#data structures#performance
Illustration comparing a Python list as a contiguous array and a deque as a linked structure for efficient end operations.

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.

python
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 append and popleft
  • 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:

python
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:

Operationlistdeque
Index accessO(1)O(n)
Append at endO(1) amortizedO(1)
Pop from endO(1)O(1)
Insert at frontO(n)O(1)
Pop from frontO(n)O(1)
SlicingO(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:

python
from collections import deque def process_tasks(task_list): pending = deque(task_list) while pending: task = pending.popleft() # process task

Sliding 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:

python
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 result

Here, 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:

python
lst = [10, 20, 30, 40] for i in range(len(lst)): print(lst[i]) # O(1) per access

Common 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 list when you need random access, slicing, or in-place sorting.
  • Use deque when 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 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.