(2022.05.04 Wed)

Doubly Linked List雙向鏈表

采用基于array形式的鏈表，如Python list求橄，為找到某特定元素只需要知道該元素的index即可，查找方便晰奖，但在非array鏈表實現(xiàn)過程中查找某特定元素需要從表頭開始遍歷鏈表直到找到谈撒，效率低下。在這里給鏈表實現(xiàn)引入了定位(position)匾南，相當于對某特定元素a加標簽荞胡，保留該標簽可隨時找到a们妥，不管鏈表如何變化，方便了定位。

為了理解定位信息编丘，可設(shè)想這樣一種情況：多人排隊做活宣，Jack身在其中滑蚯，Jack前面的人會減少党巾，后面的人會增加，前面也有可能有人插隊臂聋，但不管隊伍怎么變化光稼，Jack總能在隊伍中被輕易認出或南。好像Jack頭上有個標志牌，只要看到該牌子就能找到Jack艾君。鏈表中加入的定位信息采够，相當于這個標志牌。

這里使用雙向鏈表Doubly Linked List冰垄，即表頭表尾加占位符號header和trailer蹬癌，這樣保證除header和trailer外的所有節(jié)點都有prev和next屬性，便于執(zhí)行對鏈表的修改虹茶。header和trailer不保存鏈表信息逝薪。

實現(xiàn)

這里我們給出帶位置的雙向鏈表PositionalList的實現(xiàn)過程。

首先設(shè)置雙向鏈表基類_DoubleLinkedBase蝴罪。
在基類中定義基本方法董济，即插入和刪除。設(shè)置嵌入類nested class要门，即_Node用于封裝節(jié)點信息感局，封裝內(nèi)容包括，1.節(jié)點所代表的元素, 2.節(jié)點前置點, 3.節(jié)點后置點暂衡⊙ⅲ基類的header和trailer都初始化為空值None，且互為后置前置節(jié)點狂巢。加入__slots__可在實例化時減少內(nèi)存的使用撑毛，特別是大量實例化的時候。

class _DoubleLinkedBase:

    class _Node:
        __slots__ = '_element', '_prev', '_next'
        def __init__(self, element, prev, next):
            self._element = element
            self._prev = prev
            self._next = next

    def __init__(self):
        self._header = self._Node(None, None, None)
        self._trailer = self._Node(None, None, None)
        self._header._next = self._trailer
        self._trailer._prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def _insert_between(self, e, predecessor, successor):
        newest = self._Node(e, predecessor, successor)
        predecessor._next = newest
        successor._prev = newest
        self._size += 1
        return newest

    def _delete_node(self, node):
        predecessor = node._prev
        successor = node._next
        predecessor._next = successor
        successor._prev = predecessor
        self._size -= 1
        element = node._element
        node._prev = node._next = node._element = None
        return element

接下來創(chuàng)建帶位置信息的類PositionalList唧领，其繼承自_DoubleLinkedBase藻雌。在該類中，創(chuàng)建nested class Position斩个，該類包含了節(jié)點的信息和所在的容器(即鏈表)胯杭。該鏈表的內(nèi)置方法包括

• _make_position: 將輸入節(jié)點封裝為Position類，對header和trailer不執(zhí)行該操作
• _validate: 驗證輸入的對象p是否受啥，1. 是Position類做个，2. 在同一個容器(鏈表)中，3. 其下一個節(jié)點為None滚局，即是否可用居暖。驗證通過，返回該輸入對象的節(jié)點信息藤肢，即p._node
• _insert_between: 在兩個節(jié)點間插入新節(jié)點太闺，繼承了_DoubleLinkedBase的中方法，返回封裝后的Position類對象
• 查詢first last before after: 如名字所示嘁圈，查詢鏈表的首省骂、尾元素蟀淮，和指定元素的前、后元素钞澳。返回結(jié)果是經(jīng)過封裝的Position類對象灭贷。注意，鏈表的首元素非header元素略贮，而是header的下一個元素，尾元素同理仗岖。
• 更新add_first add_last add_before add_after: 更新逃延，返回都是經(jīng)過封裝的Position類對象
• 刪除替換delete replace: 略

class PositionalList(_DoubleLinkedBase):

    #------------------------ nested Position class --------------------------
    class Position:

        def __init__(self, container, node):
            self._container = container
            self._node = node

        def element(self):
            return self._node._element

        def __eq__(self, other):
            return type(self) is type(other) and other._node is self._node

        def __ne__(self, node):
            return not (self == node)
    #---------------------------- utility method -------------------------------
    def _validate(self, p):
        '''Return position s node, or raise appropriate error if invalid.'''
        if not isinstance(p, self.Position):
            raise TypeError('p must be of Position type')
        if p._container is not self:
            raise ValueError('P does not belong to this container')
        if p._node._next is None:
            raise ValueError('p is no longer valid')
        return p._node

    def _make_position(self, node):
        if node is self._header or node is self._trailer:
            return None
        else:
            return self.Position(self, node)

    def first(self):
        # first node is NOT header, but the first after header
        return self._make_position(self._header._next)

    def last(self):
        return self._make_position(self._trailer._prev)

    def before(self, p):
        n = self._validata(p)
        return self._make_position(n._prev)

    def after(self, p):
        n = self._validate(p)
        return self._make_position(n._next)

    def __iter__(self):
        cursor = self.first()
        while cursor is not None:
            yield cursor.element()
            cursor = self.after(cursor)

    def _insert_between(self, e, predecessor, successor):
        node = super()._insert_between(e, predecessor, successor)
        return self._make_position(node)

    def add_first(self, e):
        return self._insert_between(e, self._header, self._header._next)

    def add_last(self, e):
        return self._insert_between(e, self._trailer._prev, self._trailer)

    def add_before(self, p, e):
        original = self._validate(p)
        return self._insert_between(e, original._prev, original)

    def add_after(self, p, e):
        original = self._validate(p)
        return self._insert_between(e, original, original._next)

    def delete(self, p):
        original = self._validate(p)
        return self._delete_node(original)

    def replace(self, p, e):
        original = self._validate(p)
        old_old = original._element
        original._elemenet = e
        return old_value

應(yīng)用如下

>>> pl = PositionalList()
>>> pl._header._element
>>> pl._trailer._element
>>> pl._header._next._element
>>> a1 = pl.add_first(365) # 首元素365
>>> a2 = pl.add_after(a1, 10086) # 在365后加入10086
>>> a3 = pl.add_before(a2, 1314) # 在10086前計入1314
# 此時該鏈表中元素順序是365->1314->10086，位置順序為a1->a3->a2
>>> a3.element()
1314
>>> a3._node._next._element
10086
>>> a3._node._prev._element
365
>>> print(a1._node._prev._element)
None

復(fù)雜度分析

O(1)

Reference

1 Goodrich and etc., Data Structures and Algorithms in Python