【久遠(yuǎn)講算法4】鏈表——實(shí)現(xiàn)無序列表

“閱讀本文大概需要6分鐘”

你好，我是久遠(yuǎn)，上周開始我們算是正式入門了數(shù)據(jù)結(jié)構(gòu)，進(jìn)行了數(shù)組的講解。

我們現(xiàn)在來總結(jié)回顧一下數(shù)組的知識。

1. 【久遠(yuǎn)講算法①】什么是時間復(fù)雜度

2. 【久遠(yuǎn)講算法】什么是空間復(fù)雜度？

3. 【久遠(yuǎn)講算法3】數(shù)組——最簡單的數(shù)據(jù)結(jié)構(gòu)

• 數(shù)組是什么？

是由相同類型的元素的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲。利用元素的索引（index）可以計算出該元素對應(yīng)的存儲地址。

• 數(shù)組的儲存類型

順序存儲：數(shù)組在內(nèi)存中的順序存儲，具體是什么樣子呢？

內(nèi)存是由一個個連續(xù)的內(nèi)存單元組成的，每一個內(nèi)存單元都有自己的地址。在這些內(nèi)存單元中，有些被他數(shù)據(jù)占用了，有些是空閑的。

數(shù)組中的每一個元素，都存儲在小小的內(nèi)存單元中，并且元素之間緊密排列，既不能打亂元素的存儲順序，也不能跳過某個存儲單元進(jìn)行存儲。

既然有順序存儲，那么一定就有無序存儲咯？我們今天要介紹的鏈表便是無序存儲的類型。

鏈表的使用

• 我們?yōu)槭裁匆獙W(xué)鏈表，它的存在又有什么作用呢？

上周我們講解到數(shù)組，數(shù)組的特點(diǎn)便是順序存儲，適用于查找和修改操作，如果要進(jìn)行刪除和插入元素的操作的時候，數(shù)組元素騰位置這件事就要花費(fèi)不少時間，因此遇到一些經(jīng)常要刪除數(shù)據(jù)，插入數(shù)據(jù)的事情的時候，我們盡量不優(yōu)先考慮用數(shù)組去解決這類問題，因?yàn)檫@樣反復(fù)的使用數(shù)組，只會增加我們代碼的運(yùn)行時間，對我們其實(shí)是沒什么好處的。

這種時候我們就可以使用鏈表了，鏈表主要是便于管理長度或數(shù)量不確定的數(shù)據(jù)，經(jīng)常插入或者刪除數(shù)據(jù)，鏈表輕而易舉就能做到這些，花費(fèi)的時間相對于數(shù)組少很多。

• 列表和鏈表名字很像，它們之間有什么關(guān)系么？

列表是我們接觸 python 以后，最經(jīng)常用到的數(shù)據(jù)類型，列表非常的強(qiáng)大，它為我們提供了很多操作。但是其實(shí)不是所有的編程語言都有列表的，而沒有列表的編程語言，就要通過別的方式去實(shí)現(xiàn)列表的功能。鏈表便可以幫助我們完成列表的實(shí)現(xiàn)。

而列表又分為有序列表和無序列表，我們平常是非常常見列表的，數(shù)組就可以用來實(shí)現(xiàn)有序列表，而鏈表則用來實(shí)現(xiàn)無序列表。

• 無序列表是什么？

先從列表的定義來分析，列表是元素的集合，其中每一個元素都有一個相對于其他元素的位置。更具體地說，這種列表稱為無序列表?？梢哉J(rèn)為列表有第一個元素、第二個元素、第三個元素，等等；也可以稱第一個元素為列表的起點(diǎn)，稱最后一個元素為列表的終點(diǎn)。為簡單起見，我們假設(shè)列表中沒有重復(fù)元素。

什么是鏈表

在計算機(jī)科學(xué)中，鏈表是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點(diǎn)里存到下一個節(jié)點(diǎn)的指針。效果如圖：

看似隨意的一組數(shù)字，通過指針可以將它們進(jìn)行連接。

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

使用鏈表實(shí)現(xiàn)無序列表

Node 類

上文我們提到了一個例子，一個鏈表如果存在，那么我們需要知道它第一個元素的位置，讓計算機(jī)清楚它應(yīng)該從哪里開始尋找元素，還要告訴最后一個元素它沒有下一個元素，讓計算機(jī)懂得停止尋找元素。因此在實(shí)現(xiàn)鏈表時，我們需要知道一個元素的位置，以及元素自身，以及這個元素指向的下一個元素是什么，只有這樣我們才能順藤摸瓜找到接下來的元素嘛，我們將這一系列所需的東西合在一起，稱作節(jié)點(diǎn)。

