python中的OrderedDict是对双向链表的一个实现。

初始化

from weakref import proxy as _proxy

class _Link(object):
    __slots__ = 'prev', 'next', 'key', '__weakref__'

class OrderedDict(dict):
    'Dictionary that remembers insertion order'


    # The internal self.__map dict maps keys to links in a doubly linked list.
    # The circular doubly linked list starts and ends with a sentinel element.
    # The sentinel element never gets deleted (this simplifies the algorithm).
    # The sentinel is in self.__hardroot with a weakref proxy in self.__root.
    # The prev links are weakref proxies (to prevent circular references).
    # Individual links are kept alive by the hard reference in self.__map.
    # Those hard references disappear when a key is deleted from an OrderedDict.

    def __init__(self, other=(), /, **kwds):
        '''Initialize an ordered dictionary.  The signature is the same as
        regular dictionaries.  Keyword argument order is preserved.
        '''
        try:
            self.__root
        except AttributeError:
            self.__hardroot = _Link()
            self.__root = root = _proxy(self.__hardroot)
            root.prev = root.next = root
            self.__map = {}
        self.__update(other, **kwds)

首先类定义了一个__hardroot，并且创建弱引用root和self.__root。通过弱引用root创建一个环。

关于弱引用，首先要知道python的垃圾回收机制，如果一个变量的计数为$0$那么就会释放内存。但是当我们创建一个引用循环时，例如对上面的双向链表节点创建一个自身的环时，计数值变为$3$，将无法释放占用的内存（python中的gc模块可以对引用循环进行内存释放）。
一个简单的case

import sys
import weakref
class Link:
   __slots__ = "prev", "next", "key", "__weakref__"
   def __init__(self) -> None:
       pass
   def __del__(self):
       print("__del__")

当我们执行下面的代码时，del root是没有输出的，而删除_s时会因为引用的对象已不存在而报错。

root = Link()
root.prev = root
root.next = root
del root
s = Link()
_s = weakref.proxy(s)
_s.prev = _s
_s.next = _s
del(s)
print(_s)

关于弱引用可以看What is weak reference in Python和python cookbook。

添加元素

def __setitem__(self, key, value,
                dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
    'od.__setitem__(i, y) <==> od[i]=y'
    # Setting a new item creates a new link at the end of the linked list,
    # and the inherited dictionary is updated with the new key/value pair.
    if key not in self:
        self.__map[key] = link = Link()
        root = self.__root
        last = root.prev
        link.prev, link.next, link.key = last, root, key
        last.next = link
        root.prev = proxy(link)
    dict_setitem(self, key, value)

OrderedDict类继承自dict基类，通过父类的方法添加键值对。如果元素不在链表中，则在root环中添加该元素。注意root为弱引用。

删除元素

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

__marker = object()

def pop(self, key, default=__marker):
    '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
    value.  If key is not found, d is returned if given, otherwise KeyError
    is raised.
    '''
    marker = self.__marker
    result = dict.pop(self, key, marker)
    if result is not marker:
        # The same as in __delitem__().
        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
        return result
    if default is marker:
        raise KeyError(key)
    return default

遍历

def __iter__(self):
    'od.__iter__() <==> iter(od)'
    # Traverse the linked list in order.
    root = self.__root
    curr = root.next
    while curr is not root:
        yield curr.key
        curr = curr.next

def __reversed__(self):
    'od.__reversed__() <==> reversed(od)'
    # Traverse the linked list in reverse order.
    root = self.__root
    curr = root.prev
    while curr is not root:
        yield curr.key
        curr = curr.prev

删除尾端元素

def popitem(self, last=True):
    '''Remove and return a (key, value) pair from the dictionary.
    Pairs are returned in LIFO order if last is true or FIFO order if false.
    '''
    if not self:
        raise KeyError('dictionary is empty')
    root = self.__root
    if last:
        link = root.prev
        link_prev = link.prev
        link_prev.next = root
        root.prev = link_prev
    else:
        link = root.next
        link_next = link.next
        root.next = link_next
        link_next.prev = root
    key = link.key
    del self.__map[key]
    value = dict.pop(self, key)
    return key, value

last用来标记从尾端删除还是前端删除。

移动元素至末尾

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

这个方法在缓存中，如RLU，会用到。