鏈表是一系列元素的集合，這些元素的內(nèi)存是散亂的。

無(wú)序鏈表則是一系列邏輯無(wú)序元素的集合，只是通過(guò)鏈表數(shù)據(jù)結(jié)構(gòu)連接起來(lái)。雖然這些元素整體來(lái)看是散亂的，但其中每一個(gè)元素都有一個(gè)相對(duì)于其他元素的位置信息。所以鏈表需要維持元素之間的相對(duì)位置，但是也不需要特意在一段內(nèi)存空間中存儲(chǔ)這些位置信息。

以下圖中的元素集合為例，這些元素的位置看上去都是隨機(jī)的。如果可以為每一個(gè)元素附加一份信息，即下一個(gè)元素的位置，那么這些元素的相對(duì)位置就能通過(guò)自身指向下一個(gè)元素的鏈接來(lái)表示。

附加信息后則可表示為：

需要注意的是，使用鏈表時(shí)我們必須指明鏈表中第一個(gè)元素的位置。一旦知道第一個(gè)元素的位置，就能根據(jù)其中的鏈接信息訪問(wèn)第二個(gè)元素，接著訪問(wèn)第三個(gè)元素，依此類推。指向鏈表第一個(gè)元素的引用被稱作頭 。最后一個(gè)元素需要知道自己沒(méi)有下一個(gè)元素。

認(rèn)真觀察鏈表，我們將每一個(gè)元素視為一個(gè)節(jié)點(diǎn)，鏈表則是通過(guò)他們之間的相對(duì)位置關(guān)系把這些節(jié)點(diǎn)串起來(lái)的。每一個(gè)節(jié)點(diǎn)至少包含了兩個(gè)基本屬性，首先就是節(jié)點(diǎn)的數(shù)據(jù)變量，其次就是節(jié)點(diǎn)對(duì)下一個(gè)節(jié)點(diǎn)位置的指向關(guān)系。

我們首先來(lái)構(gòu)造節(jié)點(diǎn)。

節(jié)點(diǎn)（Node）是構(gòu)建鏈表的基本數(shù)據(jù)結(jié)構(gòu)。每一個(gè)節(jié)點(diǎn)對(duì)象都必須持有至少兩份信息。首先，節(jié)點(diǎn)必須包含一個(gè)數(shù)據(jù)元素，我們稱之為節(jié)點(diǎn)的數(shù)據(jù)變量 。其次，節(jié)點(diǎn)必須保存指向下一個(gè)節(jié)點(diǎn)的引用。下面的代碼展示了 Node 類的Python實(shí)現(xiàn)。在構(gòu)建節(jié)點(diǎn)時(shí)，需要為其提供初始值。Node 類也需要包含訪問(wèn)和修改數(shù)據(jù)的方法，以及指向下一 個(gè)元素的引用。

class Node:
    def __init__(self, initdata):
        self.data = initdata  # 數(shù)據(jù)元素
        self.next = None      # 指向下一節(jié)點(diǎn)的引用
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self, newdata):
        self.data = newdata
    def setNext(self, newnext):
        self.next = newnext

需要注意的是，None 在 Node 類以及之后的鏈表中起到了重要的作用。節(jié)點(diǎn)指向 None 的引用代表著后面沒(méi)有新節(jié)點(diǎn)。所以，在 Node 的構(gòu)造方法中我們將 next 的初始值設(shè)為 None 。

節(jié)點(diǎn)（Node）的類構(gòu)建完畢后，接下來(lái)我們開(kāi)始構(gòu)建整個(gè)鏈表（LinkList）的類。

如前所述，鏈表是基于節(jié)點(diǎn)集合來(lái)構(gòu)建的，每一個(gè)節(jié)點(diǎn)都通過(guò)顯式的引用指向下一個(gè)節(jié)點(diǎn)。只要知道第一個(gè)節(jié)點(diǎn)的位置（第一個(gè)節(jié)點(diǎn)包含第一個(gè)元素），其后的每一個(gè)元素都能通過(guò)對(duì)下一個(gè)節(jié)點(diǎn)的引用找到。因此，LinkList 類必須包含指向第一個(gè)節(jié)點(diǎn)的引用。下列代碼展示了 LinkList 類的構(gòu)造方法。

class LinkList:
    def __init__(self):
        self.head = None

