六十九、數(shù)據(jù)結(jié)構(gòu)鏈表的實現(xiàn)

「@Author：Runsen」

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

鏈表 Linked List

鏈表由許多結(jié)點(也可以叫節(jié)點或元素)組成，每一個結(jié)點有兩個域，左邊部份叫值域 data，用于存放用戶數(shù)據(jù)；右邊叫指針域 next，一般是存儲著到下一個元素的指針。head結(jié)點(頭節(jié)點)，head是一個特殊的結(jié)節(jié)，head結(jié)點永遠(yuǎn)指向第一個結(jié)點，tail結(jié)點(尾節(jié)點)，tail結(jié)點也是一個特殊的結(jié)點，tail結(jié)點永遠(yuǎn)指向最后一個節(jié)點，tail.next = None。

節(jié)點結(jié)構(gòu)

上面四個節(jié)點 abcd 組成一個鏈表，每一個節(jié)點都包含 data 和 next，尾節(jié)點的 next 指向 None。

鏈表中的元素都會兩個屬性，一個是元素的值，另一個是指針，此指針標(biāo)記了下一個元素的地址，每一個數(shù)據(jù)都會保存下一個數(shù)據(jù)的內(nèi)存的地址，通過此地址可以找到下一個數(shù)據(jù)，任意位置插入元素和刪除元素效率較高，時間復(fù)雜度為O(1)。

要需要訪問某個位置的數(shù)據(jù)，需要從第一個數(shù)據(jù)開始找起，依次往后遍歷，直到找到待查詢的位置，故可能在查找某個元素時，時間復(fù)雜度達(dá)到O(N)

優(yōu)點：

• 任意位置插入元素和刪除元素的速度快，時間復(fù)雜度為O(1)
• 內(nèi)存利用率高，不會浪費內(nèi)存

缺點：

• 隨機(jī)訪問效率低，時間復(fù)雜度為0(N)

鏈表與我們熟悉的數(shù)組相對比，數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間，對內(nèi)存的要求比較高，如果聲明的數(shù)組過大，系統(tǒng)可能沒有足夠的連續(xù)空間分配給它。

而鏈表恰恰相反，它并不需要一塊連續(xù)的內(nèi)存空間，它通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來使用。

雙鏈表 Doubly Linked List

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。

鏈表代碼實現(xiàn)

下面以class類創(chuàng)建節(jié)點， 每個節(jié)點包含當(dāng)前節(jié)點所要存的數(shù)據(jù)data，和指向下一節(jié)點的指針。

節(jié)點類的定義很簡單，節(jié)點只有兩個屬性，data 和 next，next指向下一個節(jié)點。定義完節(jié)點類后，可以創(chuàng)建節(jié)點，但是還需要將節(jié)點連接在一起，構(gòu)成鏈表才可以。

我們用 Python 語言來自己實現(xiàn)一個單向鏈表結(jié)構(gòu)，以加深理解。

功能需求：

創(chuàng)建一個 SingleLinkedList 類，具備以下功能：

• append(data) ?將元素添加到鏈表頭，需要參數(shù)，無返回值。
• is_empty() ?檢查單鏈表是否為空，不需要參數(shù)，返回布爾值。
• iter() ?遍歷鏈表。
• insert(index, vaule) 指定位置刪除。
• remove(index) 實現(xiàn)移除鏈表指定索引的節(jié)點。
• size() ?返回單鏈表中元素個數(shù)，不需要參數(shù)，返回整數(shù)。

class?Node:
????'''定義節(jié)點類'''
????def?__init__(self,?data):
????????self.data?=?data????#值域，存儲數(shù)據(jù)
????????self.next?=?None????#指針域，存儲下一元素的地址

#定義四個節(jié)點
a?=?Node(86)
b?=?Node(19)
c?=?Node(4)
d?=?Node(12)
#最簡單的方法將四個節(jié)點連接
a.next?=?b
b.next?=?c
c.next?=?d
head?=?a
#依次輸出節(jié)點的值
while?head?is?not?None:
????print(head.data)
????head?=?head.next
#輸出為?86?19?4?12

定義一個鏈表類來實現(xiàn)鏈表，同時可以定義對鏈表的簡單操作，比如對鏈表進(jìn)行添加節(jié)點，移除節(jié)點，插入節(jié)點等方法。

