How to Use Deque in Python: collections.deque

Modified: | Tags: Python, List

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.

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) and insert(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 to O(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().

Related Categories

Related Articles