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

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

線性表的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)方法

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

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

1. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

但指針的這種靈活性是有代價(jià)的，即需要額外的空間來(lái)存儲(chǔ)地址。例如有一個(gè)整數(shù)線性表，我們?cè)诿總€(gè)結(jié)點(diǎn)中不僅需要存儲(chǔ)一個(gè)整數(shù)數(shù)據(jù)，同時(shí)還需要一個(gè)額外空間用于存儲(chǔ)指向下一個(gè)結(jié)點(diǎn)的指針。

1.3 結(jié)點(diǎn)

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

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

1.4 結(jié)點(diǎn)類

接下來(lái)，我們將實(shí)現(xiàn)上述結(jié)點(diǎn)結(jié)構(gòu)：

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

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

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

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

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

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

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

2.1 單鏈表的初始化

單鏈表表的初始化建立一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表，其表長(zhǎng) length 初始化為 0，此時(shí)鏈表中沒(méi)有元素結(jié)點(diǎn)，只有一個(gè)頭結(jié)點(diǎn)，其指針域?yàn)榭眨?/p>

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

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

2.2 獲取單鏈表長(zhǎng)度

由于我們?cè)阪湵碇惺褂?length 跟蹤鏈表中的項(xiàng)數(shù)，因此求取單鏈表長(zhǎng)度只需要重載 len 從對(duì)象返回 length 的值，因此時(shí)間復(fù)雜度為O(1)：

def __len__(self):
    return self.length

2.3 讀取指定位置元素

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

我們也可以實(shí)現(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 查找指定元素

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

使用 Python 實(shí)現(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é)點(diǎn)
        node.next = previous.next
        previous.next = node
        self.length += 1

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

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

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

使用 Python 實(shí)現(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

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

2.7 其它一些有用的操作

2.7.1 鏈表元素輸出操作

將單鏈表轉(zhuǎn)換為字符串以便進(jìn)行打印，使用 str 函數(shù)調(diào)用對(duì)象上的 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
    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 在鏈表尾部追加新元素

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

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

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

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

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

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

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

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

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

以上代碼輸出如下：

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

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

# 在指定位置添加/刪除結(jié)點(diǎn)
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 利用單鏈表基本操作實(shí)現(xiàn)復(fù)雜操作

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

為了保證算法的空間復(fù)雜度為O(1)，只能修改原結(jié)點(diǎn)的指針，設(shè)置指針 current， 令其指向 head->next，并令head.next=None，然后使用 current 指針依次遍歷每個(gè)結(jié)點(diǎn)并插入到 head 之后。該算法只需要對(duì)鏈表順序掃描一遍即可完成倒置，因此時(shí)間復(fù)雜度為O(n)，算法實(shí)現(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
# 算法測(cè)試
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é)點(diǎn)，如下圖操作所示，(a) 為刪除前的情況，(b) 為刪除后的狀態(tài)。

用指針 previous 指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，并使用另一個(gè)指針 curent 指向 previous 的直接后繼開(kāi)始遍歷整個(gè)鏈表，當(dāng)遇到具有相同的數(shù)據(jù)元素的結(jié)點(diǎn)時(shí)將其刪除；然后 previous 指向下一個(gè)結(jié)點(diǎn)，重復(fù)刪除過(guò)程；直到 previous 指向最后結(jié)點(diǎn)時(shí)算法結(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
# 算法測(cè)試
sllist = SinglyLinkedList()
print('刪除重復(fù)結(jié)點(diǎn)前：', sllist)
sllist.append(10)
sllist.append(11)
sllist.append(10)
sllist.append(10)
sllist.append(11)
print('刪除重復(fù)結(jié)點(diǎn)后', delete_same_node(sllist))

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

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

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