How to Use Deque in Python: collections.deque
In Python, the collections.deque
class provides an efficient way to handle data as a queue, stack, or deque (double-ended queue).
While the built-in list
can be used as a queue, stack, or deque, collections.deque
offers better performance, especially for adding or removing elements at the beginning.
However, note that accessing elements in the middle of a deque
is slower compared to a list
.
All sample code in this article assumes that the deque
class from the collections
module has been imported as follows.
from collections import deque
Refer to the following articles for details on adding and removing elements from a list
.
- Add an item to a list in Python (append, extend, insert)
- Remove an item from a list in Python (remove, pop, clear, del)
Performance comparison: list
vs. collections.deque
The official Python Wiki details the complexities of various operations for list
and deque
.
In a list
, operations like pop(0)
(remove and return the first element) and insert(0, v)
(add an element to the head) have O(n)
time complexity.
However, in deque
, methods like append()
, appendleft()
, pop()
, and popleft()
for adding and removing the first and last elements all have O(1)
time complexity.
This is also mentioned in the official documentation.
Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same
O(1)
performance in either direction.Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for
pop(0)
andinsert(0, v)
operations which change both the size and position of the underlying data representation. collections - deque objects — Container datatypes — Python 3.13.3 documentation
Accessing elements in the middle using []
is faster in a list
.
Indexed access is
O(1)
at both ends but slows toO(n)
in the middle. For fast random access, use lists instead. collections - deque objects — Container datatypes — Python 3.13.3 documentation
Here's a general guideline:
- If you want to add, delete, and access elements only at both ends -> use
deque
- If you frequently access elements in the middle -> use
list
It’s best to use deque
when you specifically need to handle data as a queue, stack, or double-ended queue.
However, the difference in processing speed between list
and deque
is usually not noticeable when dealing with a few hundred or a few thousand elements, depending on the environment and specific conditions. In most cases, using list
is sufficient unless you're optimizing for performance at the millisecond level.
To decide between list
and deque
based on your specific needs, consider benchmarking the processing time with the timeit
module.
How to use collections.deque
As mentioned at the beginning, the deque
class from the collections
module is imported as follows.
from collections import deque
Create a deque
object
Use deque()
to create a deque
object.
If no argument is passed, an empty deque
is created. If an iterable object, such as list
, is passed, a deque
object containing those elements is created.
d = deque()
print(d)
# deque([])
print(type(d))
# <class 'collections.deque'>
d = deque(['m', 'n'])
print(d)
# deque(['m', 'n'])
You can also limit the maximum length (maximum number of elements) with the second argument, maxlen
. Details are described later.
Add an element: append()
, appendleft()
, extend()
, extendleft()
, insert()
append()
adds an element to the right side, appendleft()
adds it to the left side.
d = deque(['m', 'n'])
d.append('o')
print(d)
# deque(['m', 'n', 'o'])
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n', 'o'])
extend()
adds all the elements of an iterable object, such as list
, to the right side. extendleft()
adds them to the left side. Note that when using extendleft()
, the elements are added to the left one by one, resulting in the original order being reversed in the deque.
d.extend(['p', 'q'])
print(d)
# deque(['l', 'm', 'n', 'o', 'p', 'q'])
d.extendleft(['k', 'j'])
print(d)
# deque(['j', 'k', 'l', 'm', 'n', 'o', 'p', 'q'])
insert()
adds an element at a specific position, with the position as the first argument and the value to be added as the second.
You can specify a position from the end using a negative value for the first argument. If a position that doesn't exist (out of range) is specified, the element will be added either to the beginning or the end, depending on the specified value.
d.insert(3, 'XXX')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'q'])
d.insert(-1, 'YYY')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q'])
d.insert(100, 'ZZZ')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])
d.insert(-100, 'XYZ')
print(d)
# deque(['XYZ', 'j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])
Remove an element: pop()
, popleft()
, remove()
, clear()
pop()
removes one element from the right side, and popleft()
removes one element from the left side, and returns its value. Unlike the pop()
method in a list
, you cannot specify the position as an argument for deque's pop()
.
d = deque(['a', 'b', 'c', 'b', 'd'])
print(d.pop())
# d
print(d)
# deque(['a', 'b', 'c', 'b'])
print(d.popleft())
# a
print(d)
# deque(['b', 'c', 'b'])
remove()
removes the first element whose value matches the specified argument. Even if two or more elements match the specified value, only the first element is removed. If no element matches the specified value, an error is raised.
d.remove('b')
print(d)
# deque(['c', 'b'])
# d.remove('X')
# ValueError: deque.remove(x): x not in deque
clear()
removes all elements and empties deque
.
d.clear()
print(d)
# deque([])
Calling pop()
or popleft()
on an empty deque
raises an error, but clear()
does not.
# d.pop()
# IndexError: pop from an empty deque
# d.popleft()
# IndexError: pop from an empty deque
d.clear()
print(d)
# deque([])
Rotate the deque: rotate()
The rotate()
method is available in deque
but not in list
. By default, elements are rotated one by one to the right.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate()
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
If an integer is specified, it rotates to the right by that number. If a negative value is specified, it rotates to the left.
You can also specify a value greater than the number of elements.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(2)
print(d)
# deque(['d', 'e', 'a', 'b', 'c'])
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(-1)
print(d)
# deque(['b', 'c', 'd', 'e', 'a'])
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(6)
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
Access an element and index: []
, index()
As with a list
, you can access and modify an element by index in []
. Negative indices reference positions from the end.
d = deque(['a', 'b', 'c', 'd', 'e'])
print(d[0])
# a
print(d[-1])
# e
d[2] = 'X'
print(d)
# deque(['a', 'b', 'X', 'd', 'e'])
While direct slicing (:
) isn't supported in a deque
, you can replicate this functionality using islice()
from the standard library's itertools
module.
# print(d[2:4])
# TypeError: sequence index must be integer, not 'slice'
import itertools
print(deque(itertools.islice(d, 2, 4)))
# deque(['X', 'd'])
With index()
, you can get the index of the first element that matches the value specified as an argument. If no matching element is found, an error is raised.
d = deque(['a', 'b', 'c', 'c', 'd'])
print(d.index('c'))
# 2
# print(d.index('x'))
# ValueError: 'x' is not in deque
Other common operations: len()
, count()
, in
, and more
In addition, deque
also supports other operations like list
.
Get the number of elements with the built-in len()
function.
d = deque(['a', 'a', 'b', 'c'])
print(len(d))
# 4
Use count()
to count the number of occurrences of a specified value.
print(d.count('a'))
# 2
print(d.count('x'))
# 0
Use the in
operator to check if an element exists in the deque
.
print('b' in d)
# True
print('x' in d)
# False
Reverse the order with the reverse()
method or the built-in reversed()
function. The reverse()
method reverses the original object itself, and reversed()
returns the reversed iterator.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.reverse()
print(d)
# deque(['e', 'd', 'c', 'b', 'a'])
d = deque(['a', 'b', 'c', 'd', 'e'])
print(deque(reversed(d)))
# deque(['e', 'd', 'c', 'b', 'a'])
You can also iterate over a deque
using a for
loop.
d = deque(['a', 'b', 'c'])
for v in d:
print(v)
# a
# b
# c
You can convert a deque
to either a list
or a tuple
using list()
or tuple()
.
d = deque(['a', 'b', 'c'])
l = list(d)
print(l)
# ['a', 'b', 'c']
print(type(l))
# <class 'list'>
Limit the maximum length with maxlen
If the second argument maxlen
of deque()
is specified, the maximum length (the maximum number of elements) can be limited. The default value of maxlen
is None
, which means there is no limit on the length.
from collections import deque
d = deque(['l', 'm', 'n'], 3)
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
When maxlen
is specified and the deque
is full, adding new elements with append()
, appendleft()
, extend()
, or extendleft()
automatically discards elements from the opposite side.
d.append('o')
print(d)
# deque(['m', 'n', 'o'], maxlen=3)
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
d.extend(['o', 'p'])
print(d)
# deque(['n', 'o', 'p'], maxlen=3)
d.extendleft(['m', 'l'])
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
However, when using insert()
, an error is raised even when trying to add elements to either the beginning or the end of a full deque
.
# d.insert(0, 'XXX')
# IndexError: deque already at its maximum size
If the deque hasn’t reached its maxlen
, you can still add elements using insert()
.
print(d.pop())
# n
print(d)
# deque(['l', 'm'], maxlen=3)
d.insert(1, 'XXX')
print(d)
# deque(['l', 'XXX', 'm'], maxlen=3)
You can access maxlen
as an attribute, but it's read-only and cannot be modified.
print(d.maxlen)
# 3
# d.maxlen = 5
# AttributeError: attribute 'maxlen' of 'collections.deque' objects is not writable
Use deque
as a queue (FIFO)
A queue holds data in a FIFO (First In, First Out) structure. In a queue, inserting data is called "enqueue", and removing data is called "dequeue".
To use deque
as a queue, add elements with append()
and remove them with popleft()
.
from collections import deque
d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
print(d.popleft())
# a
print(d)
# deque(['b', 'c', 'd'])
Use deque
as a stack (LIFO)
A stack holds data in a LIFO (Last In, First Out) structure. In a stack, inserting data is called "push", and removing data is called "pop".
To use deque
as a stack, add elements with append()
and remove them with pop()
.
from collections import deque
d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
print(d.pop())
# d
print(d)
# deque(['a', 'b', 'c'])
Use deque
as a deque (double-ended queue)
A deque (double-ended queue) is a queue where elements can be added or removed at both ends (head and tail).
As in the previous examples, deque
allows you to add and remove elements from both ends with append()
, appendleft()
, pop()
, and popleft()
.