deque – Collections in Python

In Python, deque is a class from collections module. deque is short for double-ended queue. It provides an alternative and optimized way to work with queue and stack. deque has many properties and built-in functions that we can use in our Python programs. Let’s understand these properties and functions of deque class in Python.

deque

deque provides an optimized and efficient way to work with a queue and stack data structures. It allows insertion (append) and removal (pop) of elements from both ends (left and right) with O(1) time complexity. Since, deque supports appending and popping from both ends, it can be used as both Stacks (LIFO – Last In First Out) and Queues (FIFO – First In First Out).

Syntax to create deque object:

deque_object = collections.deque(iterable, maxlen)

• collections is a module in Python. deque class is part of collections module. We need to import collections module to use deque class in our program.
• deque() is the deque class constructor
• iterable is any sequential data type object, based on which deque object will be created.
• maxlen (optional) is the maximum length for the deque_object. This ensures that the deque_object can only hold a limited number of elements. If this parameter is not given, then object can take as many elements as required.
• deque_object is the object returned

deque Properties

• Double-Ended – deque supports efficient additions and removals from both ends (left and right). That is why it can be used as both Stacks (LIFO – Last In First Out) and Queues (FIFO – First In First Out).
• Thread-Safe – deque is designed to support fast and thread-safe addition and removal operations. That makes them suitable for multi-threaded applications.
• Flexible Size – deque can grow and shrink dynamically unlike lists which require resizing. We can also limit to its maximum length while creating it.
• deque can be used as sliding windows to efficiently maintain a window of elements.
• Also, it can be used to handle streaming data, where it can handle continuous processing of data elements.

deque vs list

Python’s built-in list type has limitations in performing operations like insertions and deletions at the beginning of the list. Following table show the comparison between Time Complexity for different operations performed on deque and list object.

Operation	deque	list
Append elements to the end	O(1)	O(1)
Append elements to the start	O(1)	O(n)
Pop elements to the end	O(1)	O(1)
Pop elements to the start	O(1)	O(n)
Insert elements at arbitrary position	O(n)	O(n)
Delete elements from arbitrary position	O(n)	O(n)

Create deque

We can create deque object in multiple ways.

• Empty deque object
• deque object with list as iterable
• deque object with tuple as iterable
• deque object with maxlen parameter

from collections import deque     # Import collections module

# create empty deque
print("create empty deque with no max length")
empty_deque = deque()                             # deque() constructor without iterable
print(empty_deque)                                # empty deque object
print(type(empty_deque))                          # type of deque object

# create deque with list and no max length
print("create deque with list and no max length")
list_deque = deque(['Power BI','Python','ML'])    # deque() constructor list iterable
print(list_deque)

# create deque with tuple and no max length
print("create deque with tuple and no max length")
tuple_deque = deque(('Power BI','Python','ML'))    # deque() constructor tuple iterable
print(tuple_deque)

# create deque with max length
print("create deque with max length")
maxlen_deque = deque(['Power BI','Python','ML'], 3)  # deque() constructor list and maxlen parameter
print(maxlen_deque)

In this program, first we import deque class from collections module. We are creating deque object in multiple ways.

• Using deque() to create empty object
• Using deque(['Power BI','Python','ML']) to create deque object from list
• Using deque(('Power BI','Python','ML')) to create deque object from tuple
• Using deque(['Power BI','Python','ML'], 3) to create deque object from list and maximum length as 3.

Program Output

create empty deque with no max length
deque([])
<class 'collections.deque'>

create deque with list and no max length
deque(['Power BI', 'Python', 'ML'])

create deque with tuple and no max length
deque(['Power BI', 'Python', 'ML'])

create deque with max length
deque(['Power BI', 'Python', 'ML'], maxlen=3)

Add elements in deque

There are multiple methods to add elements in deque and we can use them as per our requirement.

• append(element) – This method adds an element to the right end of deque object.
• appendleft(element) – This method adds an element to the left end of deque object.
• insert(index, element) – This method adds an element at the given index position of deque object.
• extend(iterable) – This method adds multiple elements to the right end of deque object.
• extendleft(iterable) – This method adds multiple elements to the left end of deque object. The elements from the iterable are processed from left to right, so the leftmost element of the iterable becomes the new leftmost element of the deque.

deque.append(element) and deque.appendleft(element)

from collections import deque     # Import collections module

