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.

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:
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:
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:
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:
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:
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).
| Operation | list.insert(0, item) | deque.appendleft(item) |
|---|---|---|
| Time complexity | O(n) | O(1) |
| Memory layout | Contiguous array | Linked blocks |
| Cache locality | High | Lower |
| Best for | Rare prepends | Frequent 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:
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 NoneHere, 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:
from collections import deque
d = deque([1, 2, 3])
result = d.appendleft(0) # result is None, not the dequeIf 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 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.