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

在順序存儲方式中，根據(jù)數(shù)據(jù)元素的序號就可隨機存取表中任何一個元素，但同時在插入和刪除運算需要移動大量的元素，造成算法效率較低。解決此缺陷的一個辦法是：對線性表采用鏈式存儲方式。在鏈表存儲方式中，在邏輯上相鄰的數(shù)據(jù)元素在存儲空間中不一定相鄰，數(shù)據(jù)元素的邏輯次序是通過鏈表中指針鏈接實現(xiàn)的。本節(jié)將介紹鏈式存儲結(jié)構(gòu)的特點以及各種基本操作的實現(xiàn)。
通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

線性表的鏈式存儲及實現(xiàn)方法

鏈表基本操作的實現(xiàn)

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

1. 線性表的鏈式存儲結(jié)構(gòu)

鏈式存儲結(jié)構(gòu)用于存放線性表中的元素的存儲單元在內(nèi)存中可以是連續(xù)的，也可以是零散分布的。由于線性表中各元素間存在著線性關(guān)系，為了表示元素間的這種線性關(guān)系，鏈式存儲結(jié)構(gòu)中不僅要存儲線性表中的元素，還要存儲表示元素之間邏輯關(guān)系的信息。所以用鏈式存儲結(jié)構(gòu)表示線性表中的一個元素時至少需要兩部分信息，除了存儲每一個數(shù)據(jù)元素值以外，還需存儲其后繼或前驅(qū)元素所在內(nèi)存的地址。采用鏈式存儲結(jié)構(gòu)表示的線性表簡稱鏈表 (Linked List)。

1.1 指針相關(guān)概念

在繼續(xù)進行講解前，我們首先來了解指針的相關(guān)概念，以便更好的理解鏈表。假設(shè)我們需要處理一個大型數(shù)據(jù)文件，這一文件已經(jīng)被讀取保持在內(nèi)存中，當我們在函數(shù)間傳遞文件時，并不會直接傳遞整個文件，我們需要創(chuàng)建變量來保存文件在內(nèi)存中的位置，這些變量很小，很容易在不同的函數(shù)之間傳遞。

使用指針的好處之一就是可以用一個簡單的內(nèi)存地址就可以指向一個更大的內(nèi)存地址段。計算機硬件中存在對指針的支持，稱為間接尋址。

與 C 語言等不同，在 Python 中，我們不需要直接操作指針，但這并不意味著 Python 中不使用指針。例如賦值語句 l = list([1, 2, 3])，我們通常會說 l 是列表類型的變量，或者直接說 l 是一個列表，但這并不準確，變量 l 是對列表的引用(指針)，list 構(gòu)造函數(shù)在內(nèi)存中的創(chuàng)建一個 list 并返回該 list 起始的內(nèi)存位置，這就是存儲在 l 中的內(nèi)容，Python 隱藏了這種復(fù)雜性。

1.2 指針結(jié)構(gòu)

每個指針結(jié)構(gòu)都包含一個或多個指向結(jié)構(gòu)中其他元素的鏈接，這些鏈接的類型取決于我們創(chuàng)建的數(shù)據(jù)類型，例如在鏈表中， 我們將鏈接到結(jié)構(gòu)中的下一個或上一個元素。

指針結(jié)構(gòu)具有如下優(yōu)點：

• 不需要連續(xù)的順序存儲空間
• 可以快速添加或刪除結(jié)點，在常數(shù)時間內(nèi)擴展結(jié)構(gòu)空間

但指針的這種靈活性是有代價的，即需要額外的空間來存儲地址。例如有一個整數(shù)線性表，我們在每個結(jié)點中不僅需要存儲一個整數(shù)數(shù)據(jù)，同時還需要一個額外空間用于存儲指向下一個結(jié)點的指針。

1.3 結(jié)點