# add element to the right of deque using append method
print("add element to the right of deque using append method")
shbytes_right_deque = deque(['Power BI','Python'])
print(shbytes_right_deque)
shbytes_right_deque.append('ML')         # Add element to the right of deque using append method 
print(shbytes_right_deque)

#add element to the left of deque using appendleft method
print("add element to the left of deque using appendleft method")
shbytes_left_deque = deque(['Power BI','Python'])
print(shbytes_left_deque)
shbytes_left_deque.appendleft('ML')      # Add element to the left of deque using appendleft method
print(shbytes_left_deque)

Program Output

add element to the right of deque using append method
deque(['Power BI', 'Python'])
deque(['Power BI', 'Python', 'ML'])

add element to the left of deque using appendleft method
deque(['Power BI', 'Python'])
deque(['ML', 'Power BI', 'Python'])

• deque.append(element) – element ML added to the right of deque => deque(['Power BI', 'Python', 'ML'])
• deque.appendleft(element) – element ML added to the left of deque => deque(['ML', 'Power BI', 'Python'])

deque.extend(iterable) and deque.extendleft(iterable)

from collections import deque     # Import collections module

# add multiple elements to the right of deque using extend method
print("add multiple elements to the right of deque using extend method")
shbytes_extend_right_deque = deque(['Power BI','Python'])
print(shbytes_extend_right_deque)
shbytes_extend_right_deque.extend(['ML', 'DevOps'])    # Add multiple elements to the right of deque
print(shbytes_extend_right_deque)

# add multiple elements to the left of deque using extendleft method
print("add multiple elements to the left of deque using extendleft method")
shbytes_extend_left_deque = deque(['Power BI','Python'])
print(shbytes_extend_left_deque)
shbytes_extend_left_deque.extendleft(['ML', 'DevOps'])  # Add multiple elements to the left of deque
print(shbytes_extend_left_deque)

Program Output

add multiple elements to the right of deque using extend method
deque(['Power BI', 'Python'])
deque(['Power BI', 'Python', 'ML', 'DevOps'])

add multiple elements to the left of deque using extendleft method
deque(['Power BI', 'Python'])
deque(['DevOps', 'ML', 'Power BI', 'Python'])

• deque.extend(['ML', 'DevOps']) – Elements ML and DevOps added to the right of deque => deque(['Power BI', 'Python', 'ML', 'DevOps'])
• deque.extendleft(['ML', 'DevOps']) – Elements ML and DevOps added to the left of deque => deque(['DevOps', 'ML', 'Power BI', 'Python']). Iterable list elements were processed from left to right. First ML was added to the left. Then DevOps was added to the left of it.

deque.insert(index, element)

from collections import deque     # Import collections module

# add element at an index position in deque using insert method
print("add element at an index position in deque using insert method")

shbytes_index_deque = deque(['Power BI','Python','ML'])
print(shbytes_index_deque)

shbytes_index_deque.insert(1, 'DevOps')  # Add element at index position
print(shbytes_index_deque)

Program Output

add element at an index position in deque using insert method
deque(['Power BI', 'Python', 'ML'])
deque(['Power BI', 'DevOps', 'Python', 'ML'])   # DevOps added at index position 1

From the program output, element DevOps is added to the index position 1 of the deque.

Remove/Pop elements from deque

There are multiple methods to remove/pop elements from deque and we can use them as per our requirement.

• remove(value) – This method removes the first occurrence of value.This method will raise ValueError, if the value does not exists in deque.
• pop() – This method removes and returns an element from the right end of the deque.
• popleft() – This method removes and returns an element from the left end of the deque.
• Both pop() and popleft() methods raise IndexError, if these methods are called on empty deque object.
• clear() – This method removes all elements from the deque.

deque.remove(value) with ValueError

from collections import deque     # Import collections module

# remove first occurrence of element from the deque
print("remove first occurrence of element from the deque")
courses_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(courses_deque)      # Original elements in deque
courses_deque.remove('ML')
print(courses_deque)      # Elements in deque after removing 'ML'

# remove an element from the deque, ValueError if not found
print("remove an element from the deque, ValueError if not found")
courses_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(courses_deque)      # Original elements in deque
try:
	courses_deque.remove('DevOps')    # Devops does not exists in deque, throws ValueError
except ValueError as err:
	print("ValueError", err)
	print(courses_deque)

Program Output

