python collections.Ordereddict 源码中, 用来记录有序的结构，怎么理解？不是能看懂为什么这样存储。

[Nisenasdf]

代码如下, 其中初始化时root[:] = [root, root, None] 和设置值时last[1] = root[0] = self.__map[key] = [last, root, key] 这边怎么理解呢？谢谢啦

class OrderedDict(dict):
    'Dictionary that remembers insertion order'
    # An inherited dict maps keys to values.
    # The inherited dict provides __getitem__, __len__, __contains__, and get.
    # The remaining methods are order-aware.
    # Big-O running times for all methods are the same as regular dictionaries.

    # 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).
    # Each link is stored as a list of length three:  [PREV, NEXT, KEY].

    def __init__(*args, **kwds):
        '''Initialize an ordered dictionary.  The signature is the same as
        regular dictionaries, but keyword arguments are not recommended because
        their insertion order is arbitrary.

        '''
        if not args:
            raise TypeError("descriptor '__init__' of 'OrderedDict' object "
                            "needs an argument")
        self = args[0]
        args = args[1:]
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))
        try:
            self.__root
        except AttributeError:
            self.__root = root = []                     # sentinel node
            root[:] = [root, root, None]
            self.__map = {}
        self.__update(*args, **kwds)

    def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
        '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:
            root = self.__root
            last = root[0]
            last[1] = root[0] = self.__map[key] = [last, root, key]
        return dict_setitem(self, key, value)

    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_prev, link_next, _ = self.__map.pop(key)
        link_prev[1] = link_next                        # update link_prev[NEXT]
        link_next[0] = link_prev                        # update link_next[PREV]

    def __iter__(self):
        'od.__iter__() <==> iter(od)'
        # Traverse the linked list in order.
        root = self.__root
        curr = root[1]                                  # start at the first node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[1]                              # move to next node

    def __reversed__(self):
        'od.__reversed__() <==> reversed(od)'
        # Traverse the linked list in reverse order.
        root = self.__root
        curr = root[0]                                  # start at the last node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[0]                              # move to previous node

    def clear(self):
        'od.clear() -> None.  Remove all items from od.'
        root = self.__root
        root[:] = [root, root, None]
        self.__map.clear()
        dict.clear(self)

[Contextualist]

关键在于
> # Each link is stored as a list of length three: [PREV, NEXT, KEY].
就是说 od 的有序实际上是由一个双向链表实现的。由于 Python 里 list 是可变对象，一个节点 list 里的 PREV 和 NEXT 是对前驱和后继节点 list 的引用

初始化那里， root 前驱和后继都指向自己，方便接下来实现环链。
那句核心操作应该联系上文：
last = root[0]
last[1] = root[0] = [last, root, key] # self.__map[key] 可以稍后再看
这句话实现了在 root 前插入节点，建议楼主自己在纸上画一下。

[zhy0216]

是个双向链表 [0] 和 [1] 理解成 .prev 和 .next 就可以了
root[:] = [root, root, None] ==> root = [None, None, None]; root[0] = root; root[1] = None;

[Nisenasdf]

@Contextualist 今天补了下双向链表和哨兵的相关知识，大体上能理解为什么能这样做了。然而还是有几点不清楚。
1. 为什么要采用这种结构来保存有序性，这样做的用意是什么，为什么不采用简单的 list 来做呢？
2. 这种用 list 实现双向链表的做法妥当吗？实际上，在每一个 list 的三个元素中，前两个(prev, next)保存的什么，指针？ 这样用 list 来实现双向链表会数据冗余吗?
谢谢啦！ 我现在还不是能理解透彻，望指教！

[Contextualist]

@Nisenasdf
我只会从静态语言的角度解释，所以下面说的不一定是对的。
1. 这个涉及到数组 (Python 里的近似就是元素都是不可变对象的 list ，就是你所说的“简单的 list ”) 和链表这两种基本数据结构的本质用途：二者同样是序列，数组按 index 存值取值，对于**固定**的序列存取都是 O(1)；双向链表按 pre 、 next 遍历，因为节点是可变对象，可以被引用 (对于 od 来说就是 self.__map[key] 的用途) ，对于**动态**的序列存取也是 O(1)。
od 显然要维护一个动态序列，链表就是个很好的选择。你可能会想到 list 可以 del 某个元素，但这其实破坏了数组的规则 (Python 的 list 不是数组)， index 都被改变了，不能根据原来的 index 来存取。那元素是可变对象的 list ([[key1], [key2], ...]) 呢？这样也可以用不受 index 影响的不变引用来 O(1) 存取。但其实 list 的 del 效率是很低的，是 O(n)，因为要重新分配 index 。总之，对于动态序列，用链表就对了。

2. 上面的问题纠结完了，这个问题就很好回答。双向链表的节点必须要 pre ， next ，和值这三部分，没有任何冗余。其次，引用其实不是很占空间。再说了，牺牲了空间，换来了时间。

题外话：关于指针和引用，请看： https://zh.m.wikipedia.org/wiki/參照