節(jié)點(diǎn)是構(gòu)建鏈表的基本數(shù)據(jù)結(jié)構(gòu)。每一個節(jié)點(diǎn)都必須包含有兩種內(nèi)容。首先，節(jié)點(diǎn)必須包含要生成的鏈表的元素，我們稱之為節(jié)點(diǎn)的數(shù)據(jù)變量。其次，節(jié)點(diǎn)必須保存指向下一個節(jié)點(diǎn)的引用。在構(gòu)建節(jié)點(diǎn)時，需要為其提供初始值。執(zhí)行下面的賦值語句會生成一個包含數(shù)據(jù)值20 的節(jié)點(diǎn)對象。

temp = Node(20) 
temp.getData()
#20

Node 類也包含訪問和修改數(shù)據(jù)的方法，以及指向下一個元素的引用。

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

對 python 代碼進(jìn)行分析：

我們定義一個 Node 類，那就需要有初始化方法__init__ ，其中定義了一個 data 元素，用來存放節(jié)點(diǎn)的數(shù)據(jù)，又定義了一個 next 元素，用來指向下一個節(jié)點(diǎn)。next 的值默認(rèn)初始化為 None ，指向 None 的引用代表著該元素后面沒有其他元素。

getData 方法主要是用于獲取當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)。

getNext 用于告訴使用者該鏈表當(dāng)前節(jié)點(diǎn)指向的下一節(jié)點(diǎn)是什么。

setData 方法主要用于修改當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，傳入一個新的數(shù)據(jù)（newdata），然后將其賦值給節(jié)點(diǎn)的原數(shù)據(jù)，這樣當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)內(nèi)容就修改成功啦。

setNext 方法主要用于插入新節(jié)點(diǎn)，當(dāng)我們在當(dāng)前節(jié)點(diǎn)的后面插入一個新的節(jié)點(diǎn)的時候，要告訴當(dāng)前節(jié)點(diǎn)它的后面有了新的節(jié)點(diǎn)，所以才有了 self.next = newnext。

無序列表類

由上文可知，節(jié)點(diǎn)是無序列表的構(gòu)成要素之一。每一個節(jié)點(diǎn)都通過顯式的引用指向下一個節(jié)點(diǎn)。只要知道第一個節(jié)點(diǎn)的位置，其后的每一個元素都能通過下一個引用找到。因此，無序列表類必須包含指向第一個節(jié)點(diǎn)的引用。

無序列表類的定義方法如下：

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

對 python 代碼進(jìn)行講解：

無序列表類的生成方法包括有一行代碼，self.head = None 即默認(rèn)該無序列表的頭節(jié)點(diǎn)為空，不指向任何元素。

因此我們可以加以思考，當(dāng)我們定義一個無序列表時，判斷一個無序列表是否為空，我們只需要知道它的頭節(jié)點(diǎn)是不是指向空就可以了。我們可以以此延伸出判斷無序列表是否為空的方法 isEmpty().

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

僅僅一行代碼，如果頭節(jié)點(diǎn)不為空，那則說明頭節(jié)點(diǎn)必定有指向別處的元素，如果頭節(jié)點(diǎn)為空那說明這個列表只有這么長。

現(xiàn)在我們已經(jīng)做好了十足的前期準(zhǔn)備了，即知道了無序列表是怎么定義的，也可以通過 isEmpty 方法來判斷它其中是否有元素了。現(xiàn)在要做的便是對我們新建的無序列表進(jìn)行增刪改查操作了。

Add 方法

想生成一個無序列表，我們首先要向其中添加元素，那么我們就需要實(shí)現(xiàn) add 方法。

但在實(shí)現(xiàn)之前，需要考慮一個問題：新元素要被放在哪個位置？

這個問題是否似曾相識？在數(shù)組章節(jié)中，我們考慮了很多情況，在末尾，在開頭，在中間加入新的元素，尤其是將元素插入到數(shù)組中間，處理起來非常的費(fèi)勁，插入一個元素，剩下的不少元素都要為它騰出位置。但是現(xiàn)在我們要實(shí)現(xiàn)的列表是無序的，因此新元素相對于已有元素的位置并不重要。新的元素可以在任意位置。因此，將新元素放在最簡便的位置是最合理的選擇。這里我們首先考慮元素在列表頭部插入。

def add(self):
        temp = Node(data)
        temp.getNext(self.head)
        self.head = temp

代碼講解：