下圖展示了鏈表無(wú)節(jié)點(diǎn)和有節(jié)點(diǎn)的兩種情況：

我們已經(jīng)有了鏈表頭的創(chuàng)建方法，我們規(guī)定鏈表頭的初始指向?yàn)镹one，當(dāng)鏈表中有內(nèi)容（節(jié)點(diǎn)）時(shí)，鏈表頭則指向節(jié)點(diǎn)。

那么我們還需要一個(gè)方法來(lái)判斷鏈表頭的指向。

我們使用 isEmpty 方法檢查鏈表的頭部是否為指向None的引用。布爾表達(dá)式 self.head == None 當(dāng)且僅當(dāng)鏈表中沒(méi)有節(jié)點(diǎn)時(shí)才為真。由于新的鏈表是空的，因此構(gòu)造方法必須和檢查是否為空的方法保持一致。這體現(xiàn)了使用 None 表示鏈表末尾的好處。

class LinkList:
    def isEmpty(self):
        return self.head == None

接下來(lái)我們構(gòu)建鏈表節(jié)點(diǎn)的添加方法。

為了將節(jié)點(diǎn)添加到鏈表中，我們需要實(shí)現(xiàn) add 方法。但在實(shí)現(xiàn)之前，需要解決一個(gè)重要問(wèn)題：新節(jié)點(diǎn)要被放在鏈表的哪個(gè)位置？由于鏈表是無(wú)序元素的集合，因此新元素相對(duì)于已有元素的位置并不重要。新的元素可以在任意位置。因此，將新元素放在最簡(jiǎn)便的位置是最合理的選擇。 由于鏈表只提供一個(gè)入口（頭部），因此其他所有節(jié)點(diǎn)都只能通過(guò)第一個(gè)節(jié)點(diǎn)以及 next 鏈接來(lái)訪問(wèn)。這意味著添加新節(jié)點(diǎn)最簡(jiǎn)便的位置就是頭部，或者說(shuō)是鏈表的起點(diǎn)位置。我們把新節(jié)點(diǎn)作為鏈表的第一個(gè)節(jié)點(diǎn)，并且把已有的節(jié)點(diǎn)鏈接到該元素的后面。

下列代碼展示了 add 方法的實(shí)現(xiàn)：

class LinkList:
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

代碼第 3 行創(chuàng)建一個(gè)新節(jié)點(diǎn)，并且將 item 作為其數(shù)據(jù)。現(xiàn)在需要將新節(jié)點(diǎn)與已有的鏈表結(jié)構(gòu)鏈接起來(lái)。這一過(guò)程需要兩步，如下圖所示。圖中第 1 步（代碼第 4 行），將新節(jié)點(diǎn)的 next 引用指向當(dāng)前鏈表中的第一個(gè)節(jié)點(diǎn)。 這樣一來(lái)，原來(lái)的鏈表就和新節(jié)點(diǎn)正確地鏈接在了一起。圖中第 2 步，修改鏈表頭的指向， 使其指向新創(chuàng)建的節(jié)點(diǎn)。代碼第 5 行的賦值語(yǔ)句，完成了這一操作。

上述兩步的順序非常重要。如果顛倒代碼第 4 行和第 5 行的順序，會(huì)發(fā)生什么呢？如果先修改鏈表頭的指向，由于頭節(jié)點(diǎn)是唯一指向鏈表節(jié)點(diǎn)的外部引用，因此所有的已有節(jié)點(diǎn)都將丟失并且無(wú)法訪問(wèn)。

接下來(lái)我們要實(shí)現(xiàn)的方法還有 length 、search 以及 remove ，這些方法都基于遍歷鏈表。遍歷是指系統(tǒng)地訪問(wèn)每一個(gè)節(jié)點(diǎn)，具體做法是額外用一個(gè)外部引用從鏈表的頭節(jié)點(diǎn)開(kāi)始訪問(wèn)。隨著訪問(wèn)每一個(gè)節(jié)點(diǎn)，我們將這個(gè)外部引用通過(guò)“遍歷”下一個(gè)引用來(lái)指向下一個(gè)節(jié)點(diǎn)。

實(shí)現(xiàn)length方法（計(jì)算鏈表中節(jié)點(diǎn)的個(gè)數(shù)/鏈表長(zhǎng)度）

