pythonpython-3.xdictionaryordereddictionary

Complexity of deleting a key from python ordered dict


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?


Solution

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

    Since the average case complexity of all the above operations is constant, the average case complexity of OrderedDict.__delitem__ is constant as well.

    Do note however that the worst case complexity of deleting a key from a dictionary is O(n), so the same applies for ordered dictionaries as well.