一個結(jié)點是一個數(shù)據(jù)容器，以及一個或多個指向其它結(jié)點的鏈接，鏈接就是一個指針。一種簡單的結(jié)點只有到下一個結(jié)點的鏈接。假如我們有一個包含水果清單的鏈表，我們知道字符串實際上并不存儲在結(jié)點中，而是有一個指向?qū)嶋H字符串的指針，如下圖所示，其中包含兩個結(jié)點，第一個結(jié)點有一個指向存儲在內(nèi)存中的字符串 (apple) 的指針和一個存儲下一個結(jié)點地址的指針，因此，這個簡單結(jié)點的存儲要求是兩個內(nèi)存地址，包括數(shù)據(jù)域和指針域：

我們還需要考慮的一個問題是，最后一個結(jié)點的指針域，我們需要確保每個結(jié)點的指針域都指向一個明確的值。如果我們要明確讓最后一個結(jié)點的指針域不指向任何內(nèi)容，那么在 Python 中，我們需要使用特殊值 None 來表示什么都沒有。 如下圖所示，鏈表的最后一個結(jié)點的指針域指向 None：

1.4 結(jié)點類

接下來，我們將實現(xiàn)上述結(jié)點結(jié)構(gòu)：

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

Next 指針初始化為 None，這意味著默認結(jié)點為端點，除非更改 Next 的值，這樣可以確保正確終止鏈表。我們也可以根據(jù)需要向結(jié)點類添加其他內(nèi)容，例如我們可以創(chuàng)建一個 Fruit 類，用于存儲不同水果售價信息等數(shù)據(jù)，并使用數(shù)據(jù)域鏈接到 Fruit 類的實例。
為了能夠打印節(jié)點信息，我們需要重載 __str__ 方法：

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

2. 單鏈表的實現(xiàn)

通常，“鏈表”是指單鏈表，單鏈表由許多結(jié)點組成，其中每個結(jié)點都有只有一個指向直接后繼的 next 指針，鏈表中最后一個節(jié)點的鏈接為 None，表示鏈表結(jié)束。訪問數(shù)據(jù)元素只能由鏈表頭依次到鏈表尾，而不能做逆向訪問，這是一種最簡單的鏈表。而其它鏈表類型(包括雙向鏈表、循環(huán)鏈表等)將在之后小節(jié)中進行講解。

單鏈表分為帶頭結(jié)點和不帶頭結(jié)點兩種類型。因為鏈表中的第一個結(jié)點沒有直接前驅(qū)，它的地址需要放在鏈表的頭指針變量中；而其它結(jié)點的地址放入直接前驅(qū)結(jié)點的指針域中。在鏈表中插入和刪除結(jié)點時，對第一個結(jié)點和其它結(jié)點的處理是不同的。因此為了操作方便，就在鏈表的頭部加入一個“頭結(jié)點”，其指針域中存放第一個數(shù)據(jù)結(jié)點的地址，頭指針變量中存放頭結(jié)點的地址。下圖 (a) 中表示不帶頭結(jié)點的鏈表，其頭指針 linked_list 指向第一個數(shù)據(jù)結(jié)點，而圖 (b) 中表示不帶頭結(jié)點的鏈表頭指針 linked_list 指向頭結(jié)點，頭結(jié)點的指針域指向第一個數(shù)據(jù)結(jié)點：

Note：在接下來的實現(xiàn)的單鏈表基本操作中，若不特別說明，采用帶有頭結(jié)點的鏈表。

2.1 單鏈表的初始化

單鏈表表的初始化建立一個空的帶頭結(jié)點的單鏈表，其表長 length 初始化為 0，此時鏈表中沒有元素結(jié)點，只有一個頭結(jié)點，其指針域為空：

class SinglyLinkedList:
    def __init__(self):
        self.length = 0
        # 初始化頭結(jié)點
        head_node = Node()
        # 頭指針指向頭結(jié)點
        self.head = head_node

創(chuàng)建單鏈表 SinglyLinkedList 對象的時間復(fù)雜度為O(1)。

2.2 獲取單鏈表長度

由于我們在鏈表中使用 length 跟蹤鏈表中的項數(shù)，因此求取單鏈表長度只需要重載 __len__ 從對象返回 length 的值，因此時間復(fù)雜度為O(1)：

    def __len__(self):
        return self.length

2.3 讀取指定位置元素