class LinkList:
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

為了實(shí)現(xiàn) length 方法，需要遍歷鏈表并且記錄訪問(wèn)過(guò)多少個(gè)節(jié)點(diǎn)。上述代碼展示了計(jì)算鏈表中節(jié)點(diǎn)個(gè)數(shù)的Python代碼。current 就是外部引用，它在第 3 行中被初始化為鏈表頭的引用。此時(shí)如果鏈表中沒(méi)有節(jié)點(diǎn)，current 將指向 None，如果鏈表中有節(jié)點(diǎn)，current 此時(shí)就是指向鏈表中的第一個(gè)結(jié)點(diǎn)。

在計(jì)算開(kāi)始時(shí)，由于沒(méi)有訪問(wèn)到任何節(jié)點(diǎn)，因此 count 被初始化為 0 。第 5~7 行實(shí)現(xiàn)遍歷過(guò)程。只要 current 指向的不是鏈表的結(jié)尾（None），就將它指向下一個(gè)節(jié)點(diǎn)（第 7 行）。每當(dāng)current 指向一個(gè)新節(jié)點(diǎn)時(shí)，將count加 1。最終，循環(huán)完成后返回 count 。

實(shí)現(xiàn)search方法（搜索鏈表中的某個(gè)節(jié)點(diǎn)）

在鏈表中搜索一個(gè)值同樣也會(huì)用到遍歷。每當(dāng)訪問(wèn)一個(gè)節(jié)點(diǎn)時(shí)，檢查該節(jié)點(diǎn)中的元素是否與要搜索的元素相同。在搜索時(shí)，可能并不需要完整遍歷鏈表就能找到該元素。事實(shí)上，如果遍歷到鏈表的末尾，就意味著要找的元素不在鏈表中。如果在遍歷過(guò)程中找到所需的元素，就沒(méi)有必要繼續(xù)遍歷了。

class LinkList:
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

上述代碼展示了 search 方法的實(shí)現(xiàn)。與在 length 方法中相似，遍歷從列表的頭部開(kāi)始（第3行）。我們使用布爾型變量 found 來(lái)標(biāo)記是否找到所需的元素。由于一開(kāi)始時(shí)并未找到該元素，因此第 4 行將 found 初始化為False 。

第 5 行的循環(huán)既考慮了是否到達(dá)鏈表末尾，也考慮了是否已經(jīng)找到目標(biāo)元素。只要還有未訪問(wèn)的節(jié)點(diǎn)并且還沒(méi)有找到目標(biāo)元素，就繼續(xù)檢查下一個(gè)節(jié)點(diǎn)。第 6 行檢查當(dāng)前節(jié)點(diǎn)中的元素是否為目標(biāo)元素。如果是，就將 found 設(shè)為True。

實(shí)現(xiàn)remove方法（移除鏈表中的某個(gè)節(jié)點(diǎn)）

remove 方法在邏輯上需要分兩步。

第 1 步，遍歷列表并查找要移除的元素(節(jié)點(diǎn))。一旦找到該元素（假設(shè)元素在鏈表中），就必須將其移除。第 1 步與 search 非常相似。從一個(gè)指向鏈表頭節(jié)點(diǎn)的外部引用開(kāi)始，遍歷整個(gè)鏈表，直到遇到需要移除的元素。假設(shè)目標(biāo)元素已經(jīng)在鏈表中，因此我們預(yù)測(cè)循環(huán)會(huì)在 current 抵達(dá) None 之前結(jié)束。這意味著可以在判斷條件中使用布爾型變量 found 。

第 2 步，移除元素(節(jié)點(diǎn))。當(dāng) found 被設(shè)為 True 時(shí)，current 將指向需要移除的節(jié)點(diǎn)。該如何移除它呢？一種做法是將節(jié)點(diǎn)包含的值替換成表示其已被移除的標(biāo)識(shí)值（比如 None 或者 Null，完全可以自定義）。這種做法的問(wèn)題是，節(jié)點(diǎn)的數(shù)量和元素的數(shù)量不再匹配。更好的做法是移除整個(gè)節(jié)點(diǎn)。

