Python資料結構與演算法（2.4）——雙向鏈表

0. 學習目標

單鏈表只有一個指向直接后繼的指標來表示結點間的邏輯關系，因此可以方便的從任一結點開始查找其后繼結點，但要找前驅結點則比較困難，雙向鏈表是為了解決這一問題，其使用兩個指標表示結點間的邏輯關系，在上一節中我們已經討論了單鏈表及其相關操作的實作，本節中我們將重點討論雙向鏈表及其相關操作的實作，
通過本節學習，應掌握以下內容：

• 雙向鏈表的基本概念及其優缺點
• 雙向鏈表基本操作的實作
• 利用雙向鏈表的基本操作實作復雜演算法

1. 雙向鏈表簡介

1.1 雙向鏈表介紹

雙向鏈表 (doubly linked list) 與單鏈表相似，同樣使用結點和指標的相關概念，屬于順序表的鏈式存盤結構，單鏈表和雙向鏈表的唯一區別在于雙向鏈表是用兩個指標表示結點間的邏輯關系，增加了一個指向其直接前驅的指標域，這樣形成的鏈表有兩條不同方向的鏈——前驅鏈和后繼鏈，因此稱為雙向鏈表，或稱為雙鏈表，

1.2 雙向鏈表結點類

在雙向鏈表中，根據已知結點查找其直接前驅結點可以與查找其直接后繼結點一樣方便，與單鏈表相同，雙向鏈表同樣可以分為帶有頭結點和不帶頭結點兩類，本節僅討論帶頭結點的雙向鏈表，雙向鏈表的結點示意圖如下所示，每個結點都有兩個指標——指向直接后繼的指標 next 和指向直接前驅的指標 previous：

用 Python 實作雙向鏈表結點類如下：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.previous = None

    def __str__(self):
        return str(self.data)

previous 變數指向直接前驅結點，而 next 變數保留對直接后繼結點的參考，而 data 變數用于存盤資料，多載 __str__ 方法用于便于列印結點物件，

1.3 雙向鏈表優缺點

雙向鏈表的優點在于給定雙向鏈表中的一個節點，我們可以雙向遍歷，直接訪問它的前驅結點，這樣在需要查找前驅的操作中，就不必再從頭開始遍歷整個鏈表，極大的方便了諸如洗掉結點等操作，
而雙向鏈表的主要缺點如下：
? 每個結點需要一個額外的前驅指標，需要更多的空間；
? 結點的插入或洗掉需要更多的指標修改操作，

2. 雙向鏈表實作

類似于單鏈表，接下來讓我們實作一個帶有頭結點的雙鏈表類，并用頭指標標識鏈表的開頭，如果你還不了解單鏈表，可以參考《單鏈表及其操作實作》相關介紹，

2.1 雙向鏈表的初始化

雙向鏈表的初始化建立一個空的帶頭結點的單鏈表，其表長 length 初始化為 0，此時鏈表中沒有元素結點，只有一個頭結點：

class DoublyLinkedList:
    def __init__(self, data=None):
        self.length = 0
        # 初始化頭結點
        head_node = Node()
        self.head = head_node

創建雙向鏈表 DoublyLinkedList 物件的時間復雜度為 O ( 1 ) O(1) O(1)，

NOTE：如果你還記得繼承機制的話，我們也可以令 DoublyLinkedList 繼承自在《單鏈表及其操作實作》中實作的 SinglyLinkedList，可以極大的化簡雙向鏈表的實作，

2.2 獲取雙向鏈表長度

求取雙向鏈表長度只需要多載 __len__ 從物件回傳 length 的值，因此時間復雜度為 O ( 1 ) O(1) O(1)：

    def __len__(self):
        return self.length

2.3 讀取指定位置元素

雙向鏈表中讀取指定位置元素的演算法與單鏈表完全相同，只需要使用后繼鏈訪問每一個結點即可，因此操作的復雜度同樣為 O ( n ) O(n) O(n)，接下來我們將多載 __getitem__ 操作實作讀取鏈表指定位置元素的操作；同時，我們希望確保索引在可接受的索引范圍內，否則將引發 IndexError 例外：

    def __getitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1
            return current.data

類似的，我們也可以實作修改指定位置元素的操作，只需要多載 __setitem__ 操作，其復雜度同樣為 O ( n ) O(n) O(n)：

    def __setitem__(self, index, value):
        if index > self.length - 1 or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1

            current.data = value

2.4 查找指定元素