class?LinkedList:
????'''定義鏈表類'''
????def?__init__(self):????#不需要參數(shù)，返回值是空鏈表
????????self.head?=?None???#頭節(jié)點
????????self.tail?=?None???#尾節(jié)點

定義類方法，判斷鏈表是否為空。

def?is_empty(self):????
????'''判斷鏈表是否為空'''
????return?self.head?is?None

定義類方法，向鏈表末尾新的節(jié)點。

def?append(self,?data):????
????'''向鏈表里添加節(jié)點'''
????node?=?Node(data)??????#創(chuàng)建一個節(jié)點實例
????if?self.head?is?None:??#判斷鏈表是否為空
?????????self.head?=?node???#如果是空鏈表，添加一個節(jié)點，頭節(jié)點就是尾節(jié)點
?????????self.tail?=?node
?????else:
?????????self.tail.next?=?node??#tail為尾節(jié)點，在尾節(jié)點添加新節(jié)點，尾節(jié)點的指針域
?????????self.tail?=?node???????#指向下一節(jié)點，這時新的尾節(jié)點就是node節(jié)點

定義類方法，實現(xiàn)遍歷鏈表元素。

def?iter(self):????????????
????'''遍歷鏈表,函數(shù)返回的是一個生成器'''
????if?not?self.head:????#遍歷從鏈表的頭節(jié)點開始，如果不是，返回
????????return
????current?=?self.head??#將head節(jié)點賦值給current,當(dāng)前節(jié)點
????yield?current.data???#包含yield語句的函數(shù)都被稱為生成器。
????while?current.next:
????????current?=?current.next
????????yield?current.data

定義類方法，實現(xiàn)在鏈表指定位置插入新的節(jié)點。

def?insert(self,?index,?vaule):????
????'''在鏈表的指定索引插入一個新的節(jié)點'''
????current?=?self.head
????current_index?=?0????????#head節(jié)點的索引為0
????if?self.head?is?None:????#如果鏈表為空
????????raise?Exception("The?list?is?an?empty?list")
????while?current_index?-1:??#通過while循環(huán)找到指定索引的節(jié)點
????????current?=?current.next
????????if?current?is?None:??#判斷是否為尾節(jié)點
????????????raise?Exception('......')
????????current_index?+=?1
????node?=?Node(vaule)???????#新建節(jié)點
????node.next?=?current.next?#node的指針域指向原節(jié)點的下一節(jié)點
????current.next?=?node??????#原節(jié)點的下一節(jié)點指向node
????if?node.next?is?None:
????????self.tail?=?node

要向 a 和 b節(jié)點之間插入一個新的節(jié)點 e ，需要將 e.next = a.next，之后再將 a.next = e，這是插入一個新的節(jié)點的關(guān)鍵。

定義類方法，實現(xiàn)移除鏈表指定索引的節(jié)點。

def?remove(self,?index):
????'''移除鏈表指定索引元素'''
????current?=?self.head
????current_index?=?0
????if?self.head?is?None:??#?空鏈表時
????????raise?Exception('The?list?is?an?empty?list')
????while?current_index?-1:
????????current?=?current.next
????????if?current?is?None:
????????????raise?Exception('list?length?less?than?index')
????????current_index?+=?1
????if?index?==?0:???#?當(dāng)刪除第一個節(jié)點時
????????self.head?=?current.next
????????current?=?current.next
????????return
????if?self.head?is?self.tail:???#?當(dāng)只有一個節(jié)點的鏈表時
????????self.head?=?None
????????self.tail?=?None
????????return?
????current.next?=?current.next.next
????if?current.next?is?None:??#?當(dāng)刪除的節(jié)點是鏈表最后一個節(jié)點時
????????self.tail?=?current

定義類方法，返回鏈表的長度(節(jié)點的數(shù)量)。

def?size(self):
????'''返回鏈表長度'''
????current?=?self.head
????count?=?0
????if?current?is?None:
????????return?'The?list?is?an?empty?list'
????while?current?is?not?None:
????????count?+=?1
????????current?=?current.next
????return?count

最后，來實現(xiàn)一下鏈表的一些簡單操作。

