Python 3 中 OrderedDict 的 move_to_end 操作的时间复杂度是多少？

Question

我找到了源代码，它似乎是 O(1)，因为它基本上是一个链表和一个字典的更新。虽然我不确定。

你怎么认为？谢谢！

Answer 1

您可以检查 的纯 Python 实现OrderedDict.move_to_end()，它等效于 C 实现：

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

基本上，此方法在字典的链表中查找链接，self.__map并更新链接及其邻居的上一个和下一个指针。
由于上述所有操作都需要恒定的时间，因此 的复杂度OrderedDict.move_to_end()也是恒定的。