本講內(nèi)容

鏈表定義和分類
鏈表和數(shù)組比較
鏈表操作
寫鏈表代碼的技巧
簡單算法題

鏈表定義和分類

定義：通過指針把零散的內(nèi)存空間串聯(lián)起來存儲數(shù)據(jù)
思想：空間換時間

對于執(zhí)行較慢的程序，可以通過消耗更多的內(nèi)存（空間換時間）來進行優(yōu)化；而消耗過多內(nèi)存的程序，可以通過消耗更多的時間（時間換空間）來降低內(nèi)存的消耗。

分類：單鏈表，循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表

單鏈表

循環(huán)鏈表是一種特殊的單鏈表，單鏈表尾指針指向null，循環(huán)鏈表尾指針指向頭節(jié)點

循環(huán)鏈表

雙向鏈表

單鏈表是單向的，每個節(jié)點只有一個指針，而雙向鏈表每個節(jié)點有兩個指針，所以占用的空間更大，但是它的操作相比于單鏈表更靈活高效。
接下來我們看下主要高效在什么地方？
刪除操作：

• 刪除結(jié)點中“值等于某個給定值”的結(jié)點；
• 刪除給定指針指向的結(jié)點。

第一種情況，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點，都需要從頭結(jié)點開始一個一個依次遍歷對比，直到找到值等于給定值的結(jié)點，然后再通過我前面講的指針操作將其刪除。盡管單純的刪除操作時間復(fù)雜度是 O(1)，但遍歷查找的時間是主要的耗時點，對應(yīng)的時間復(fù)雜度為 O(n)。根據(jù)時間復(fù)雜度分析中的加法法則，刪除值等于給定值的結(jié)點對應(yīng)的鏈表操作的總時間復(fù)雜度為 O(n)。
第二種情況，我們已經(jīng)找到了要刪除的結(jié)點，但是刪除某個結(jié)點 q 需要知道其前驅(qū)結(jié)點，而單鏈表并不支持直接獲取前驅(qū)結(jié)點，所以，為了找到前驅(qū)結(jié)點，我們還是要從頭結(jié)點開始遍歷鏈表，直到 p->next=q，說明 p 是 q 的前驅(qū)結(jié)點。
對于單鏈表，需要從頭遍歷找到該節(jié)點的前向節(jié)點指針，然后指向刪除操作，刪除操作時間復(fù)雜度O(1)，但是遍歷節(jié)點的時間復(fù)雜度為 O(n)，所以根據(jù)復(fù)雜度計算的加法原則，總時間復(fù)雜度為 O(n)
對于雙向鏈表，找到的節(jié)點包含前向節(jié)點的指針，因此不需要再進行遍歷，找到前向節(jié)點O(1)，刪除節(jié)點O(1)，所以總時間復(fù)雜度為 O(1)

雙向循環(huán)鏈表

鏈表和數(shù)組比較

image.png

鏈表操作

1. 插入和刪除

   
   
   單鏈表的插入和刪除

2. 查找

寫鏈表代碼技巧

技巧一：理解指針或引用的含義

將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者反過來說，指針中存儲了這個變量的內(nèi)存地址，指向了這個變量，通過指針就能找到這個變量。
示例：
p->next=q。這行代碼是說，p 結(jié)點中的 next 指針存儲了 q 結(jié)點的內(nèi)存地址。
p->next=p->next->next。這行代碼表示，p 結(jié)點的 next 指針存儲了 p 結(jié)點的下下一個結(jié)點的內(nèi)存地址。

技巧二：警惕指針丟失和內(nèi)存泄漏

示例：
單鏈表的插入

單鏈表的插入

p->next = x; // 將p的next指針指向x結(jié)點；
x->next = p->next; // 將x的結(jié)點的next指針指向b結(jié)點；

以上代碼會導(dǎo)致指針丟失，b節(jié)點后的節(jié)點無法訪問

插入結(jié)點時，一定要注意操作的順序

正確寫法：

x->next = p->next; // 將x的結(jié)點的next指針指向b結(jié)點；
p->next = x; // 將p的next指針指向x結(jié)點；

刪除鏈表結(jié)點時，也一定要記得手動釋放內(nèi)存空間，否則，也會出現(xiàn)內(nèi)存泄漏的問題。當然，對于像 Java 這種虛擬機自動管理內(nèi)存的編程語言來說，就不需要考慮這么多了。

注：什么是內(nèi)存泄漏？
內(nèi)存泄露 memory leak，是指程序在申請內(nèi)存后，無法釋放已申請的內(nèi)存空間，一次內(nèi)存泄露危害可以忽略，但內(nèi)存泄露堆積后果很嚴重，無論多少內(nèi)存，遲早會被占光。
memory leak會最終會導(dǎo)致out of memory(內(nèi)存溢出)！

技巧三：利用哨兵簡化實現(xiàn)難度

• 為什么要引入哨兵？
  針對鏈表的插入、刪除操作，需要對插入第一個結(jié)點和刪除最后一個結(jié)點的情況進行特殊處理。
  單鏈表插入
  其他節(jié)點插入

x->next = p->next; // 將x的結(jié)點的next指針指向b結(jié)點；
p->next = x; // 將p的next指針指向x結(jié)點；

第一個節(jié)點的插入

if (head == null) { head = new_node;}

單鏈表刪除
其他節(jié)點刪除

p->next = p->next->next;

最后一個節(jié)點刪除

if (head->next == null) { head = null;}

如果我們引入哨兵結(jié)點，在任何時候，不管鏈表是不是空，head 指針都會一直指向這個哨兵結(jié)點。我們也把這種有哨兵結(jié)點的鏈表叫帶頭鏈表。相反，沒有哨兵結(jié)點的鏈表就叫作不帶頭鏈表。

帶頭鏈表

哨兵結(jié)點是不存儲數(shù)據(jù)的。因為哨兵結(jié)點一直存在，所以插入第一個結(jié)點和插入其他結(jié)點，刪除最后一個結(jié)點和刪除其他結(jié)點，都可以統(tǒng)一為相同的代碼實現(xiàn)邏輯了。

技巧四：重點留意邊界條件處理

要實現(xiàn)沒有 Bug 的鏈表代碼，一定要在編寫的過程中以及編寫完成之后，檢查邊界條件是否考慮全面，以及代碼在邊界條件下是否能正確運行。

常需檢查的邊界情況：

• 如果鏈表為空時，代碼是否能正常工作？
• 如果鏈表只包含一個結(jié)點時，代碼是否能正常工作？
• 如果鏈表只包含兩個結(jié)點時，代碼是否能正常工作？
• 代碼邏輯在處理頭結(jié)點和尾結(jié)點的時候，是否能正常工作？

技巧五：舉例畫圖，輔助思考

技巧六：多寫多練，沒有捷徑

• 單鏈表反轉(zhuǎn)
• 鏈表中環(huán)的檢測
• 兩個有序的鏈表合并
• 刪除鏈表倒數(shù)第 n 個結(jié)點
• 求鏈表的中間結(jié)點

簡單算法題

如何實現(xiàn)LRU緩存淘汰算法？