remove first occurrence of element from the deque
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])    # Original elements
deque(['Power BI', 'Python', 'AI', 'LLM', 'ML'])          # First ML is removed

remove an element from the deque, ValueError if not found
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])    # Original elements
ValueError 'DevOps' is not in deque                       # ValueError DevOps not found in elements
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])    # No change in original elements

• courses_deque.remove('ML') – First occurrence of ML removed from the deque elements.
• courses_deque.remove('DevOps') – This raises ValueError, DevOps not found in deque elements.

deque.pop() and deque.popleft()

from collections import deque     # Import collections module

# remove and return the element from right of the deque
print("remove and return the element from right of the deque")
courses_pop_right_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(courses_pop_right_deque)
popped_right_element = courses_pop_right_deque.pop()     # pop element from right
print(courses_pop_right_deque)
print(popped_right_element)

# remove and return the element from left of the deque
print("remove and return the element from left of the deque")
courses_pop_left_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(courses_pop_left_deque)
popped_left_element = courses_pop_left_deque.popleft()  # pop element from left
print(courses_pop_left_deque)
print(popped_left_element)

# pop & popleft method throw index error if no elements are present in deque
print("pop & popleft method throw index error if no elements are present in deque")
empty_deque = deque() 
print(empty_deque)
try:
	pop_element = empty_deque.pop()       # pop or popleft, raise IndexError
except IndexError as err:
	print("IndexError", err)

Program Output

remove and return the element from right of the deque
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM'])
ML

remove and return the element from left of the deque
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
deque(['ML', 'Python', 'AI', 'LLM', 'ML'])
Power BI

pop & popleft method throw index error if no elements are present in deque
deque([])
IndexError pop from an empty deque

• deque.pop() remove and return the element from the right. Element ML was removed and returned.
• deque.popleft() remove and return the element from the left. Element Power BI was removed and returned.
• empty_deque.pop() – raises IndexError

deque.clear()

from collections import deque     # Import collections module

# remove all elements from the deque leaving it with no length
print("remove all elements from the deque leaving it with no length")
courses_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(courses_deque)
courses_deque.clear()   # Removes all elements from the deque
print(courses_deque)

Program Output

remove all elements from the deque leaving it with no length
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
deque([])

Access elements in deque

There are multiple ways to access elements in deque.

• deque elements are stored in sequence like a queue or stack. it supports indexing, but indexing is O(n), unlike to lists where indexing was O(1).
• Slicing is not supported directly on deque. To use slicing, we need to convert it to a list first like deque_list = list(deque)
• index(element, start, stop) – This method returns the index position of the first occurrence of element. It will raise ValueError if element is not found.
  • start (optional) – This is an optional parameter. Search for element will start from this position.
  • stop (optional) – This is an optional parameter. Search for element will stop at this position.

deque indexing and slicing

from collections import deque

# deque indexing
print("deque indexing")
shbytes_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])

print(shbytes_deque[0])   # Output => 'Power BI'
print(shbytes_deque[-1])  # Output => 'ML' (from the right)
print(shbytes_deque[2])   # Output => 'Python'

# deque slicing
print("deque slicing")
deque_list = list(shbytes_deque)[1:3]
print(deque_list)  # Output => ['ML', 'Python']

• Accessing deque element based on positive index like shbytes_deque[0] and negative index position like shbytes_deque[-1]
• Using slicing after converting deque to a list like list(shbytes_deque)[1:3]

Program Output

deque indexing
Power BI
ML
Python

deque slicing
['ML', 'Python']

index(element, start, stop) method

• index(element, start, stop) – This method returns the index position of the first occurrence of element. It will raise ValueError if element is not found.
• start (optional) – This is an optional parameter. Search for element will start from this position.
• stop (optional) – This is an optional parameter. Search for element will stop at this position.

from collections import deque

# returns first match index for element from left
print("returns first match index for element from left")
shbytes_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(shbytes_deque)
element_index = shbytes_deque.index('ML')
print("index of ML - ", element_index)

# return first match index from left at or after start
print("return first match index from left at or after start")
shbytes_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(shbytes_deque)
element_index = shbytes_deque.index('ML', 2)
print("index of ML start from index 2 - ", element_index)

# return first match index from left at or after start and before stop
print("return first match index from left at or after start and before stop")
shbytes_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(shbytes_deque)
element_index = shbytes_deque.index('ML', 1, 3)
print("index of ML start from 2 and stop at 3 - ", element_index)

