以后再也不怕別人問(wèn)「單鏈表」的問(wèn)題啦

寫(xiě)在之前

在程序設(shè)計(jì)里，我們經(jīng)常需要將同為某個(gè)類(lèi)型的一組數(shù)據(jù)元素作為一個(gè)整體來(lái)使用，需要?jiǎng)?chuàng)建這種元素組，用變量來(lái)記錄它們或者傳入函數(shù)等等等等，「線(xiàn)性表」就是這樣一組元素的抽象，它是某類(lèi)元素的集合并且記錄著元素之間一種順序關(guān)系，是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實(shí)際程序中運(yùn)用非常廣泛，比如 Python 中的 list 和 tuple 都可以看作是線(xiàn)性表的實(shí)現(xiàn)。

基于各種實(shí)際操作等方面的綜合考慮，我們提出了兩種實(shí)現(xiàn)線(xiàn)性表的形式：「順序表」和「鏈表」。

「順序表」是將表中的元素順序存放在一大塊連續(xù)的存儲(chǔ)區(qū)間里，所以在這里元素間的順序是由它們的存儲(chǔ)順序來(lái)表示的?！告湵怼箘t是將表中元素存放在一系列的結(jié)點(diǎn)中（結(jié)點(diǎn)的存儲(chǔ)位置可以是連續(xù)的，可以是不連續(xù)的，也就意味著它們可以存在任何內(nèi)存未被占用的位置），這些結(jié)點(diǎn)通過(guò)連接構(gòu)造起來(lái)，結(jié)點(diǎn)分為「數(shù)據(jù)域」和「指針域」。這次我們要學(xué)習(xí)的「單鏈表」就是「鏈表」的一種實(shí)現(xiàn)形式，「數(shù)據(jù)域」保存著作為表元素的數(shù)據(jù)項(xiàng)，「指針域」保存同一個(gè)表里的下一個(gè)結(jié)點(diǎn)的標(biāo)識(shí)。

在正式說(shuō)「單鏈表」之前，我先來(lái)說(shuō)一下很多人在學(xué)習(xí)鏈表之初都傻傻分不清的兩個(gè)東西：「頭結(jié)點(diǎn)」和「頭指針」。

「頭結(jié)點(diǎn)」的設(shè)立是為了操作的統(tǒng)一和方便，是放在第一個(gè)元素的節(jié)點(diǎn)之前，它的數(shù)據(jù)域一般沒(méi)有意義，并且它本身也不是鏈表必須要帶的。那設(shè)立頭節(jié)點(diǎn)的目的是什么呢？其實(shí)就是為了在某些時(shí)候可以更方便的對(duì)鏈表進(jìn)行操作，有了頭結(jié)點(diǎn)，我們?cè)趯?duì)第一個(gè)元素前插入或者刪除結(jié)點(diǎn)的時(shí)候，它的操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了。

「頭指針」顧名思義，是指向鏈表第一個(gè)結(jié)點(diǎn)的指針，如果有頭結(jié)點(diǎn)的話(huà)，那么就是指向頭結(jié)點(diǎn)的指針。它是鏈表的必備元素且無(wú)論鏈表是否為空，頭指針都不能為空，因?yàn)樵谠L問(wèn)鏈表的時(shí)候你總得知道它在什么位置，這樣才能通過(guò)它的指針域找到下一個(gè)結(jié)點(diǎn)的位置，也就是說(shuō)知道了頭指針，整個(gè)鏈表的元素我們都是可以訪問(wèn)的，所以它必須要存在，這也就是我們常說(shuō)的「標(biāo)識(shí)」，這也就是為什么我們一般用頭指針來(lái)表示鏈表。

單鏈表

n 個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，這也就是平時(shí)書(shū)上所說(shuō)的「鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)」，因?yàn)檫@個(gè)鏈表中的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以又叫「單鏈表」。單鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€(xiàn)性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。單鏈表的第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做「頭指針」，最后一個(gè)結(jié)點(diǎn)的指針為「空」，一般用 “^” 表示。

上圖是不帶頭結(jié)點(diǎn)的單鏈表，下面我們來(lái)看一下帶頭結(jié)點(diǎn)的單鏈表：

還有一種是空鏈表：

通過(guò)上面 3 個(gè)圖我們發(fā)現(xiàn)無(wú)論單鏈表是否為空，是否有頭結(jié)點(diǎn)，頭指針都是存在的，這就很好的印證了之前我們所說(shuō)的「頭指針是鏈表的必備元素且無(wú)論鏈表是否為空，頭指針都不能為空」。

為了方便后續(xù)的操作，我們一般會(huì)先定義一個(gè)簡(jiǎn)單的結(jié)點(diǎn)類(lèi)：

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

單鏈表的基本操作

首先我們先來(lái)創(chuàng)建一個(gè)鏈表類(lèi)：

class LinkList(object): def __init__(self): self.head = Node(None) # 判斷鏈表是否為空 def IsEmpty(self): p = self.head # 頭指針 if p.next == None: print("List is Empty") return True return False # 打印鏈表 def PrintList(self): if self.IsEmpty(): return False p = self.head while p: print(p.data,end=' ') p = p.next

