CODEWITHSUNDEEP
pythonalgorithmdata-structurestime-complexitydeque
Max Mikhaylov
Max Mikhaylov

Reputation: 792

Time complexity: deleting element of deque

What is the time complexity of deleting an element of collections.deque?

E.g.:

deq = collections.deque([1, 2, 3])
del deq[1]

Upvotes: 10

Views: 9578

Answers (1)

Raymond Hettinger
Raymond Hettinger

Reputation: 226754

Summary

The time complexity is O(n) where n is the distance to the nearest endpoint. The total size of the deque does not matter.

Reason Why

The implementation of deque is a doubly-linked list of fixed length blocks. Deletion of an element requires individually moving all of the elements between the deleted point and the nearest endpoint.

Illustration

Consider the following example:

>>> d = deque('abcdefghijklmnop')
>>> del d[3]

For illustration purposes, assume a block size of three (the actual block size is 64) for the following data layout:

ab  ⇄  cde  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op     # State before deletion
        ×                                     # Step 1, delete "d"
ab  ⇄  c-e  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op     
       →                                      # Step 2, move "c" to right 
ab  ⇄  -ce  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op  
 →                                            # Step 3, move "b" to right
a-  ⇄  bce  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op  
→                                             # Step 4, move "a" to right
 a  ⇄  bce  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op     # Final state after deletion

As you can see, the data elements between the deleted element and the end-point all have to move over by one to the right.

If "k" were being deleted, the elements "lmnop" would all move one the the left. The algorithm is smart enough to work towards the closest end point.

Upvotes: 22

Related Questions