Complexity of deleting a key from python ordered dict
The implementation of OrderedDict.__delitem__
in Python 3.7 is as follows:
def __delitem__(self, key, dict_delitem=dict.__delitem__):
'od.__delitem__(y) <==> del od[y]'
# Deleting an existing item uses self.__map to find the link which gets
# removed by updating the links in the predecessor and successor nodes.
dict_delitem(self, key)
link = self.__map.pop(key)
link_prev = link.prev
link_next = link.next
link_prev.next = link_next
link_next.prev = link_prev
link.prev = None
link.next = None
This code does 3 things:
- Remove an item from the internal key-value dictionary.
- Remove a node from the dictionary holding linked list nodes.
- Delete an item from a doubly linked list.
Since all of the operations above take constant time, the complexity of OrderedDict.__delitem__
is constant as well.
Riken Shah
Computer Science Graduate Student at NC State. Enjoys and Excels in working at the intersection of data science and software engineering paradigms.
Updated on June 05, 2022Comments
-
Riken Shah almost 2 years
Deleting a key from a python
dict
ordefaultdict
in python is O(1) operation, as mentioned here and here. To remove a key fromOrderedDict
, we can either usedel d[key]
or usepopitem()
method, as mentioned in the docs.What is the underlying implementation of
OrderedDict
and the time complexity ofdel
operation?Edit: This answer OrderedDict performance (compared to deque) , refers to the complexity of
del
inOrderedDict
as being O(1). However, how can we justify it at implementation detail level?