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:
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.
