Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Using Python deque.appendleft() for Efficient Prepending

Learn how to use deque.appendleft() for O(1) prepending in Python, with syntax examples, performance trade-offs, and practical use cases.

~6 min readPython
#deque#collections#performance#data structures
Illustration of a Python deque with an element being added to the left side using appendleft, emphasizing O(1) operation.

Python's deque.appendleft() adds an item to the front of a deque in O(1) time. It is the efficient counterpart to list.insert(0, item), which shifts every existing element one position to the right and runs in O(n). When you repeatedly prepend items, list insertion can turn a linear algorithm into a quadratic one. The deque class from collections avoids that cost; this article explains what appendleft does, when it is the right choice, and where a list is still better.

The Cost of Prepending to a Python List

Consider a typical list-based prepend:

python
def prepend_to_list(items, new_item): items.insert(0, new_item)

Every call to insert(0, ...) shifts all existing elements right by one. If you build a list by prepending n items, the total work is roughly 1 + 2 + ... + n, which is O(n^2). This becomes noticeable when n grows beyond a few thousand elements. The following example shows how a list grows inefficiently:

python
numbers = [] for i in range(10000): numbers.insert(0, i)

Each insert shifts the entire current list to the right. The runtime cost is hidden but significant. If your algorithm genuinely needs to add to the front repeatedly, a deque avoids this quadratic behavior entirely.

What Is a deque and How Does appendleft Work?

A deque (short for double-ended queue) is a sequence that supports efficient appends and pops from both ends. In CPython, it is implemented as a doubly-linked list of blocks, which allows constant-time insertion and removal at either end. The appendleft method adds an element to the left side (the front) of the deque:

python
from collections import deque d = deque([1, 2, 3]) d.appendleft(0) print(d) # deque([0, 1, 2, 3])

The method mutates the deque in place and returns None. Unlike list.insert, it does not shift any elements; it only adjusts a few pointers and possibly allocates a new block. This is why the operation is O(1) regardless of the deque's size.

appendleft Syntax and Basic Examples

The syntax is straightforward: deque.appendleft(item). Here are a few common patterns:

python
from collections import deque # Initialize an empty deque tasks = deque() # Add a high-priority task to the front tasks.appendleft('urgent') # Add multiple items in a loop for i in range(5): tasks.appendleft(i) # Pop from the left to process in LIFO order while tasks: current = tasks.popleft() print(current)

Because appendleft works in constant time, it is safe to call it inside tight loops without worrying about hidden O(n) costs. The deque also provides append for the right side, pop and popleft for removal, and extendleft to add multiple elements from an iterable in one call:

python
from collections import deque d = deque() d.extendleft([1, 2, 3]) # equivalent to appendleft(1), appendleft(2), appendleft(3) print(d) # deque([3, 2, 1])

Note that extendleft reverses the order of the iterable because each element is prepended individually.

Performance Comparison: deque.appendleft vs list.insert(0)

The core difference is time complexity. list.insert(0, item) is O(n) because it shifts all existing elements. deque.appendleft(item) is O(1) because it only updates pointers at the boundary. The memory overhead differs too: a list stores elements in a contiguous array, which is cache-friendly but requires occasional reallocation when growing. A deque uses linked blocks, which avoids large contiguous allocations but adds some overhead for block management.

For typical use cases where you prepend a few items to a small list, the difference is negligible. The problem appears when the collection grows large or when prepending is the dominant operation. Consider a breadth-first search that processes nodes in order but needs to add newly discovered nodes to the front of the frontier. Using a list with insert(0, ...) would make the search O(n^2) in the number of nodes, while a deque keeps it O(n).

Operationlist.insert(0, item)deque.appendleft(item)
Time complexityO(n)O(1)
Memory layoutContiguous arrayLinked blocks
Cache localityHighLower
Best forRare prependsFrequent prepends

The table summarizes the tradeoff. If you only prepend occasionally and need fast random access, a list is often the better choice. If you need to prepend frequently and do not require random access, a deque is the right tool.

Practical Use Cases for appendleft

appendleft shines in algorithms that process recent items first or maintain a bounded history. One direct example is an undo stack that keeps the most recent action at the left:

python
from collections import deque class UndoHistory: def __init__(self): self._history = deque(maxlen=10) def record(self, action): self._history.appendleft(action) def undo(self): if self._history: return self._history.popleft() return None

Here, maxlen=10 automatically discards the oldest entry when the deque exceeds ten items, which is a convenient way to bound memory. The appendleft call is constant time, so recording an action never depends on the number of saved actions.

Because you can append and pop from either end, a deque can also serve as a stack or a queue. For example, a browser back button can be modeled as a deque where you push new pages to the left and pop them when the user goes back. For sliding-window minimum or maximum problems, deque-based solutions rely on the same O(1) end operations; common implementations append the new item on one side and pop expired items from the other.

Memory and Compatibility Considerations

A deque generally consumes more memory than a list because it stores elements in linked blocks rather than one contiguous array. For large collections, this overhead can be significant. If you need to store millions of integers and prepend rarely, a list's contiguous storage is more memory-efficient. However, if you are constantly adding to the front, the memory savings from avoiding repeated reallocation and shifting may outweigh the per-block overhead.

Regarding thread safety, individual deque.append, appendleft, pop, and popleft calls are atomic in CPython, so they can be called from multiple threads without additional locking for those single calls. Compound operations such as if d: d.popleft() still need an external lock. This atomicity is an implementation detail of CPython, not a language-level guarantee for every Python implementation.

The collections.deque class has been part of Python's standard library for a long time, so compatibility is not a concern for modern projects.

Common Mistakes and Edge Cases

One frequent mistake is using appendleft on a regular list, which raises an AttributeError. Another is forgetting that appendleft mutates the deque in place and returns None, so assigning the result to a variable leads to None instead of the deque. For example:

python
from collections import deque d = deque([1, 2, 3]) result = d.appendleft(0) # result is None, not the deque

If you use a deque with maxlen, appendleft will discard the rightmost element when the deque is full. This is useful for keeping a bounded history, but it can surprise you if you expect the deque to grow without limit. Always check whether maxlen is set when you rely on the deque retaining all elements.

Another edge case is using appendleft with an empty deque. It works fine and simply adds the element. There is no special error condition. Also, appendleft accepts any Python object, including None, lists, or custom objects, so there is no type restriction.

When Not to Use appendleft

If you need random access to elements by index, a deque is a poor choice because indexing in the middle is O(n). Lists provide O(1) indexing and are better for algorithms that frequently read arbitrary positions. Similarly, if you only prepend a few items and then perform many reads, the overhead of a deque's linked structure may not be justified. A simple list with insert(0, ...) is acceptable when the list is small or when prepends are rare.

Another situation where appendleft is not ideal is when you need to insert elements at arbitrary positions, not just the front. A deque only supports efficient insertion at the ends; inserting in the middle still requires O(n) time. For that, you would need a different data structure like a balanced tree or a skip list.

Finally, consider the memory tradeoff. If you are building a large collection and memory is a constraint, a list's contiguous storage is more compact. Use appendleft when the O(1) prepend operation is critical to your algorithm's complexity, and you can tolerate the additional memory overhead. The decision ultimately depends on the frequency of prepends, the need for random access, and the size of the data set.

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.