1.創(chuàng)建單鏈表

創(chuàng)建單鏈表的過(guò)程其實(shí)就是一個(gè)動(dòng)態(tài)生成鏈表的過(guò)程，說(shuō)簡(jiǎn)單點(diǎn)就是從一個(gè)「空鏈表」開(kāi)始，依次建立各個(gè)元素的結(jié)點(diǎn)，并把它們逐個(gè)插入鏈表，時(shí)間復(fù)雜度為 O(n)：

def InitList(self,data): self.head = Node(data[0]) # 頭結(jié)點(diǎn) p = self.head # 頭指針 for i in data[1:]: node = Node(i) p.next = node p = p.next

下面我們來(lái)測(cè)試一下：

# testlst = LinkList()data = [1, 4, 5, 8, 2, 3]lst.InitList(data)lst.PrintList()

輸出結(jié)果如下：

1 4 5 8 2 3

2.計(jì)算單鏈表的長(zhǎng)度

在使用鏈表的時(shí)候，經(jīng)常需要求表的長(zhǎng)度，為此我們可以創(chuàng)建一個(gè)球表長(zhǎng)的函數(shù)，這個(gè)函數(shù)就是從左到右掃描，遍歷表中的所有結(jié)點(diǎn)并完成計(jì)數(shù)，時(shí)間復(fù)雜度為 O(n)：

def LengthList(self): if self.IsEmpty(): return 0 p = self.head cnt = 0 while p: cnt += 1 p = p.next return cnt

下面我們來(lái)測(cè)試一下：

# testlst = LinkList()data = [1, 4, 5, 8, 2, 3]lst.InitList(data)print(lst.LengthList())

輸出的結(jié)果如下：

6

3.單鏈表的插入

假設(shè)我們要將結(jié)點(diǎn) s 插入到 結(jié)點(diǎn) p 的后面，只需要將結(jié)點(diǎn) s 插入到結(jié)點(diǎn) p 和 結(jié)點(diǎn) p.next 之間即可，說(shuō)起來(lái)簡(jiǎn)單，那么到底如何插入呢？請(qǐng)看下圖：

由上圖我們可以看到，單鏈表結(jié)點(diǎn)的插入根本不需要驚動(dòng)其它結(jié)點(diǎn)，只需要讓 s.next 和 p.next 的指針稍作改變即可。讓 p 的后繼結(jié)點(diǎn)改為 s 的后繼結(jié)點(diǎn)，再把 s 的后繼結(jié)點(diǎn)變成 p 的后繼結(jié)點(diǎn)。這里一定要切記，插入操作的順序不能改變，至于為什么，你可以拿起紙筆手動(dòng)的畫(huà)一下，結(jié)果一下子就會(huì)出來(lái)（對(duì)于單鏈表的表頭和表尾的特殊情況，操作是相同的）。

# 單鏈表的插入(在第 s 個(gè)結(jié)點(diǎn)后面插入 data)def InsertList(self,s,data): if self.IsEmpty() or s < 0 or s > self.LengthList(): print("Insert failed！") return p = self.head index = 1 while index < s: ? ? ? ?p = p.next ? ? ? ?index += 1 ? ?node = Node(data) ? ?node.next = p.next ? ?p.next = node

下面我們來(lái)測(cè)試一下：

# testlst = LinkList()data = [1, 4, 5, 8, 2, 3]lst.InitList(data)lst.InsertList(0,666)lst.PrintList()

輸出的結(jié)果如下：

1 666 4 5 8 2 3

4.單鏈表刪除

看完插入，我們現(xiàn)在再來(lái)看看單鏈表的刪除。假設(shè)我們想要?jiǎng)h除一個(gè)結(jié)點(diǎn) q，其實(shí)就是將它的前繼結(jié)點(diǎn) p 的指針繞過(guò) q，直接指向 q 的后繼結(jié)點(diǎn)即可，具體操作如下圖所示：

由上圖可以看出，我們只需要一步就可以實(shí)現(xiàn)刪除操作，那就是讓 p.next 直接為 p 的 next 的 next，p 的 next 為 q，所以也就是 p.next = q.next，時(shí)間復(fù)雜度為 O(n)。

# 單鏈表的刪除(刪除第 s 個(gè)結(jié)點(diǎn))def DeleteList(self, s): if self.IsEmpty() or s < 0 or s > self.LengthList(): print("Delete failed! ") return p = self.head index = 1 while index < s: ? ? ? ?pre = p ? ? ? ?index += 1 ? ? ? ?p = p.next ? ?pre.next = p.next ? ?p = None

由 p = None 可以看出，在 Python 中，只需要簡(jiǎn)單的將指針賦值為 None，就拋棄了鏈表原有的結(jié)點(diǎn)，Python 解釋器的存儲(chǔ)管理系統(tǒng)會(huì)自動(dòng)回收不用的存儲(chǔ)。

下面我們來(lái)測(cè)試一下：

# testlst = LinkList()data = [1, 4, 5, 8, 2, 3]lst.InitList(data)lst.DeleteList(3)lst.PrintList()

輸出的結(jié)果如下：

