Deque in Python


Deque (double ended queue) is a data structure that can be used to insert or delete data elements at both it ends. It is directly supported in Python through collections module.

  • "Collections", is a Python Module that defines Deque.
  • To begin using Deque in your python program use the code given below.
import collections
de = collections.deque([1,2,3])
  • Deque requires O(1) time to perform the operations of append and pop. Whereas, a list requires O(N) complexity.
    For reference a machine takes 1s to perform 10^6 operations.
  • Elements can be accessed at any index. Just like an array.If in an example case you need to access (say) the 4th element, you can can access simply by the index.

basic-deque

Question

Time Complexity for append and pop operations?

O(1)
O(n*logn)
O(n^2)
O(n)
Refer the introduction above.

Operations on deque

The operations supported by deque are:

  • append
  • appendleft
  • pop and popleft
  • index
  • insert
  • remove
  • count
  • extend
  • extendleft
  • reverse
  • rotate
  • len

1. append() :- This function is used to insert the value in its argument to the right end of deque. Append simply appends the element you enter to the right end of the deque.

import collections
de = collections.deque([1,2,3])
de.append(4)
de

out1

2. appendleft() :- This function is used to insert the value in its argument to the left end of deque.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de

out2

3. pop() & popleft() :- These methods are used to delete an argument from the right end and also from the left end of the deque respectively.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de
de.popleft()
de

out3

out4

Question

What if the pop is performed on an empty deque?

The output will be:

out15
4. index(ele, beg, end) :- This function returns the first index of the value mentioned in arguments, starting searching from beg till end index. This simply searches the occurence for the 'ele'and returns it.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)

out5

5. insert(i, a) :- This function inserts the value mentioned in arguments(a) at index(i) specified in arguments. This is similar to in array. It overrides the value, if the value is present in prior to the insertion at the given index.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de

out6

Question

What if index is out of bound?

The output will be the lowerbound or upperbound of deque if the index is out of bounds at maximum or minimum element respectively.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.remove(2)
de.insert(-5,10)
de

out17

6. remove() :- This function removes the first occurrence of value mentioned in arguments. Searches, for the occurence of the element and deletes whenever, it finds the required element.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de

out7

7. count() :- This function counts the number of occurrences of value mentioned in arguments. Increements to the value of the number of times a number is present.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)

out8

Question

How do you think can we add more that one elements?

Extend
Multiple append lefts
Multiple appends
Not in my knowledge.
Please, see the next sections. It is explained ahead!

8. extend(iterable) :- This function is used to add multiple values at the right end of deque. The argument passed is an iterable. Iteratively, it just inserts the values into the deque.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)
de.extend([9,8,7])
de

out9
9. extendleft(iterable) :- This function is used to add multiple values at the left end of deque. The argument passed is an iterable. Order is reversed as a result of left appends.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)
de.extend([9,8,7])
de.extendleft([-1,-2,-3])
de

out11

10. reverse() :- This function is used to reverse order of deque elements. Just as in other cases for other data-structures.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)
de.extend([9,8,7])
de.extendleft([-1,-2,-3])
de.reverse()
de

out12

11. rotate() :- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to left. By default the rotation is to right.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)
de.extend([9,8,7])
de.extendleft([-1,-2,-3])
de.rotate()
de

out13
Negative Rotation is:

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)
de.extend([9,8,7])
de.extendleft([-1,-2,-3])
de.reverse()
de.rotate(-3)
de

out14
12. len() :- Gives out the length of the Deque.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)
de.extend([9,8,7])
de.extendleft([-1,-2,-3])
de.reverse()
de.rotate(-3)
de
len(de)

out16

Question

The function/method used for reversing the order?

reverse()
rotate()
append()
None of the above
Please, see the next sections. It is explained ahead!

With this article at OpenGenus, you must have a complete idea of using deque in Python. Enjoy.