Python數(shù)據(jù)結(jié)構(gòu)之雙向鏈表詳解

更新時(shí)間：2022年01月20日 10:33:49 作者：盼小輝丶

單鏈表只有一個(gè)指向直接后繼的指針來表示結(jié)點(diǎn)間的邏輯關(guān)系，可以方便的從任一結(jié)點(diǎn)開始查找其后繼結(jié)點(diǎn)，但要找前驅(qū)結(jié)點(diǎn)則比較困難，雙向鏈表是為了解決這一問題，使用兩個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系。本文將重點(diǎn)為大家介紹雙向鏈表的相關(guān)操作，需要的可以參考一下

0. 學(xué)習(xí)目標(biāo)

單鏈表只有一個(gè)指向直接后繼的指針來表示結(jié)點(diǎn)間的邏輯關(guān)系，因此可以方便的從任一結(jié)點(diǎn)開始查找其后繼結(jié)點(diǎn)，但要找前驅(qū)結(jié)點(diǎn)則比較困難，雙向鏈表是為了解決這一問題，其使用兩個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系。在上一節(jié)中我們已經(jīng)討論了單鏈表及其相關(guān)操作的實(shí)現(xiàn)，本節(jié)中我們將重點(diǎn)討論雙向鏈表及其相關(guān)操作的實(shí)現(xiàn)。

通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

雙向鏈表的基本概念及其優(yōu)缺點(diǎn)

雙向鏈表基本操作的實(shí)現(xiàn)

利用雙向鏈表的基本操作實(shí)現(xiàn)復(fù)雜算法

1. 雙向鏈表簡介

1.1 雙向鏈表介紹

雙向鏈表 (doubly linked list) 與單鏈表相似，同樣使用結(jié)點(diǎn)和指針的相關(guān)概念，屬于順序表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，單鏈表和雙向鏈表的唯一區(qū)別在于雙向鏈表是用兩個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系，增加了一個(gè)指向其直接前驅(qū)的指針域，這樣形成的鏈表有兩條不同方向的鏈——前驅(qū)鏈和后繼鏈，因此稱為雙向鏈表，或稱為雙鏈表。

1.2 雙向鏈表結(jié)點(diǎn)類

在雙向鏈表中，根據(jù)已知結(jié)點(diǎn)查找其直接前驅(qū)結(jié)點(diǎn)可以與查找其直接后繼結(jié)點(diǎn)一樣方便。與單鏈表相同，雙向鏈表同樣可以分為帶有頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩類，本節(jié)僅討論帶頭結(jié)點(diǎn)的雙向鏈表。雙向鏈表的結(jié)點(diǎn)示意圖如下所示，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針——指向直接后繼的指針 next 和指向直接前驅(qū)的指針 previous：

用 Python 實(shí)現(xiàn)雙向鏈表結(jié)點(diǎn)類如下：

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

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

previous 變量指向直接前驅(qū)結(jié)點(diǎn)，而 next 變量保留對直接后繼結(jié)點(diǎn)的引用，而 data 變量用于存儲數(shù)據(jù)，重載 __str__ 方法用于便于打印結(jié)點(diǎn)對象。

1.3 雙向鏈表優(yōu)缺點(diǎn)

雙向鏈表的優(yōu)點(diǎn)在于給定雙向鏈表中的一個(gè)節(jié)點(diǎn)，我們可以雙向遍歷，直接訪問它的前驅(qū)結(jié)點(diǎn)，這樣在需要查找前驅(qū)的操作中，就不必再從頭開始遍歷整個(gè)鏈表，極大的方便了諸如刪除結(jié)點(diǎn)等操作。

而雙向鏈表的主要缺點(diǎn)如下：

每個(gè)結(jié)點(diǎn)需要一個(gè)額外的前驅(qū)指針，需要更多的空間；
結(jié)點(diǎn)的插入或刪除需要更多的指針修改操作。

2. 雙向鏈表實(shí)現(xiàn)

類似于單鏈表，接下來讓我們實(shí)現(xiàn)一個(gè)帶有頭結(jié)點(diǎn)的雙鏈表類，并用頭指針標(biāo)識鏈表的開頭，如果你還不了解單鏈表，可以參考《單鏈表及其操作實(shí)現(xiàn)》相關(guān)介紹。