要向列表中加入新的元素，我們首先要記起，列表的組成單位為節(jié)點(diǎn)，想要成功插入一個元素，首先我們要生成一個包含有此元素的節(jié)點(diǎn)，因此我們使用了Node(data)，生成了一個包含有要插入的元素 data 的節(jié)點(diǎn)，并將其賦值給temp，以此這個節(jié)點(diǎn)的新名字就叫 temp 了，temp 節(jié)點(diǎn)想要加入到列表的首部，首先我們要讓 temp 節(jié)點(diǎn)找到頭節(jié)點(diǎn)，這樣子才有說服力，如果連自己想要加入的列表隊伍的首部都不認(rèn)識，就算你說你是頭節(jié)點(diǎn)了，你的后邊沒有隊伍，也不算是加入到列表隊伍中啊，因此才有了 temp.getNext(self.head) ,你找到了你要加入的列表的首部以后，你就可以名正言順的成為第一名了，因此通過 self.head = temp 這行代碼，你被冠名了列表首部這個名字。

length 方法

我們向列表中添加多個節(jié)點(diǎn)之后，想要計算當(dāng)前列表的長度，我們引入 length 方法進(jìn)行處理。

我們的具體做法是用一個外部引用從列表的頭節(jié)點(diǎn)開始訪問。隨著訪問每一個節(jié)點(diǎn)，然后根據(jù)每個節(jié)點(diǎn)的指針指向去尋找下一個節(jié)點(diǎn)，以此類推最后計算出列表的長度。

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

代碼講解：

我們使用了一個叫做 current 的外部引用，讓它從列表的頭部開始進(jìn)行訪問，然后又引入了一個計數(shù)器 cnt ，用來計算節(jié)點(diǎn)的個數(shù)，之后我們要做的便是，尋找 current 所指向的節(jié)點(diǎn)是否為空，如果指向的節(jié)點(diǎn)不為空，則說明該節(jié)點(diǎn)后面還有另外的節(jié)點(diǎn)存在，計數(shù)器加1，如此循環(huán)直到 current 指向的節(jié)點(diǎn)為空，這就在提醒我們，該節(jié)點(diǎn)后沒有別的節(jié)點(diǎn)了，已經(jīng)到了列表的尾部，因此我們將返回計數(shù)器的個數(shù)即可。

Search 方法

既然我們能對列表的長度進(jìn)行計算，那么我們能不能查找列表中的元素呢？當(dāng)然可以，實(shí)現(xiàn)的基本思路和 length 方法是非常相似的，我們只需要加入一個 boolean 類型的變量 found 來表示我們是否找到了我們要查找的那個元素即可。

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

與在 length 方法中相似，遍歷從列表的頭部開始。我們使用布爾型變量 found 來標(biāo)記是否找到所需的元素。默認(rèn)一開始我們沒有找到元素，found的值為 False ，當(dāng)我們對列表進(jìn)行遍歷時，我們使用 getData 方法來進(jìn)行判斷節(jié)點(diǎn)元素的獲取，如果獲取到的元素和我們要查找的元素 item 相同，我們就告訴 found ，我們找到了 item 這個元素，因此有 found = True，如果通過 getData 方法獲取到的元素與 item 不同，那么我們就繼續(xù)尋找下一個節(jié)點(diǎn)，直到節(jié)點(diǎn)的元素與 item 相同為止，如果我們找遍了整個列表都沒有找到 item 元素，那我們最終就要返回 found 的默認(rèn)值了，即為 False 。

remove 方法

我們通過 remove 方法來進(jìn)行列表元素的刪除。要刪除列表中的某個元素，我們是否要考慮先找到這個元素我們才能對其進(jìn)行刪除操作呢，因此其實(shí) remove 方法和 search 方法也是十分相像的，我們首先要使用 search 方法找到我們要刪除的元素，然后對其進(jìn)行刪除即可。但是刪除具體要怎么刪除呢？我們回到最初的那副圖片。假設(shè)我要刪除 21 這個節(jié)點(diǎn)，以我們正常的思維去想的話，直接去掉 21 不就好了么！但是這會出現(xiàn)一個問題，那便是，34 本身是指向 21 的，而 21 又指向了 56 ，唐突的把 21 刪掉的話，34又要指向哪里呢？56 也沒有被指向的對象了，整個列表就從 21 這里斷開了！我們不能因?yàn)橐粋€元素的刪除，就使得整個列表因此作廢，因此我們要考慮，如果刪除21的同時，又使得列表繼續(xù)存在。

這時，我們就可以考慮，如果我把 21 刪掉了的話，34 和 56 豈不是前后鄰居了？那這樣的話，我直接讓 34 無視 21 ，轉(zhuǎn)而指向 56 不就可以了，又因?yàn)榱斜淼拈L度是通過節(jié)點(diǎn)指向進(jìn)行計算的嘛，只要沒有節(jié)點(diǎn)指向 21 ，就相當(dāng)于 21 不存在于列表中，從而達(dá)到了 21 被刪除的效果。