與單鏈表相同，當查找指定元素時，需要設定一個跟蹤鏈表結點的指標 current，令其順著 next 域依次指向每個結點，每指向一個結點就判斷其值是否等于指定值 value，若是則回傳該結點索引；否則繼續往后搜索，如果鏈表中無此元素，則引發 ValueError 例外，其時間復雜度為 O ( n ) O(n) O(n)：

    def locate(self, value):
        count = -1
        current = self.head
        while current != None and current.data != value:
            count += 1
            current = current.next
        if current and current.data == value:
            return count
        else:
            raise ValueError("{} is not in sequential list".format(value))

2.5 在指定位置插入新元素

在指定位置插入新元素有兩種不同的方法，一種是找到待插入位置的結點 current，然后將待插結點插入 current 之前；另一種方法是找到待插入位置結點的前驅結點 prev，然后待插結點插入 prev 之后，兩種方法的操作略有不同，這里以第二種方法的操作為例，第一種方法的具體操作留給大家進行推導，
由于 prev 指向待插入位置的后繼結點，因此如果插入位置為串列末尾，由于 prev.next = None，無法使用 prev.next.previous，而在鏈表中間部位 prev.next.previous = prev，所以顯然插入鏈表中間位置和鏈表末尾的操作有所不同，
(1) 在雙向鏈表的末尾插入一個結點步驟如下：

• 遍歷串列直到最后一個結點，創建新結點；
• 將新節點的 previous 指標指向鏈表的最后一個結點；
• 更新原鏈表最后一個結點的 next 指標指向新結點，

(2) 在雙鏈表中間插入結點與單鏈表類似，但是需要更多的步驟用于修改指標：

• 首先遍歷鏈表到插入位置的前驅結點 prev，創建新結點；
• 新結點的 next 指標指向要插入新結點位置的下一個節點，新結點的 previous 指標指向 prev；
• 插入位置后繼節點的 previous 指向新節點，prev 結點的 next 指標指向新節點，

演算法實作如下所示：

    def insert(self, index, data):
        count = 0
        prev = self.head
        # 判斷插入位置的合法性
        if index > self.length or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            new_node = Node(data)
            while count < index:
                prev = prev.next
                count += 1
            new_node.previous = prev
            self.length += 1
            if prev.next:
                # 鏈表中間插入結點
                new_node.next = prev.next
                prev.next.previous = new_node
                prev.next = new_node
            else:
                # 鏈尾插入結點
                prev.next = new_node

2.6 洗掉指定位置元素

洗掉指定位置元素，只需要找到相應位置結點 current，修改指標后，洗掉結點即可，需要注意的是，除了需要將 current 的前驅結點的 next 指標指向 current 的后繼節點外，如果洗掉的并非鏈尾元素，還需要將 current 的后繼節點的 previous 指標指向 current 的前驅結點：

演算法實作如下所示：

    def get_node(self, index):
        """輔助函式，用于根據位置回傳結點"""
        if index > self.length - 1 or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        count = -1
        current = self.head
        while count < index:
            current = current.next
            count += 1
        return current
    def __delitem__(self, index):
        """洗掉指定位置元素"""
        if index > self.length - 1 or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        else:
            current = self.get_node(index)
            if current:
                current.previous.next = current.next
            # 如果洗掉的并非最后一個結點
            if current.next:
                current.next.previous = current.previous
            self.length -= 1
            del current

在插入和洗掉操作中，都是先確定操作位置，然后再進行插入和洗掉操作，所以其時間復雜度均為 O ( n ) O(n) O(n)，

2.7 其它一些有用的操作

2.7.1 鏈表元素輸出操作

將雙向鏈表轉換為字串以便進行列印，使用 str 函式呼叫物件上的 __str__ 方法可以創建適合列印的字串表示：

    def __str__(self):
        s = "["
        current = self.head.next
        count = 0
        while current != None:
            count += 1
            s += str(current)
            current = current.next
            if count < self.length:
                s += '<-->'
        s += "]"
        return s

2.7.2 洗掉指定元素

與洗掉指定位置元素略有不同，洗掉指定元素需要在鏈表中洗掉第一個具有與給定值相同資料元素的結點，但修改指標的操作是類似的，其時間復雜度同樣為 O ( n ) O(n) O(n)：

    def del_value(self, value):
        current = self.head
        while current:
            if current.data == value:
                current.previous.next = current.next
                if current.next:
                    current.next.previous = current.previous
                self.length -= 1 
                del current
                return
            else:
                current = current.next
        raise ValueError("The value provided is not present!")

