寫在之前

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

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

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

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

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

「頭指針」顧名思義，是指向鏈表第一個結(jié)點的指針，如果有頭結(jié)點的話，那么就是指向頭結(jié)點的指針。它是鏈表的必備元素且無論鏈表是否為空，頭指針都不能為空，因為在訪問鏈表的時候你總得知道它在什么位置，這樣才能通過它的指針域找到下一個結(jié)點的位置，也就是說知道了頭指針，整個鏈表的元素我們都是可以訪問的，所以它必須要存在，這也就是我們常說的「標(biāo)識」，這也就是為什么我們一般用頭指針來表示鏈表。

單鏈表

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

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

還有一種是空鏈表：

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

為了方便后續(xù)的操作，我們一般會先定義一個簡單的結(jié)點類：

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

單鏈表的基本操作

首先我們先來創(chuàng)建一個鏈表類：

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)建單鏈表的過程其實就是一個動態(tài)生成鏈表的過程，說簡單點就是從一個「空鏈表」開始，依次建立各個元素的結(jié)點，并把它們逐個插入鏈表，時間復(fù)雜度為 O(n)：

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

下面我們來測試一下：

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

輸出結(jié)果如下：

1 4 5 8 2 3

2.計算單鏈表的長度

在使用鏈表的時候，經(jīng)常需要求表的長度，為此我們可以創(chuàng)建一個球表長的函數(shù)，這個函數(shù)就是從左到右掃描，遍歷表中的所有結(jié)點并完成計數(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

下面我們來測試一下：

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

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

6

3.單鏈表的插入

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

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

# 單鏈表的插入(在第 s 個結(jié)點后面插入 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

下面我們來測試一下：

# 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)在再來看看單鏈表的刪除。假設(shè)我們想要刪除一個結(jié)點 q，其實就是將它的前繼結(jié)點 p 的指針繞過 q，直接指向 q 的后繼結(jié)點即可，具體操作如下圖所示：

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

# 單鏈表的刪除(刪除第 s 個結(jié)點)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 中，只需要簡單的將指針賦值為 None，就拋棄了鏈表原有的結(jié)點，Python 解釋器的存儲管理系統(tǒng)會自動回收不用的存儲。

下面我們來測試一下：

# 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)中，我們想要獲取任意一個元素的存儲位置是很容易的，但是在單鏈表中，第 i 個元素到底在哪我們一開始沒辦法知道，只能傻傻的從頭開始找，所以在對于單鏈表獲取第 i 個元素的操作，算法上相對麻煩一些。

# 單鏈表的讀?。ǐ@取第 s 個結(jié)點的值）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("第 {} 個值為 {}".format(s, p.data))

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

寫在之后

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

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

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

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

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

插入元素：首端插入為 O(1)；尾端插入為 O(n)，因為還要找到表的最后結(jié)點；定位插入 為O(n)。

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

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

# 結(jié)點類class Node(object): def __init__(self,data): self.data = data self.next = None# 鏈表類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é)點 p = self.head # 頭指針 for i in data[1:]: node = Node(i) p.next = node p = p.next # 單鏈表的長度 def LengthList(self): if self.IsEmpty(): return 0 p = self.head cnt = 0 while p: cnt += 1 p = p.next return cnt # 單鏈表的插入(在第 s 個結(jié)點后面插入 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 個結(jié)點) ? ?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 個結(jié)點的值） ? ?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("第 {} 個值為 {}".format(s, p.data))