2.1 雙向鏈表的初始化

雙向鏈表的初始化建立一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表，其表長 length 初始化為 0，此時(shí)鏈表中沒有元素結(jié)點(diǎn)，只有一個(gè)頭結(jié)點(diǎn)：

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

創(chuàng)建雙向鏈表 DoublyLinkedList 對象的時(shí)間復(fù)雜度為O(1)。

NOTE：如果你還記得繼承機(jī)制的話，我們也可以令 DoublyLinkedList 繼承自在《單鏈表及其操作實(shí)現(xiàn)》中實(shí)現(xiàn)的 SinglyLinkedList，可以極大的化簡雙向鏈表的實(shí)現(xiàn)。

2.2 獲取雙向鏈表長度

求取雙向鏈表長度只需要重載 __len__ 從對象返回 length 的值，因此時(shí)間復(fù)雜度為O(1)：

    def __len__(self):
        return self.length

2.3 讀取指定位置元素

雙向鏈表中讀取指定位置元素的算法與單鏈表完全相同，只需要使用后繼鏈訪問每一個(gè)結(jié)點(diǎn)即可，因此操作的復(fù)雜度同樣為O(n)，接下來我們將重載 __getitem__ 操作實(shí)現(xiàn)讀取鏈表指定位置元素的操作；同時(shí)，我們希望確保索引在可接受的索引范圍內(nèi)，否則將引發(fā) 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

類似的，我們也可以實(shí)現(xiàn)修改指定位置元素的操作，只需要重載 __setitem__ 操作，其復(fù)雜度同樣為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 查找指定元素

與單鏈表相同，當(dāng)查找指定元素時(shí)，需要設(shè)置一個(gè)跟蹤鏈表結(jié)點(diǎn)的指針 current，令其順著 next 域依次指向每個(gè)結(jié)點(diǎn)，每指向一個(gè)結(jié)點(diǎn)就判斷其值是否等于指定值 value，若是則返回該結(jié)點(diǎn)索引；否則繼續(xù)往后搜索，如果鏈表中無此元素，則引發(fā) ValueError 異常，其時(shí)間復(fù)雜度為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 在指定位置插入新元素

在指定位置插入新元素有兩種不同的方法，一種是找到待插入位置的結(jié)點(diǎn) current，然后將待插結(jié)點(diǎn)插入 current 之前；另一種方法是找到待插入位置結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) prev，然后待插結(jié)點(diǎn)插入 prev 之后，兩種方法的操作略有不同，這里以第二種方法的操作為例，第一種方法的具體操作留給大家進(jìn)行推導(dǎo)。

由于 prev 指向待插入位置的后繼結(jié)點(diǎn)，因此如果插入位置為列表末尾，由于 prev.next = None，無法使用 prev.next.previous，而在鏈表中間部位 prev.next.previous = prev，所以顯然插入鏈表中間位置和鏈表末尾的操作有所不同。

(1) 在雙向鏈表的末尾插入一個(gè)結(jié)點(diǎn)步驟如下：

遍歷列表直到最后一個(gè)結(jié)點(diǎn)，創(chuàng)建新結(jié)點(diǎn)；
將新節(jié)點(diǎn)的 previous 指針指向鏈表的最后一個(gè)結(jié)點(diǎn)；
更新原鏈表最后一個(gè)結(jié)點(diǎn)的 next 指針指向新結(jié)點(diǎn)。

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

首先遍歷鏈表到插入位置的前驅(qū)結(jié)點(diǎn) prev，創(chuàng)建新結(jié)點(diǎn)；
新結(jié)點(diǎn)的 next 指針指向要插入新結(jié)點(diǎn)位置的下一個(gè)節(jié)點(diǎn)，新結(jié)點(diǎn)的 previous 指針指向 prev；
插入位置后繼節(jié)點(diǎn)的 previous 指向新節(jié)點(diǎn)，prev 結(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn)。

算法實(shí)現(xiàn)如下所示：

    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:
                # 鏈表中間插入結(jié)點(diǎn)
                new_node.next = prev.next
                prev.next.previous = new_node
                prev.next = new_node
            else:
                # 鏈尾插入結(jié)點(diǎn)
                prev.next = new_node

