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!
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With