2.7.3 在鏈表尾部追加新元素

為了方便的在鏈表尾部追加新元素，可以實作函式 append：

    def append(self, data):
        new_node = Node(data)
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.previous = current
        self.length += 1

此演算法的時間復雜度為 O ( n ) O(n) O(n)，如果需要經常在鏈表尾部追加新元素，可以使用增加尾指標 tail 用于追蹤鏈表的最后一個元素，利用尾指標在鏈表尾部追加新元素時間復雜度可以降至 O ( 1 ) O(1) O(1)，

3. 雙向鏈表應用

接下來，我們首先測驗上述實作的雙向鏈表，以驗證操作的有效性，然后利用實作的基本操作來實作更復雜的演算法，

3.1 雙向鏈表應用示例

首先初始化一個鏈表 dllist，并在其中追加若干元素：

dllist = DoublyLinkedList()
# 在鏈表末尾追加元素
dllist.append('apple')
dllist.append('banana')
dllist.append('orange')
# 在指定位置插入元素
dllist.insert(0, 'grape')
dllist.insert(4, 'lemon')

我們可以直接列印鏈表中的資料元素、鏈表長度等資訊：

print('雙向鏈表 sllist 為：', dllist)
print('雙向鏈表 sllist 長度為：', len(dllist))
print('雙向鏈表 sllist 第0個元素為：', dllist[0])
# 修改資料元素
dllist[0] = 'pear'
del(dllist[3])
print('雙向修改鏈表 sllist 資料后：', dllist)

以上代碼輸出如下：

雙向鏈表 dllist 為： [grape<-->apple<-->banana<-->orange<-->lemon]
雙向鏈表 dllist 長度為： 5
雙向鏈表 dllist 第0個元素為： grape
修改雙向鏈表 dllist 資料后： [pear<-->apple<-->banana<-->lemon]

接下來，我們將演示在指定位置添加/洗掉元素、以及如何查找指定元素等：

# 修改資料元素
dllist[0] = 'pear'
print('修改雙向鏈表 dllist 資料后：', dllist)
dllist.insert(0, 'watermelon')
print('在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 資料：', dllist)
del(dllist[3])
print('洗掉位置 3 處元素后雙向鏈表 ddlist 資料：', dllist)
dllist.append('lemon')
print('在尾部追加元素 lemon 后雙向鏈表 ddlist 資料：', dllist)
dllist.del_value('lemon')
print('洗掉 lemon 后雙向鏈表 dllist 資料：', dllist)
print('watermelon 在雙向鏈表 dllist 中的索引為：', dllist.locate('orange'))

以上代碼輸出如下：

修改雙向鏈表 dllist 資料后： [pear<-->apple<-->banana<-->orange<-->lemon]
在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 資料： [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon]
洗掉位置 3 后雙向鏈表 ddlist 資料： [watermelon<-->pear<-->apple<-->orange<-->lemon]
在尾部追加元素 lemon 后雙向鏈表 ddlist 資料： [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon]
洗掉 lemon 后雙向鏈表 dllist 資料： [watermelon<-->pear<-->apple<-->orange<-->lemon]
watermelon 在雙向鏈表 dllist 中的索引為： 3

3.2 利用雙向鏈表基本操作實作復雜操作

[1] 利用雙向鏈表的基本操作，合并兩個雙向鏈表：

def merge(dllist1, dllist2):
    current = dllist1.head
    while current.next:
        current = current.next
    if dllist2.head.next:
        tmp = dllist2.head.next
        current.next = tmp
        tmp.previous = current
    dllist1.length += len(dllist2)
    return dllist1
# 演算法測驗
dllist1 = DoublyLinkedList()
dllist2 = DoublyLinkedList()
for i in range(5):
    dllist1.append(i)
    dllist2.append((i+1)*5)
print('雙向鏈表 dllist1：', dllist1)
print('雙向鏈表 dllist2：', dllist2)
dllist = merge(dllist1, dllist2)
print('鏈表合并結果：', dllist)

程式輸出結果如下：

雙向鏈表 dllist1： [0<-->1<-->2<-->3<-->4]
雙向鏈表 dllist2： [5<-->10<-->15<-->20<-->25]
鏈表合并結果： [0<-->1<-->2<-->3<-->4<-->5<-->10<-->15<-->20<-->25]

相關鏈接

線性表基本概念
順序表及其操作實作
單鏈表及其操作實作
雙向鏈表及其操作實作