為了將包含元素的整個(gè)節(jié)點(diǎn)移除，需要將其前面的節(jié)點(diǎn)中的 next 引用指向 current 之后的節(jié)點(diǎn)。然而，并沒(méi)有反向遍歷鏈表的方法。由于current 已經(jīng)指向了需要修改的節(jié)點(diǎn)之后的節(jié)點(diǎn)，此時(shí)做修改為時(shí)已晚。

這一困境的解決方法就是在遍歷鏈表時(shí)使用兩個(gè)外部引用。current 與之前一樣，標(biāo)記在鏈表中的當(dāng)前位置。新的引用 previous 總是指向 current 上一次訪問(wèn)的節(jié)點(diǎn)。這樣一來(lái)，當(dāng)current 指向需要被移除的節(jié)點(diǎn)時(shí)，previous 就剛好指向真正需要修改的節(jié)點(diǎn)。

class LinkList:
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
                if current == None:
                	return found
        if previous == None:
            self.head = current.getnext()
        else:
            previous.setNext(current.getNext())

上面的代碼展示了完整的 remove 方法。第 3~4 行對(duì)兩個(gè)引用進(jìn)行初始賦值。注意，current 與其他遍歷例子一樣，從鏈表的頭節(jié)點(diǎn)開(kāi)始。由于頭節(jié)點(diǎn)之前沒(méi)有別的節(jié)點(diǎn)，因此 previous 的初始值是None。

第 7~8 行檢查當(dāng)前節(jié)點(diǎn)中的元素是否為要移除的元素。如果是，就設(shè) found 為 True 。 如果不是，則將 previous 和 current 往下一個(gè)節(jié)點(diǎn)的方向各移動(dòng)一次。這兩條語(yǔ)句的順序十分重要。必須先將 previous 移動(dòng)到current 的位置，然后再移動(dòng) current。這一過(guò)程經(jīng)常被稱 為“蠕動(dòng)”，因?yàn)?nbsp;previous 必須在 current 移動(dòng)之前指向其當(dāng)前位置。

下圖展示了這一過(guò)程：

一旦搜索過(guò)程結(jié)束，就需要執(zhí)行移除操作。如移除圖中數(shù)據(jù)值為 17 的節(jié)點(diǎn)，修改過(guò)程如下：

有一種特殊情況需要注意，如果被移除的節(jié)點(diǎn)正好是鏈表的第一個(gè)節(jié)點(diǎn)，那么 current 會(huì)指向鏈表中的第一個(gè)節(jié)點(diǎn)，previous 的值則是None 。在這種情況下，需要修改鏈表的頭節(jié)點(diǎn)，而不是 previous 指向的節(jié)點(diǎn)，如圖所示：

代碼第 13 行檢查是否遇到上述特殊情況。如果 previous 沒(méi)有移動(dòng)，當(dāng) found 被設(shè)為True 時(shí)，它的值仍然是None 。在這種情況下 （第13行），鏈表的頭節(jié)點(diǎn)指向被修改成指向當(dāng)前頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，從而達(dá)到移除頭節(jié)點(diǎn)的效果。但是，如果 previous 的值不是None ，則說(shuō)明需要移除的節(jié)點(diǎn)在鏈表結(jié)構(gòu)中的某個(gè)位置。在這種情況下，previous 指向了 next 引用需要被修改的節(jié)點(diǎn)。第 16 行使用 previous 的 setNext 方法來(lái)完成移除操作。注意，在兩種情況中，修改后的引用都指向current.getNext() 。

代碼匯總

# 構(gòu)造節(jié)點(diǎn)
class Node:
    def __init__(self, initdata):
        self.data = initdata      # 數(shù)據(jù)元素
        self.next = None          # 指向下一節(jié)點(diǎn)的引用（python變量賦值的本質(zhì)是引用）
    def getData(self):            # 獲取節(jié)點(diǎn)的數(shù)據(jù)元素值
        return self.data
    def getNext(self):            # 獲取下一節(jié)點(diǎn)的引用 若有節(jié)點(diǎn)則直接視作為下一節(jié)點(diǎn)
        return self.next
    def setData(self, newdata):   # 給節(jié)點(diǎn)的數(shù)據(jù)元素設(shè)置值
        self.data = newdata
    def setNext(self, newnext):   # 給節(jié)點(diǎn)設(shè)置對(duì)下一節(jié)點(diǎn)的引用
        self.next = newnext