if?__name__?==?'__main__':
????l?=?LinkedList()????#創(chuàng)建一個鏈表對象，空鏈表
????for?i?in?range(10):?#向鏈表里添加節(jié)點
????????l.append(i)
????print(list(l.iter()))???#遍歷鏈表元素
????#輸出為[0,?1,?2,?3,?4,?5,?6,?7,?8,?9]
????l.insert(2,?10)????#在索引2處插入10
????print(list(l.iter()))???#遍歷鏈表元素
????#輸出為[0,?1,?10,?2,?3,?4,?5,?6,?7,?8,?9]
????l.remove(0)???????#移除索引為0的節(jié)點
????print(list(l.iter()))???#遍歷鏈表元素
????#輸出為[1,?2,?3,?4,?5,?6,?7,?8,?9]
????print(l.size())???#輸出鏈表的長度?輸出為10

LeetCode 第 2題：兩數(shù)相加

給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。

#?如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。?
#?您可以假設(shè)除了數(shù)字?0?之外，這兩個數(shù)都不會以?0?開頭。?
#?示例：?
#?輸入：(2 -> 4 -> 3)?+?(5 -> 6 -> 4)
#輸出：7 ->?0?-> 8
#原因：342 + 465 = 807
#?
#?Related?Topics?鏈表?數(shù)學(xué)

思路一：將鏈表轉(zhuǎn)化列表，反轉(zhuǎn)列表 用join方法拼接數(shù)字 切片[::-1]，將sum轉(zhuǎn)化成鏈表res

#?class?ListNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.next?=?None


class?Solution:
????def?addTwoNumbers(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:
????????#?將鏈表轉(zhuǎn)化列表
????????val1,?val2?=?[l1.val],?[l2.val]

????????while?l1.next:
????????????val1.append(l1.next.val)
????????????l1?=?l1.next

????????while?l2.next:
????????????val2.append(l2.next.val)
????????????l2?=?l2.next

????????#?反轉(zhuǎn)列表?用join方法拼接數(shù)字?切片[::-1]

????????num_1?=?''.join([str(i)?for?i?in?val1[::-1]])
????????num_2?=?''.join([str(i)?for?i?in?val2[::-1]])
????????sums?=??str(int(num_1)?+?int(num_2))[::-1]
????????#?將sum轉(zhuǎn)化成鏈表res

????????#?頭節(jié)點
????????res??=?head?=?ListNode(int(sums[0]))

????????for?i?in?range(1,?len(sums)):
????????????#?拼接
????????????head.next?=?ListNode(int(sums[i]))
????????????head?=?head.next
????????return?res

思路二：將結(jié)果保存在一個新的鏈表中，使用兩個指針，一個指向頭節(jié)點，用于返回結(jié)果，另一個指向當(dāng)前節(jié)點，用于計算并保存結(jié)果。遍歷兩個輸入鏈表，逐位進(jìn)行相加，若某一個鏈表遍歷到了結(jié)尾，則取 0 參與運(yùn)算。每一位的數(shù)字為兩個數(shù)字對應(yīng)位以及進(jìn)位之和除 10 的余數(shù)，而該位是否有進(jìn)位則是這個和除 10 的商。

優(yōu)化：不需要將整個數(shù)的和求出，只需要每一位對應(yīng)相加，

具體代碼如下：

class?Solution:
????def?addTwoNumbers(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:
???????#?判斷0還是1
????????res?=?0
????????root?=?n?=?ListNode(0)
????
????????while?l1?or?l2?or?res:
????????????v1?=?v2?=?0
????????????if?l1:
????????????????v1?=?l1.val
????????????????l1?=?l1.next
????????????if?l2:
????????????????v2?=?l2.val
????????????????l2?=?l2.next
????????????# divmod()?函數(shù)把除數(shù)和余數(shù)運(yùn)算結(jié)果結(jié)合起來，返回一個包含商和余數(shù)的元組(a // b, a % b)。
????????????res,?val?=?divmod(v1?+?v2?+?res,?10)
????????????n.next?=?ListNode(val)
????????????n?=?n.next
????????????
????????return?root.next

「人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫得自己體會，修煉身心；在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會有所收獲，不留遺憾 （作者：Runsen ）」

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

參考資料