為了實現(xiàn)讀取鏈表指定位置元素的操作，我們將重載 __getitem__ 操作。我們已經(jīng)知道單鏈表中的結(jié)點只能順序存取，即訪問前一個結(jié)點后才能接著訪問后一個結(jié)點。因此要訪問單鏈表中第i個元素值，必須從頭指針開始遍歷鏈表，依次訪問每個結(jié)點，直到訪問到第i個結(jié)點為止。因此操作的復(fù)雜度為O(n)。同時，我們希望確保索引在可接受的索引范圍內(nèi)，否則將引發(fā) IndexError 異常：

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

我們也可以實現(xiàn)修改指定位置元素的操作，只需要重載 __setitem__ 操作，其復(fù)雜度同樣為O(n)：

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

2.4 查找指定元素

當查找指定元素時，需要設(shè)置一個跟蹤鏈表結(jié)點的指針 current，初始時 current 指向鏈表中的第一個數(shù)據(jù)結(jié)點， 然后順著 next 域依次指向每個結(jié)點，每指向一個結(jié)點就判斷其值是否等于指定值 value，若是則返回該結(jié)點索引；否則繼續(xù)往后搜索，如果鏈表中無此元素，則引發(fā) ValueError 異常，其時間復(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é)點的插入只需要修改結(jié)點指針域的值，使其指向新的鏈接位置，而無需移動任何元素。 例如我們要在鏈表中索引為 i ii 處插入一個新結(jié)點，必須首先找到所插位置的前一個結(jié)點 i − 1 i-1i−1，再進行插入，設(shè)指針 previous 指向待插位置的前驅(qū)結(jié)點，指針 current 指向插入前鏈表中索引為 i ii 的結(jié)點，同時也是待插位置的后繼結(jié)點，指針 new_node 指向待插新結(jié)點，插入操作過程如下所示：

使用 Python 實現(xiàn)算法如下：

    def insert(self, index, data):
        count = -1
        current = self.head
        # 判斷插入位置的合法性
        if index > self.length or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        else:
            node = Node(data)
            while count < index:
                # 查找插入位置
                previous = current
                current = current.next
                count += 1
            # 插入新結(jié)點
            node.next = previous.next
            previous.next = node
            self.length += 1

也可以利用上述思想，直接在鏈表中插入結(jié)點：

    def insert_node(self, index, node):
        count = -1
        current = self.head
        if index > self.length or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        else:
            while count < index:
                previous = current
                current = current.next
                count += 1
                
                node.next = previous.next
? ? ? ? ? ?     previous.next = node
? ? ? ? ? ?     self.length += 1

2.6 刪除指定位置元素

要刪除鏈表中第 i ii 個結(jié)點，首先在單鏈表中找到刪除位置的前一個結(jié)點 previous，指針 current 指向要刪除的結(jié)點，將 previous 的指針域修改為待刪除結(jié)點 current 的后繼結(jié)點的地址，刪除后的結(jié)點需動態(tài)的釋放。下圖 (b) 中的粉色虛線表示刪除結(jié)點 current 后的指針指向：

使用 Python 實現(xiàn)算法如下：

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

在插入和刪除操作中，都是先確定操作位置，然后再進行插入和刪除操作，所以其時間復(fù)雜度均為O(n)。由于算法在進行插入和刪除操作時沒有移動元素的位置，只是修改了指針鏈接，所以采用鏈表存儲方式進行插入和刪除操作要比順序存儲方式的效率高。

2.7 其它一些有用的操作

2.7.1 鏈表元素輸出操作

