0. 學習目標

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

線性表的鏈式存儲及實現方法

鏈表基本操作的實現

利用鏈表的基本操作實現復雜算法

1. 線性表的鏈式存儲結構

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

1.1 指針相關概念

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

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

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

1.2 指針結構

每個指針結構都包含一個或多個指向結構中其他元素的鏈接，這些鏈接的類型取決于我們創建的數據類型，例如在鏈表中， 我們將鏈接到結構中的下一個或上一個元素。

指針結構具有如下優點：

• 不需要連續的順序存儲空間
• 可以快速添加或刪除結點，在常數時間內擴展結構空間

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

1.3 結點

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

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

1.4 結點類

接下來，我們將實現上述結點結構：

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

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

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

2. 單鏈表的實現

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

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

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

2.1 單鏈表的初始化

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

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

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

2.2 獲取單鏈表長度

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

def __len__(self):
    return self.length

2.3 讀取指定位置元素

為了實現讀取鏈表指定位置元素的操作，我們將重載 getitem 操作。我們已經知道單鏈表中的結點只能順序存取，即訪問前一個結點后才能接著訪問后一個結點。因此要訪問單鏈表中第i個元素值，必須從頭指針開始遍歷鏈表，依次訪問每個結點，直到訪問到第i個結點為止。因此操作的復雜度為O(n)。同時，我們希望確保索引在可接受的索引范圍內，否則將引發 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

我們也可以實現修改指定位置元素的操作，只需要重載 setitem 操作，其復雜度同樣為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 查找指定元素

當查找指定元素時，需要設置一個跟蹤鏈表結點的指針 current，初始時 current 指向鏈表中的第一個數據結點， 然后順著 next 域依次指向每個結點，每指向一個結點就判斷其值是否等于指定值 value，若是則返回該結點索引；否則繼續往后搜索，如果鏈表中無此元素，則引發 ValueError 異常，其時間復雜度為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 在指定位置插入新元素

單鏈表結點的插入只需要修改結點指針域的值，使其指向新的鏈接位置，而無需移動任何元素。 例如我們要在鏈表中索引為 i ii 處插入一個新結點，必須首先找到所插位置的前一個結點 i − 1 i-1i−1，再進行插入，設指針 previous 指向待插位置的前驅結點，指針 current 指向插入前鏈表中索引為 i ii 的結點，同時也是待插位置的后繼結點，指針 new_node 指向待插新結點，插入操作過程如下所示：

使用 Python 實現算法如下：

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
        # 插入新結點
        node.next = previous.next
        previous.next = node
        self.length += 1

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

 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 個結點，首先在單鏈表中找到刪除位置的前一個結點 previous，指針 current 指向要刪除的結點，將 previous 的指針域修改為待刪除結點 current 的后繼結點的地址，刪除后的結點需動態的釋放。下圖 (b) 中的粉色虛線表示刪除結點 current 后的指針指向：

使用 Python 實現算法如下：

    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

在插入和刪除操作中，都是先確定操作位置，然后再進行插入和刪除操作，所以其時間復雜度均為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)：

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 在鏈表尾部追加新元素

為了方便的在鏈表尾部追加新元素，可以實現函數 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

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

3. 單鏈表應用

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

3.1 單鏈表應用示例

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

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

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

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

以上代碼輸出如下：

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

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

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

以上代碼輸出如下：

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

3.2 利用單鏈表基本操作實現復雜操作

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

為了保證算法的空間復雜度為O(1)，只能修改原結點的指針，設置指針 current， 令其指向 head->next，并令head.next=None，然后使用 current 指針依次遍歷每個結點并插入到 head 之后。該算法只需要對鏈表順序掃描一遍即可完成倒置，因此時間復雜度為O(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]

算法執行流程如下所示：

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

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

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('刪除重復結點前：', sllist)
sllist.append(10)
sllist.append(11)
sllist.append(10)
sllist.append(10)
sllist.append(11)
print('刪除重復結點后', delete_same_node(sllist))

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

刪除重復結點前： [10-->11-->10-->10-->11] 刪除重復結點后： [10-->11]

算法執行流程如下所示：