利用代碼來實(shí)現(xiàn) remove 方法：

def remove(self,item):
        cur = self.head
        pre = None
        found = False
        while not found :
            if cur.getData() == item:
                found = True
            else:
                pre = cur
                cur = cur.getNext()
                
        if pre == None:
            self.head = current.getNext()
        else:
            pre.setNext(cur,getNext())

代碼講解：

先提出一個問題 ：為什么這段代碼里引入了 pre 變量，它有什么特殊的用法么？

當(dāng)我們使用循環(huán)進(jìn)行元素遍歷時，查找到要刪除的節(jié)點(diǎn)時，cur 已經(jīng)指向了要被刪除的節(jié)點(diǎn)，還記得我們剛剛說的么？要刪除這個節(jié)點(diǎn)，我們就要將這個節(jié)點(diǎn)前面的節(jié)點(diǎn)（它的前鄰居）指向它后面的節(jié)點(diǎn)（它的后鄰居），無視該節(jié)點(diǎn)，達(dá)到刪除該節(jié)點(diǎn)的效果，而我們定義的節(jié)點(diǎn)類里面之后 getNext() 方法，沒有任何關(guān)于查找前節(jié)點(diǎn)的方法，因此我們只通過 cur 這一個變量，是無法完成刪除操作的。為了解決這一問題，我們引入了一個新的變量 ?pre ，cur 與之前一樣，標(biāo)記在鏈表中的當(dāng)前位置。新的引用 pre 總是指向 cur上一次訪問的節(jié)點(diǎn)。這樣一來，當(dāng) cur指向需要被移除的節(jié)點(diǎn)時，pre 正好指向要刪除節(jié)點(diǎn)的“前鄰居”，可以起到修改前節(jié)點(diǎn)指向的作用。

一旦搜索過程結(jié)束，就需要執(zhí)行刪除操作。而刪除操作又包括有以下兩種情況：刪除頭節(jié)點(diǎn)，刪除其他節(jié)點(diǎn)。

如果被刪除的元素正好是鏈表的頭節(jié)點(diǎn)所包含的元素的話，那么 cur會指向頭節(jié)點(diǎn)，而 pre 則依舊為它的默認(rèn)值 None，在這種情況下，我們只需要修改 cur 即可，告訴它頭節(jié)點(diǎn)變成了它后面那個節(jié)點(diǎn)，而不再是它本身就可以了，無需修改 pre 的值。

如果 pre 的值不是 None，則說明需要移除的節(jié)點(diǎn)在鏈表結(jié)構(gòu)中的某個位置。在這種情況下，pre 指向了 next 引用需要被修改的節(jié)點(diǎn)。我們對 pre 進(jìn)行 setNext() 方法來進(jìn)行節(jié)點(diǎn)的指向修改操作，這將意味著，pre 的下一個節(jié)點(diǎn)將指向 cur的下一個節(jié)點(diǎn)，而不再是指向 cur 本身了，修了指向，從而起到了刪除 cur 的效果。

如果是刪除最后的節(jié)點(diǎn)，我們應(yīng)該告訴倒數(shù)第二個節(jié)點(diǎn)，它的下一個節(jié)點(diǎn)為空，即倒數(shù)第二個節(jié)點(diǎn)的指向?yàn)镹one。

總結(jié)

恭喜你，又完成了一個數(shù)據(jù)結(jié)構(gòu)類型的學(xué)習(xí)，在本次的文章中，我主要通過實(shí)現(xiàn)無序列表的方式來對鏈表的操作進(jìn)行了詳細(xì)的講解，至于為什么不單獨(dú)進(jìn)行鏈表的講解，最主要還是因?yàn)?python 底層的代碼寫的非常的強(qiáng)大，它將數(shù)組和鏈表結(jié)合在一起進(jìn)而實(shí)現(xiàn)了列表，數(shù)組和鏈表其實(shí)就是列表實(shí)現(xiàn)的本質(zhì)，沒有這兩個數(shù)據(jù)結(jié)構(gòu)類型，列表便不會存在。我們平常的 python 使用中，一般都更常用列表，因此我們以列表為由，引出了它的本質(zhì)之一，鏈表。

流沙團(tuán)隊聯(lián)合AI悅創(chuàng)|久遠(yuǎn)·推出輔導(dǎo)班啦，包括「Python 語言輔導(dǎo)班、C++ 輔導(dǎo)班、java 輔導(dǎo)班、算法/數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)班、少兒編程、pygame 游戲開發(fā)」，全部都是一對一教學(xué)：一對一輔導(dǎo) + 一對一答疑 + 布置作業(yè) + 項目實(shí)踐等。QQ、微信在線，隨時響應(yīng)！