將單鏈表轉(zhuǎ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 刪除指定元素

與刪除指定位置元素略有不同，刪除指定元素需要在鏈表中刪除第一個具有與給定值相同數(shù)據(jù)元素的結(jié)點，其時間復(fù)雜度同樣為O(n)：

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

2.7.3 在鏈表尾部追加新元素

為了方便的在鏈表尾部追加新元素，可以實現(xiàn)函數(shù) append：

    def append(self, value):
        node = Node(value)
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node
        self.length += 1

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

3. 單鏈表應(yīng)用

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

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

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

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

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

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

以上代碼輸出如下：

鏈表為： [banana-->apple-->orange-->lemon]
鏈表長度為： 4
鏈表第0個元素為： banana
修改鏈表數(shù)據(jù)后： [pear-->apple-->orange-->lemon]

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

# 在指定位置添加/刪除結(jié)點
sllist.insert(1, 'grape')
print('在位置1添加grape后鏈表數(shù)據(jù)：', sllist)
del(sllist[2])
print('修改鏈表數(shù)據(jù)后：', sllist)
# 刪除指定元素
sllist.del_value('pear')
print('刪除pear后鏈表數(shù)據(jù)：', sllist)
sllist.append('watermelon')
print('添加watermelon后鏈表數(shù)據(jù)：', sllist)

以上代碼輸出如下：

在位置1添加grape后鏈表數(shù)據(jù)： [pear-->grape-->apple-->orange-->lemon]
修改鏈表數(shù)據(jù)后： [pear-->grape-->orange-->lemon]
刪除pear后鏈表數(shù)據(jù)： [grape-->orange-->lemon]
添加watermelon后鏈表數(shù)據(jù)： [grape-->orange-->lemon-->watermelon]

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

[1] 利用基本運算函數(shù)，將一單鏈表逆置，如下圖 (a) 所示為逆置前鏈表，圖 (b) 為逆置后鏈表，并要求算法的空間復(fù)雜度為O(1)：

為了保證算法的空間復(fù)雜度為O(1)，只能修改原結(jié)點的指針，設(shè)置指針 current， 令其指向 head->next，并令head.next=None，然后使用 current 指針依次遍歷每個結(jié)點并插入到 head 之后。該算法只需要對鏈表順序掃描一遍即可完成倒置，因此時間復(fù)雜度為O(n)，算法實現(xiàn)如下：

def reverse_linked_list(sllist):
    head_node = sllist.head
    if head_node.next:
        current = head_node.next
        head_node.next = None
        sllist.length = 0
        while current:
            previous = current
            current = current.next
            sllist.insert_node(0, previous)
    return sllist
# 算法測試
sllist = SinglyLinkedList()
for i in range(5):
    sllist.append(i)
print('逆置前：', sllist)
print('逆置后：', reverse_linked_list(sllist))

算法輸出如下：

逆置前： [0-->1-->2-->3-->4]
逆置后： [4-->3-->2-->1-->0]

算法執(zhí)行流程如下所示：

[2] 刪除單鏈表中的重復(fù)結(jié)點，如下圖操作所示，(a) 為刪除前的情況，(b) 為刪除后的狀態(tài)。

用指針 previous 指向第一個數(shù)據(jù)結(jié)點，并使用另一個指針 curent 指向 previous 的直接后繼開始遍歷整個鏈表，當遇到具有相同的數(shù)據(jù)元素的結(jié)點時將其刪除；然后 previous 指向下一個結(jié)點，重復(fù)刪除過程；直到 previous 指向最后結(jié)點時算法結(jié)束：

def delete_same_node(sllist):
    previous = sllist.head.next
    if not previous:
        return
    while previous:
        current = previous
        while current.next:
            if current.next.data == previous.data:
                same = current.next
                current.next = current.next.next
                sllist.length -= 1
                del same
            else:
                current = current.next
        previous = previous.next
    return sllist
# 算法測試
sllist = SinglyLinkedList()
print('刪除重復(fù)結(jié)點前：', sllist)
sllist.append(10)
sllist.append(11)
sllist.append(10)
sllist.append(10)
sllist.append(11)
print('刪除重復(fù)結(jié)點后', delete_same_node(sllist))

該算法的時間復(fù)雜度為O(n²)，程序輸出如下：

刪除重復(fù)結(jié)點前： [10-->11-->10-->10-->11]
刪除重復(fù)結(jié)點后： [10-->11]

算法執(zhí)行流程如下所示：

以上就是Python數(shù)據(jù)結(jié)構(gòu)之鏈表詳解的詳細內(nèi)容，更多關(guān)于Python 鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！