What is the time complexity of deleting an element of collections.deque
?
E.g.:
deq = collections.deque([1, 2, 3])
del deq[1]
One dequeue() operation takes O(1) time. To remove N elements from the queue will take O(N) time (in total). Similarly, One enqueue () operation takes O(1) time. To insert N elements in the queue will take O(N) time (in total).
For delete any element we can choos eleemnt in one time so the time complexity of the stack is o(1).
Time Complexity : o(1) Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack. The top most element of the stack is stored in an another variable and then the top is decremented by 1.
clear() removes all the elements from a deque container, thus making its size 0. All the elements of the deque are removed using clear() function.
The time complexity is O(n) where n is the distance to the nearest endpoint. The total size of the deque does not matter.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With