【久遠講算法4】鏈表——實現(xiàn)無序列表
“閱讀本文大概需要6分鐘”
你好，我是久遠，上周開始我們算是正式入門了數(shù)據(jù)結(jié)構(gòu)，進行了數(shù)組的講解。
我們現(xiàn)在來總結(jié)回顧一下數(shù)組的知識。
數(shù)組是什么？
是由相同類型的元素的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲。利用元素的索引（index）可以計算出該元素對應的存儲地址。
數(shù)組的儲存類型
順序存儲：數(shù)組在內(nèi)存中的順序存儲，具體是什么樣子呢？
內(nèi)存是由一個個連續(xù)的內(nèi)存單元組成的，每一個內(nèi)存單元都有自己的地址。在這些內(nèi)存單元中，有些被他數(shù)據(jù)占用了，有些是空閑的。
數(shù)組中的每一個元素，都存儲在小小的內(nèi)存單元中，并且元素之間緊密排列，既不能打亂元素的存儲順序，也不能跳過某個存儲單元進行存儲。
既然有順序存儲，那么一定就有無序存儲咯？我們今天要介紹的鏈表便是無序存儲的類型。
鏈表的使用
我們?yōu)槭裁匆獙W鏈表，它的存在又有什么作用呢？
上周我們講解到數(shù)組，數(shù)組的特點便是順序存儲，適用于查找和修改操作，如果要進行刪除和插入元素的操作的時候，數(shù)組元素騰位置這件事就要花費不少時間，因此遇到一些經(jīng)常要刪除數(shù)據(jù)，插入數(shù)據(jù)的事情的時候，我們盡量不優(yōu)先考慮用數(shù)組去解決這類問題，因為這樣反復的使用數(shù)組，只會增加我們代碼的運行時間，對我們其實是沒什么好處的。
這種時候我們就可以使用鏈表了，鏈表主要是便于管理長度或數(shù)量不確定的數(shù)據(jù)，經(jīng)常插入或者刪除數(shù)據(jù)，鏈表輕而易舉就能做到這些，花費的時間相對于數(shù)組少很多。
列表和鏈表名字很像，它們之間有什么關系么？
列表是我們接觸 python 以后，最經(jīng)常用到的數(shù)據(jù)類型，列表非常的強大，它為我們提供了很多操作。但是其實不是所有的編程語言都有列表的，而沒有列表的編程語言，就要通過別的方式去實現(xiàn)列表的功能。鏈表便可以幫助我們完成列表的實現(xiàn)。
而列表又分為有序列表和無序列表，我們平常是非常常見列表的，數(shù)組就可以用來實現(xiàn)有序列表，而鏈表則用來實現(xiàn)無序列表。
無序列表是什么？
先從列表的定義來分析，列表是元素的集合，其中每一個元素都有一個相對于其他元素的位置。更具體地說，這種列表稱為無序列表?？梢哉J為列表有第一個元素、第二個元素、第三個元素，等等；也可以稱第一個元素為列表的起點，稱最后一個元素為列表的終點。為簡單起見，我們假設列表中沒有重復元素。
什么是鏈表
在計算機科學中，鏈表是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針。效果如圖：
看似隨意的一組數(shù)字，通過指針可以將它們進行連接。
需要注意的是，必須指明鏈表中第一個元素的位置。一旦知道第一個元素的位置，就能根據(jù) 其中的鏈接信息訪問第二個元素，接著訪問第三個元素，依此類推。指向鏈表第一個元素的引用被稱作頭。最后一個元素需要知道自己沒有下一個元素。
使用鏈表實現(xiàn)無序列表
Node 類
上文我們提到了一個例子，一個鏈表如果存在，那么我們需要知道它第一個元素的位置，讓計算機清楚它應該從哪里開始尋找元素，還要告訴最后一個元素它沒有下一個元素，讓計算機懂得停止尋找元素。因此在實現(xiàn)鏈表時，我們需要知道一個元素的位置，以及元素自身，以及這個元素指向的下一個元素是什么，只有這樣我們才能順藤摸瓜找到接下來的元素嘛，我們將這一系列所需的東西合在一起，稱作節(jié)點。
節(jié)點是構(gòu)建鏈表的基本數(shù)據(jù)結(jié)構(gòu)。每一個節(jié)點都必須包含有兩種內(nèi)容。首先，節(jié)點必須包含要生成的鏈表的元素，我們稱之為節(jié)點的數(shù)據(jù)變量。其次，節(jié)點必須保存指向下一個節(jié)點的引用。在構(gòu)建節(jié)點時，需要為其提供初始值。執(zhí)行下面的賦值語句會生成一個包含數(shù)據(jù)值20 的節(jié)點對象。
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 代碼進行分析：
我們定義一個 Node 類，那就需要有初始化方法__init__ ，其中定義了一個 data 元素，用來存放節(jié)點的數(shù)據(jù)，又定義了一個 next 元素，用來指向下一個節(jié)點。next 的值默認初始化為 None ，指向 None 的引用代表著該元素后面沒有其他元素。
getData 方法主要是用于獲取當前節(jié)點的數(shù)據(jù)。
getNext 用于告訴使用者該鏈表當前節(jié)點指向的下一節(jié)點是什么。
setData 方法主要用于修改當前節(jié)點的數(shù)據(jù)，傳入一個新的數(shù)據(jù)（newdata），然后將其賦值給節(jié)點的原數(shù)據(jù)，這樣當前節(jié)點的數(shù)據(jù)內(nèi)容就修改成功啦。
setNext 方法主要用于插入新節(jié)點，當我們在當前節(jié)點的后面插入一個新的節(jié)點的時候，要告訴當前節(jié)點它的后面有了新的節(jié)點，所以才有了 self.next = newnext。
無序列表類
由上文可知，節(jié)點是無序列表的構(gòu)成要素之一。每一個節(jié)點都通過顯式的引用指向下一個節(jié)點。只要知道第一個節(jié)點的位置，其后的每一個元素都能通過下一個引用找到。因此，無序列表類必須包含指向第一個節(jié)點的引用。
無序列表類的定義方法如下：
class UnorderedList:
def __init__(self):
self.head = None
對 python 代碼進行講解：
無序列表類的生成方法包括有一行代碼，self.head = None 即默認該無序列表的頭節(jié)點為空，不指向任何元素。
因此我們可以加以思考，當我們定義一個無序列表時，判斷一個無序列表是否為空，我們只需要知道它的頭節(jié)點是不是指向空就可以了。我們可以以此延伸出判斷無序列表是否為空的方法 isEmpty().
def isEmpty(self):
return self.head == None
僅僅一行代碼，如果頭節(jié)點不為空，那則說明頭節(jié)點必定有指向別處的元素，如果頭節(jié)點為空那說明這個列表只有這么長。
現(xiàn)在我們已經(jīng)做好了十足的前期準備了，即知道了無序列表是怎么定義的，也可以通過 isEmpty 方法來判斷它其中是否有元素了?，F(xiàn)在要做的便是對我們新建的無序列表進行增刪改查操作了。
Add 方法
想生成一個無序列表，我們首先要向其中添加元素，那么我們就需要實現(xiàn) add 方法。
但在實現(xiàn)之前，需要考慮一個問題：新元素要被放在哪個位置？
這個問題是否似曾相識？在數(shù)組章節(jié)中，我們考慮了很多情況，在末尾，在開頭，在中間加入新的元素，尤其是將元素插入到數(shù)組中間，處理起來非常的費勁，插入一個元素，剩下的不少元素都要為它騰出位置。但是現(xiàn)在我們要實現(xiàn)的列表是無序的，因此新元素相對于已有元素的位置并不重要。新的元素可以在任意位置。因此，將新元素放在最簡便的位置是最合理的選擇。這里我們首先考慮元素在列表頭部插入。
def add(self):
temp = Node(data)
temp.getNext(self.head)
self.head = temp
代碼講解：
要向列表中加入新的元素，我們首先要記起，列表的組成單位為節(jié)點，想要成功插入一個元素，首先我們要生成一個包含有此元素的節(jié)點，因此我們使用了Node(data)，生成了一個包含有要插入的元素 data 的節(jié)點，并將其賦值給temp，以此這個節(jié)點的新名字就叫 temp 了，temp 節(jié)點想要加入到列表的首部，首先我們要讓 temp 節(jié)點找到頭節(jié)點，這樣子才有說服力，如果連自己想要加入的列表隊伍的首部都不認識，就算你說你是頭節(jié)點了，你的后邊沒有隊伍，也不算是加入到列表隊伍中啊，因此才有了 temp.getNext(self.head) ,你找到了你要加入的列表的首部以后，你就可以名正言順的成為第一名了，因此通過 self.head = temp 這行代碼，你被冠名了列表首部這個名字。
length 方法
我們向列表中添加多個節(jié)點之后，想要計算當前列表的長度，我們引入 length 方法進行處理。
我們的具體做法是用一個外部引用從列表的頭節(jié)點開始訪問。隨著訪問每一個節(jié)點，然后根據(jù)每個節(jié)點的指針指向去尋找下一個節(jié)點，以此類推最后計算出列表的長度。
def length(self):
current = self.head
cnt = 0
while current != None:
cnt = cnt + 1
current = current.getNext()
return cnt
代碼講解：
我們使用了一個叫做 current 的外部引用，讓它從列表的頭部開始進行訪問，然后又引入了一個計數(shù)器 cnt ，用來計算節(jié)點的個數(shù)，之后我們要做的便是，尋找 current 所指向的節(jié)點是否為空，如果指向的節(jié)點不為空，則說明該節(jié)點后面還有另外的節(jié)點存在，計數(shù)器加1，如此循環(huán)直到 current 指向的節(jié)點為空，這就在提醒我們，該節(jié)點后沒有別的節(jié)點了，已經(jīng)到了列表的尾部，因此我們將返回計數(shù)器的個數(shù)即可。
Search 方法
既然我們能對列表的長度進行計算，那么我們能不能查找列表中的元素呢？當然可以，實現(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 來標記是否找到所需的元素。默認一開始我們沒有找到元素，found的值為 False ，當我們對列表進行遍歷時，我們使用 getData 方法來進行判斷節(jié)點元素的獲取，如果獲取到的元素和我們要查找的元素 item 相同，我們就告訴 found ，我們找到了 item 這個元素，因此有 found = True，如果通過 getData 方法獲取到的元素與 item 不同，那么我們就繼續(xù)尋找下一個節(jié)點，直到節(jié)點的元素與 item 相同為止，如果我們找遍了整個列表都沒有找到 item 元素，那我們最終就要返回 found 的默認值了，即為 False 。
remove 方法
我們通過 remove 方法來進行列表元素的刪除。要刪除列表中的某個元素，我們是否要考慮先找到這個元素我們才能對其進行刪除操作呢，因此其實 remove 方法和 search 方法也是十分相像的，我們首先要使用 search 方法找到我們要刪除的元素，然后對其進行刪除即可。但是刪除具體要怎么刪除呢？我們回到最初的那副圖片。假設我要刪除 21 這個節(jié)點，以我們正常的思維去想的話，直接去掉 21 不就好了么！但是這會出現(xiàn)一個問題，那便是，34 本身是指向 21 的，而 21 又指向了 56 ，唐突的把 21 刪掉的話，34又要指向哪里呢？56 也沒有被指向的對象了，整個列表就從 21 這里斷開了！我們不能因為一個元素的刪除，就使得整個列表因此作廢，因此我們要考慮，如果刪除21的同時，又使得列表繼續(xù)存在。
這時，我們就可以考慮，如果我把 21 刪掉了的話，34 和 56 豈不是前后鄰居了？那這樣的話，我直接讓 34 無視 21 ，轉(zhuǎn)而指向 56 不就可以了，又因為列表的長度是通過節(jié)點指向進行計算的嘛，只要沒有節(jié)點指向 21 ，就相當于 21 不存在于列表中，從而達到了 21 被刪除的效果。
利用代碼來實現(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 變量，它有什么特殊的用法么？
當我們使用循環(huán)進行元素遍歷時，查找到要刪除的節(jié)點時，cur 已經(jīng)指向了要被刪除的節(jié)點，還記得我們剛剛說的么？要刪除這個節(jié)點，我們就要將這個節(jié)點前面的節(jié)點（它的前鄰居）指向它后面的節(jié)點（它的后鄰居），無視該節(jié)點，達到刪除該節(jié)點的效果，而我們定義的節(jié)點類里面之后 getNext() 方法，沒有任何關于查找前節(jié)點的方法，因此我們只通過 cur 這一個變量，是無法完成刪除操作的。為了解決這一問題，我們引入了一個新的變量 ?pre ，cur 與之前一樣，標記在鏈表中的當前位置。新的引用 pre 總是指向 cur上一次訪問的節(jié)點。這樣一來，當 cur指向需要被移除的節(jié)點時，pre 正好指向要刪除節(jié)點的“前鄰居”，可以起到修改前節(jié)點指向的作用。
一旦搜索過程結(jié)束，就需要執(zhí)行刪除操作。而刪除操作又包括有以下兩種情況：刪除頭節(jié)點，刪除其他節(jié)點。
如果被刪除的元素正好是鏈表的頭節(jié)點所包含的元素的話，那么 cur會指向頭節(jié)點，而 pre 則依舊為它的默認值 None，在這種情況下，我們只需要修改 cur 即可，告訴它頭節(jié)點變成了它后面那個節(jié)點，而不再是它本身就可以了，無需修改 pre 的值。
如果 pre 的值不是 None，則說明需要移除的節(jié)點在鏈表結(jié)構(gòu)中的某個位置。在這種情況下，pre 指向了 next 引用需要被修改的節(jié)點。我們對 pre 進行 setNext() 方法來進行節(jié)點的指向修改操作，這將意味著，pre 的下一個節(jié)點將指向 cur的下一個節(jié)點，而不再是指向 cur 本身了，修了指向，從而起到了刪除 cur 的效果。
如果是刪除最后的節(jié)點，我們應該告訴倒數(shù)第二個節(jié)點，它的下一個節(jié)點為空，即倒數(shù)第二個節(jié)點的指向為None。
總結(jié)
恭喜你，又完成了一個數(shù)據(jù)結(jié)構(gòu)類型的學習，在本次的文章中，我主要通過實現(xiàn)無序列表的方式來對鏈表的操作進行了詳細的講解，至于為什么不單獨進行鏈表的講解，最主要還是因為 python 底層的代碼寫的非常的強大，它將數(shù)組和鏈表結(jié)合在一起進而實現(xiàn)了列表，數(shù)組和鏈表其實就是列表實現(xiàn)的本質(zhì)，沒有這兩個數(shù)據(jù)結(jié)構(gòu)類型，列表便不會存在。我們平常的 python 使用中，一般都更常用列表，因此我們以列表為由，引出了它的本質(zhì)之一，鏈表。
流沙團隊聯(lián)合AI悅創(chuàng)|久遠·推出輔導班啦，包括「Python 語言輔導班、C++ 輔導班、java 輔導班、算法/數(shù)據(jù)結(jié)構(gòu)輔導班、少兒編程、pygame 游戲開發(fā)」，全部都是一對一教學：一對一輔導 + 一對一答疑 + 布置作業(yè) + 項目實踐等。QQ、微信在線，隨時響應！
長按識別下方二維碼，和眾多位島民一起
把別人的頓悟，變成你的基本功
?花半秒鐘就看透事物本質(zhì)的人，
? 和花一輩子都看不清的人，
? 注定是截然不同的命運。