# 構(gòu)造鏈表
class LinkList:
    def __init__(self):            # 設(shè)置鏈表的頭部指向 無(wú)節(jié)點(diǎn)時(shí)為None 
        self.head = None
    def isEmpty(self):             # 判斷鏈表是否為空（是否有節(jié)點(diǎn)）
        return self.head == None
    def add(self, item):           # 給鏈表增加新節(jié)點(diǎn)（從鏈表頭位置增加）
        temp = Node(item)            # 創(chuàng)建節(jié)點(diǎn)并對(duì)新節(jié)點(diǎn)數(shù)據(jù)元素賦值
        temp.setNext(self.head)      # 新節(jié)點(diǎn)指向當(dāng)前鏈表中的第一個(gè)節(jié)點(diǎn)
        self.head = temp             # 鏈表頭指向新節(jié)點(diǎn)
    def length(self):               # 計(jì)算鏈表長(zhǎng)度（節(jié)點(diǎn)個(gè)數(shù)）
        current = self.head           # 引入current作為指向標(biāo)識(shí) 指向第一個(gè)節(jié)點(diǎn) 或者None
        count = 0                     # 引入count作為計(jì)數(shù)變量
        while current != None:        # 當(dāng)指向標(biāo)識(shí)指向的不是鏈表末尾的None時(shí)
            count = count + 1           # 節(jié)點(diǎn)計(jì)數(shù)加一
            current = current.getNext() # 指向標(biāo)識(shí)向后移動(dòng)
        return count
    def search(self, item):                   # 搜索鏈表中節(jié)點(diǎn)
        current = self.head                     # 引入current作為指向標(biāo)識(shí) 指向第一個(gè)節(jié)點(diǎn)
        found = False                           # 引入found作為尋找狀態(tài)標(biāo)識(shí)
        while current != None and not found:    # 當(dāng)current沒(méi)有指向None 并且 未找到節(jié)點(diǎn)
            if current.getData() == item:         # 如果current當(dāng)前指向的節(jié)點(diǎn)是尋找的節(jié)點(diǎn)
                found = True                        # 找到
            else:                                 # 否則
                current = current.getNext()         # 指向標(biāo)識(shí)向后移動(dòng) 
        return found
    def remove(self, item):                 # 從鏈表中移除節(jié)點(diǎn)
        current = self.head                   # 引入current指向標(biāo)識(shí)指向第一個(gè)節(jié)點(diǎn)
        previous = None                       # 引入previous指向標(biāo)識(shí)指向current的上一個(gè)節(jié)點(diǎn) 所以當(dāng)current指向第一個(gè)節(jié)點(diǎn)時(shí) previous初始化指向的是None
        found = False                         # 引入尋找狀態(tài)標(biāo)識(shí) 尋找需要移除的節(jié)點(diǎn)
        while not found:                      # 遍歷節(jié)點(diǎn) 以找到為循環(huán)結(jié)束條件
            if current.getData() == item:       # 如果當(dāng)前節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)
                found = True                      # 找到
            else:                               # 當(dāng)前節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)
                previous = current                # previous指向當(dāng)前節(jié)點(diǎn)
                current = current.getNext()       # current指向移動(dòng)到下一個(gè)節(jié)點(diǎn)
                if current == None:               # 如果到最后都沒(méi)找到目標(biāo)節(jié)點(diǎn)
                    return found	 
                                              # 搜索過(guò)程結(jié)束
        if previous == None:                  # 如果previous目前指向的是None 代表current指向的是鏈表的第一個(gè)節(jié)點(diǎn) 也就是說(shuō)刪除的目標(biāo)節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn)
            self.head = current.getnext()        # 鏈表頭直接指向None表示刪除第一個(gè)節(jié)點(diǎn)
        else:                                 # 其他情況下
            previous.setNext(current.getNext())  #  當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

無(wú)注釋版：

class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self, newdata):
        self.data = newdata
    def setNext(self, newnext):
        self.next = newnext

class LinkList:
    def __init__(self):
        self.head = None
    def isEmpty(self):
        return self.head == None
    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
				if current == None:
					return found
        if previous == None:
            self.head = current.getnext()
        else:
            previous.setNext(current.getNext())

代碼運(yùn)行結(jié)果如下圖：

總結(jié)

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!