在看 collections.OrderedD...">
美文网首页
python双向链表的疑问(Question)

python双向链表的疑问(Question)

作者: Nisen | 来源:发表于2016-11-23 00:07 被阅读75次

    问题<a id="sec-1" name="sec-1"></a>

    在看 collections.OrderedDict 的源码时,对于它如何构造有序的结构这一部分不是很理解,代码如下:

    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)
    

    主要是对于初始化里和set方法里的做法不清楚, wtf doing here…:

                self.__root = root = []                     # sentinel node
                root[:] = [root, root, None]
                self.__map = {}
    # 和
                root = self.__root
                last = root[0]
                last[1] = root[0] = self.__map[key] = [last, root, key]
    

    后来在网上提问并且自己查询了相关资料后明白这是个带哨兵的双向链表的实现,关于双向链表的知识自己补了下,可以参见这里这里

    然而对于它为什么要这样实现我还不是很清楚,留待以后继续探究。

    这里 是我在v2ex上关于这个问题的提问。

    相关文章

      网友评论

          本文标题:python双向链表的疑问(Question)

          本文链接:https://www.haomeiwen.com/subject/zlvmpttx.html