1 4 8 2 3

5.單鏈表的讀取

在順序結(jié)構(gòu)中，我們想要獲取任意一個(gè)元素的存儲(chǔ)位置是很容易的，但是在單鏈表中，第 i 個(gè)元素到底在哪我們一開(kāi)始沒(méi)辦法知道，只能傻傻的從頭開(kāi)始找，所以在對(duì)于單鏈表獲取第 i 個(gè)元素的操作，算法上相對(duì)麻煩一些。

# 單鏈表的讀取（獲取第 s 個(gè)結(jié)點(diǎn)的值）def GetList(self, s): if self.IsEmpty() or s < 0 or s > self.LengthList(): print("Read failed! ") return p = self.head index = 1 while index < s: ? ? ? ?index += 1 ? ? ? ?p = p.next ? ?print("第 {} 個(gè)值為 {}".format(s, p.data))

從上面的代碼我們可以很清楚的看出，單鏈表獲取第 i 個(gè)元素就是從頭開(kāi)始找，知道第 i 個(gè)元素為止，所以我們可以很容易的估算出它的時(shí)間復(fù)雜度是 O(n)。任何事物都不是完美的，有好的地方就有壞的地方，元素的讀取就是單鏈表美中不足的地方之一。

寫(xiě)在之后

單鏈表的操作其實(shí)還有不少，我只是寫(xiě)了其中常用的幾種，希望大家能自己動(dòng)手嘗試一下，把這幾個(gè)搞懂搞透。碰到這樣的問(wèn)題從哪個(gè)方面去思考，如何去做才是最重要的，只有學(xué)會(huì)了這些，你在日后碰到相關(guān)問(wèn)題的時(shí)候就知道如何去下手。

我在上面每個(gè)操作的講解中大多數(shù)給出了圖，通過(guò)圖來(lái)看解法題目了然。算法這個(gè)東西其實(shí)就是這樣，多動(dòng)手實(shí)現(xiàn)以下，想不明白了就動(dòng)手畫(huà)一下，畫(huà)著畫(huà)著思路就出來(lái)了。

最后我們就來(lái)總結(jié)一下鏈表操作的時(shí)間復(fù)雜度，如果你還不會(huì)估算算法的時(shí)間復(fù)雜度，請(qǐng)看我的循序漸進(jìn)帶你學(xué)習(xí)時(shí)間復(fù)雜度和空間復(fù)雜度。

創(chuàng)建空表 O(1)。

創(chuàng)建單鏈表 O(n)

插入元素：首端插入為 O(1)；尾端插入為 O(n)，因?yàn)檫€要找到表的最后結(jié)點(diǎn)；定位插入 為O(n)。

刪除元素：首端刪除為 O(1)；尾端刪除為 O(n)，理由如上；定位刪除為 O(n)。

以下是上述所有操作的代碼匯總：

# 結(jié)點(diǎn)類(lèi)class Node(object): def __init__(self,data): self.data = data self.next = None# 鏈表類(lèi)class LinkList(object): def __init__(self): self.head = Node(None) # 判斷鏈表是否為空 def IsEmpty(self): p = self.head # 頭指針 if p.next == None: print("List is Empty") return True return False # 打印鏈表 def PrintList(self): if self.IsEmpty(): return False p = self.head while p: print(p.data,end= ' ') p = p.next # 創(chuàng)建單鏈表 def InitList(self,data): self.head = Node(data[0]) # 頭結(jié)點(diǎn) p = self.head # 頭指針 for i in data[1:]: node = Node(i) p.next = node p = p.next # 單鏈表的長(zhǎng)度 def LengthList(self): if self.IsEmpty(): return 0 p = self.head cnt = 0 while p: cnt += 1 p = p.next return cnt # 單鏈表的插入(在第 s 個(gè)結(jié)點(diǎn)后面插入 data) def InsertList(self,s,data): if self.IsEmpty() or s < 0 or s > self.LengthList(): print("Insert failed！") return p = self.head index = 1 while index < s: ? ? ? ? ? ?p = p.next ? ? ? ? ? ?index += 1 ? ? ? ?node = Node(data) ? ? ? ?node.next = p.next ? ? ? ?p.next = node ? ?# 單鏈表的刪除(刪除第 s 個(gè)結(jié)點(diǎn)) ? ?def DeleteList(self, s): ? ? ? ?if self.IsEmpty() or s < 0 or s > self.LengthList(): print("Delete failed! ") return p = self.head index = 1 while index < s: ? ? ? ? ? ?pre = p ? ? ? ? ? ?index += 1 ? ? ? ? ? ?p = p.next ? ? ? ?pre.next = p.next ? ? ? ?p = None ? ?# 單鏈表的讀?。ǐ@取第 s 個(gè)結(jié)點(diǎn)的值） ? ?def GetList(self, s): ? ? ? ?if self.IsEmpty() or s < 0 or s > self.LengthList(): print("Read failed! ") return p = self.head index = 1 while index < s: ? ? ? ? ? ?index += 1 ? ? ? ? ? ?p = p.next ? ? ? ?print("第 {} 個(gè)值為 {}".format(s, p.data))