Deleting a key from a python dict
or defaultdict
in python is O(1) operation, as mentioned here and here. To remove a key from OrderedDict
, we can either use del d[key]
or use popitem()
method, as mentioned in the docs.
What is the underlying implementation of OrderedDict
and the time complexity of del
operation?
Edit: This answer OrderedDict performance (compared to deque) , refers to the complexity of del
in OrderedDict
as being O(1). However, how can we justify it at implementation detail level?
The implementation of
OrderedDict.__delitem__
in Python 3.7 is as follows:This code does 3 things:
Since all of the operations above take constant time, the complexity of
OrderedDict.__delitem__
is constant as well.