Complexity of deleting a key from python ordered dict

Question

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?

Answer 1

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