What is a time complexity of move_to_end operation for OrderedDict in Python 3?

Question

I've found the source code and it seems to be O(1), since it's basically an update of a linked list and a dict. Though I'm not sure.

What do you think? Thank you!

Answer 1

You can check the pure Python implementation of OrderedDict.move_to_end(), which is equivalent to the C implementation:

def move_to_end(self, key, last=True):
    '''Move an existing element to the end (or beginning if last is false).
    Raise KeyError if the element does not exist.
    '''
    link = self.__map[key]
    link_prev = link.prev
    link_next = link.next
    soft_link = link_next.prev
    link_prev.next = link_next
    link_next.prev = link_prev
    root = self.__root
    if last:
        last = root.prev
        link.prev = last
        link.next = root
        root.prev = soft_link
        last.next = link
    else:
        first = root.next
        link.prev = root
        link.next = first
        first.prev = soft_link
        root.next = link

Basically, this method looks up a link in a linked list in a dictionary self.__map and updates the previous and next pointers for the link and its neighbors.
Since all of the operations above take constant time, the complexity of OrderedDict.move_to_end() is constant as well.