# ValueError when element not found in deque between start and stop index
print("ValueError when element not found in deque between start and stop index")
shbytes_deque = deque(['Power BI', 'ML', 'Python', "AI", "LLM", "ML"])
print(shbytes_deque)
try:
	element_index = shbytes_deque.index('AWS', 1, 3)
except ValueError as err:
	print("ValueError", err)       # ValueError 'AWS' is not in deque

We have covered 4 scenarios in this program. Using index() method elements will be accessed from left to right.

1. Use shbytes_deque.index('ML') with element value, without start and stop position. Be default start index will be 0 and stop index will be the total length.
2. Use shbytes_deque.index('ML', 2) with element value and start index position. stop index will be the total length.
3. Use shbytes_deque.index('ML', 1, 3) with element value, start and stop index positions.
4. Use shbytes_deque.index('AWS', 1, 3), element AWS not present in deque, it will raise ValueError.
5. With positive start and stop index position, elements will be accessed from left to right and with negative start and stop index position, elements will be accessed from right to left.

Program Output

returns first match index for element from left
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
index of ML -  1

return first match index from left at or after start
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
index of ML start from index 2 -  5

return first match index from left at or after start and before stop
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
index of ML start from 2 and stop at 3 -  1

ValueError when element not found in deque between start and stop index
deque(['Power BI', 'ML', 'Python', 'AI', 'LLM', 'ML'])
ValueError 'AWS' is not in deque

Other built-in methods for deque

There are some other built-in methods provides with deque class.

• deque.reverse() – This method reverses the elements of the deque. This method does not return any value. Same deque object is updated with reverse order of elements.
• deque.rotate(n) – This method rotates n number of elements. If n is positive, then numbers rotate from end to start (right to left) and if n is negative then number rotate from start to end (left to right).
• deque.maxlen – This returns the maximum length of the deque (if specified), or None if there’s no limit.
• deque.count(element) – This method gives the count of given element in deque.
• deque.copy() – This method creates a deep copy of the deque object. Deep means, if we will make a change in copy object, then those changes will not be reflected in the original object.

deque.reverse()

• deque.reverse() – This method reverses the elements of the deque. This method does not return any value. Same deque object is updated with reverse order of elements.

# reverse the elements of the deque in-place and then return None
print("reverse the elements of the deque in-place and then return None")
from collections import deque
courses_deque = deque(['AWS','Python','ML','DevOps','Azure']) 
print(courses_deque)                     # original order of elements
return_value = courses_deque.reverse()
print(courses_deque)                     # elements order is reversed in-place
print("returned value - ", return_value) # return None

Program Output

reverse the elements of the deque in-place and then return None
deque(['AWS', 'Python', 'ML', 'DevOps', 'Azure'])  # original order of elements
deque(['Azure', 'DevOps', 'ML', 'Python', 'AWS'])  # elements order is reversed in-place
returned value -  None  # return None

deque.rotate(n)

• This method rotates n number of elements.
• If n is positive, then numbers rotate from end to start (right to left). One positive rotation is equivalent to pop the element from right and append it to the left => d.appendleft(d.pop()).
• if n is negative then number rotate from start to end (left to right). One negative rotation is equivalent to pop the element from left and append it to the right => d.append(d.popleft())

from collections import deque

# for positive n, rotate the deque n steps to the right
# for positive n, rotate(n) one step equivalent to d.appendleft(d.pop())
print("for positive n, rotate the deque n steps to the right")
print("for positive n, rotate(n) one step equivalent to d.appendleft(d.pop())")
courses_deque = deque(['AWS','Python','ML','DevOps','Azure'])
print(courses_deque)    # original order of elements
courses_deque.rotate(2) # 2 (positive) => elements moved from right to left
print(courses_deque)    # Order of elements after 2 elements rotation

# for negative n, rotate the deque n steps to the left
# for negative n, rotate(n) one step equivalent to d.append(d.popleft())
print("for negative n, rotate the deque n steps to the left")
print("for negative n, rotate(n) one step equivalent to d.append(d.popleft())")
courses_deque = deque(['AWS','Python','ML','DevOps','Azure'])
print(courses_deque)     # original order of elements
courses_deque.rotate(-2) # -2 (negative) => elements moved from left to right
print(courses_deque)     # Order of elements after 2 elements rotation