2.6 刪除指定位置元素

刪除指定位置元素，只需要找到相應(yīng)位置結(jié)點(diǎn) current，修改指針后，刪除結(jié)點(diǎn)即可。需要注意的是，除了需要將 current 的前驅(qū)結(jié)點(diǎn)的 next 指針指向 current 的后繼節(jié)點(diǎn)外，如果刪除的并非鏈尾元素，還需要將 current 的后繼節(jié)點(diǎn)的 previous 指針指向 current 的前驅(qū)結(jié)點(diǎn)：

算法實(shí)現(xiàn)如下所示：

    def get_node(self, index):
        """輔助函數(shù)，用于根據(jù)位置返回結(jié)點(diǎn)"""
        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
            # 如果刪除的并非最后一個(gè)結(jié)點(diǎn)
            if current.next:
                current.next.previous = current.previous
            self.length -= 1
            del current

在插入和刪除操作中，都是先確定操作位置，然后再進(jìn)行插入和刪除操作，所以其時(shí)間復(fù)雜度均為O(n)。

2.7 其它一些有用的操作

2.7.1 鏈表元素輸出操作

將雙向鏈表轉(zhuǎn)換為字符串以便進(jìn)行打印，使用 str 函數(shù)調(diào)用對象上的 __str__ 方法可以創(chuàng)建適合打印的字符串表示：

    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 刪除指定元素

與刪除指定位置元素略有不同，刪除指定元素需要在鏈表中刪除第一個(gè)具有與給定值相同數(shù)據(jù)元素的結(jié)點(diǎn)，但修改指針的操作是類似的，其時(shí)間復(fù)雜度同樣為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 在鏈表尾部追加新元素

為了方便的在鏈表尾部追加新元素，可以實(shí)現(xiàn)函數(shù) 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

此算法的時(shí)間復(fù)雜度為O(n)，如果需要經(jīng)常在鏈表尾部追加新元素，可以使用增加尾指針 tail 用于追蹤鏈表的最后一個(gè)元素，利用尾指針在鏈表尾部追加新元素時(shí)間復(fù)雜度可以降至O(1)。

3. 雙向鏈表應(yīng)用

接下來，我們首先測試上述實(shí)現(xiàn)的雙向鏈表，以驗(yàn)證操作的有效性，然后利用實(shí)現(xiàn)的基本操作來實(shí)現(xiàn)更復(fù)雜的算法。

3.1 雙向鏈表應(yīng)用示例

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

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

我們可以直接打印鏈表中的數(shù)據(jù)元素、鏈表長度等信息：

print('雙向鏈表 sllist 為：', dllist)
print('雙向鏈表 sllist 長度為：', len(dllist))
print('雙向鏈表 sllist 第0個(gè)元素為：', dllist[0])
# 修改數(shù)據(jù)元素
dllist[0] = 'pear'
del(dllist[3])
print('雙向修改鏈表 sllist 數(shù)據(jù)后：', dllist)

以上代碼輸出如下：

雙向鏈表 dllist 為： [grape<-->apple<-->banana<-->orange<-->lemon]
雙向鏈表 dllist 長度為： 5
雙向鏈表 dllist 第0個(gè)元素為： grape
修改雙向鏈表 dllist 數(shù)據(jù)后： [pear<-->apple<-->banana<-->lemon]

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

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

以上代碼輸出如下：

修改雙向鏈表 dllist 數(shù)據(jù)后： [pear<-->apple<-->banana<-->orange<-->lemon]
在位置 0 添加 watermelon 后雙向鏈表鏈表 ddlist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon]
刪除位置 3 后雙向鏈表 ddlist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->orange<-->lemon]
在尾部追加元素 lemon 后雙向鏈表 ddlist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon]
刪除 lemon 后雙向鏈表 dllist 數(shù)據(jù)： [watermelon<-->pear<-->apple<-->orange<-->lemon]
watermelon 在雙向鏈表 dllist 中的索引為： 3

3.2 利用雙向鏈表基本操作實(shí)現(xiàn)復(fù)雜操作

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

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('鏈表合并結(jié)果：', dllist)

程序輸出結(jié)果如下：