• courses_deque.rotate(2) => Moves 2 elements from right to left
• courses_deque.rotate(-2) => Moves 2 elements from left to right

Program Output

for positive n, rotate the deque n steps to the right
for positive n, rotate(n) one step equivalent to d.appendleft(d.pop())
deque(['AWS', 'Python', 'ML', 'DevOps', 'Azure'])  # Original order of elements
deque(['DevOps', 'Azure', 'AWS', 'Python', 'ML'])  # Two elements (DevOps, Azure) moved from right to left

for negative n, rotate the deque n steps to the left
for negative n, rotate(n) one step equivalent to d.append(d.popleft())
deque(['AWS', 'Python', 'ML', 'DevOps', 'Azure'])  # Original order of elements
deque(['ML', 'DevOps', 'Azure', 'AWS', 'Python'])  # Two elements (AWS & Python) moved from left to right

count(element), copy(), maxlen

count(element)

• deque.count(element) – This method gives the count of given element in deque.

from collections import deque

# count the number of deque elements equal to given element
print("count the number of deque elements equal to given element")
shbytes_deque = deque(['AWS','Python','ML','DevOps','Python'])
print(shbytes_deque)
element_count = shbytes_deque.count('Python')
print("Python element count - ", element_count)

copy()

• deque.copy() – This method creates a deep copy of the deque object. Deep means, if we will make a change in copy object, then those changes will not be reflected in the original object.

from collections import deque

# create a deep copy of the deque
print("create a deep copy of the deque")
shbytes_deque = deque(['AWS','Python','ML','DevOps','Python']) 
print(shbytes_deque)    # Original object
copy_deque = shbytes_deque.copy() # Create deep copy of elements
print(copy_deque)       # Copied elements
copy_deque.append('Data Science') # Append elements in copied object
print(shbytes_deque)    # No change in original object
print(copy_deque)       # Elements in copied object after append

Program Output

create a deep copy of the deque
deque(['AWS', 'Python', 'ML', 'DevOps', 'Python'])  # Original object elements
deque(['AWS', 'Python', 'ML', 'DevOps', 'Python'])  # Copied object elements
deque(['AWS', 'Python', 'ML', 'DevOps', 'Python'])  # No change in original object 
deque(['AWS', 'Python', 'ML', 'DevOps', 'Python', 'Data Science']) # Elements appended to copied object

maxlen

• deque.maxlen – This returns the maximum length of the deque (if specified), or None if there’s no limit.

from collections import deque

# maximum size of a deque or None if unbounded
print("maximum size of a deque or None if unbounded")
shbytes_deque = deque(['AWS','Python','ML','DevOps','Python']) # deque without maxlen
print(shbytes_deque)  # Original object
deque_maxlen = shbytes_deque.maxlen # maxlen will return None
print(deque_maxlen)   # Output => None

#maximum size of a deque or None if unbounded
#maxlen
print("maximum size of a deque or None if unbounded")
from collections import deque
shbytes_deque = deque(['AWS','Python','ML'], 5) # deque with maxlen=5
print(shbytes_deque)   # Original object
deque_maxlen = shbytes_deque.maxlen  # maxlen will return 5
print(deque_maxlen)    # Output => 5

Summary

In this article, we learned about deque collection and it’s built-in methods in Python. Following topics were discussed:

Code – Github Repository

All code snippets and programs for this article and for Python tutorial, can be accessed from Github repository – Comments and Docstring in Python.

Interview Questions & Answers

Q: Provide a performance comparison between deque and list?

Following table show the comparison between Time Complexity for different operations performed on deque and list object.

Operation	deque	list
Append elements to the end	O(1)	O(1)
Append elements to the start	O(1)	O(n)
Pop elements to the end	O(1)	O(1)
Pop elements to the start	O(1)	O(n)
Insert elements at arbitrary position	O(n)	O(n)
Delete elements from arbitrary position	O(n)	O(n)

Q: Give scenarios in which we should use deque or we should use list?

Q: What are the memory advantages of using a deque over a list?

• Both deque and lists are dynamic arrays, deque is implemented as a doubly linked list. This makes deque more memory-efficient when adding or removing elements from both ends compared to a list.
• deque avoids the overhead of resizing that occurs with lists when their capacity is exceeded. In case of frequent insertions and deletions deque is much efficient compared to list.