前言：本篇文章只是記錄王爭的數(shù)據(jù)結(jié)構(gòu)與算法之美的學習筆記，寫下來能強迫自己系統(tǒng)的再過一遍，加深理解。這門課以實際開發(fā)中遇到的問題為例，引入解決問題涉及到的的數(shù)據(jù)結(jié)構(gòu)和算法，但不會講的太細，最好結(jié)合一本實體書進行學習。

1. 鏈表

鏈表和數(shù)組都是非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，通常也會放到一塊來比較，通過和數(shù)組對比，我們來了解一下鏈表的概念。

鏈表和數(shù)組最根本的區(qū)別是底層的存儲結(jié)構(gòu)不同。

數(shù)組是需要一塊連續(xù)的內(nèi)存空間來存儲的，對內(nèi)存的要求比較高。比如我們申請一個 100MB 大小的數(shù)組，當內(nèi)存中沒有連續(xù)的、足夠大的存儲空間時，及時內(nèi)存剩余空間 > 100MB，仍然會申請失敗。

鏈表則相反，它并不是連續(xù)的，而是通過指針將一組零散的內(nèi)存塊串了起來，所以在和上面相同的場景下，如果申請的是 100MB 大小的鏈表，則不會有任何問題。

兩者的區(qū)別如下圖所示：

image.png

2. 鏈表的分類

最常見的有三種：單鏈表、雙向鏈表、循環(huán)鏈表。

2.1 單鏈表

上面??有提到，鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起。這些個零散的內(nèi)存塊，我們稱為鏈表的結(jié)點，那為了將這些結(jié)點串聯(lián)起來，每個鏈表的結(jié)點除了存儲數(shù)據(jù)之外，還需要記錄下一個結(jié)點的地址，我們把這個記錄下個結(jié)點地址的指針叫做后繼指針 next，如下圖所示：

image.png

在鏈表中，第一個結(jié)點稱為頭結(jié)點，最后一個結(jié)點稱為尾節(jié)點。頭結(jié)點用來記錄鏈表的基地址，有了頭結(jié)點，就可以遍歷整條鏈表。尾結(jié)點的 next 指針指向一個空地址 NULL，標明這是鏈表的最后一個結(jié)點。

2.1.1 鏈表的插入和刪除

鏈表也支持數(shù)據(jù)的查找、插入和刪除操作，和數(shù)組不同，在鏈表中插入或者刪除一個數(shù)據(jù)，我們并不需要考慮內(nèi)存的連續(xù)性，因為鏈表的存儲空間本身就不是連續(xù)的，所以鏈表中的插入和刪除都是比較快速的，如下圖：

image.png

我們只需要考慮相鄰結(jié)點的指針改變就行，時間復雜度為 O(1)。

2.1.2 鏈表的隨機訪問

相對于數(shù)組的插入和刪除，鏈表的表現(xiàn)是比較高效的，但是對于隨機訪問第 k 個元素，就沒有數(shù)組那么高效了。鏈表需要一個結(jié)點一個結(jié)點的區(qū)遍歷，直到找到相應的節(jié)點。

鏈表就相當于是一個隊伍，隊伍的每個人只需要直到后面的人是誰就行了，所以我們想知道第 k 位的人時，就需要從第一個人開始，一個一個的往下數(shù)，所以時間復雜度為 O(n) 。

2.2 循環(huán)鏈表

顧名思義，循環(huán)鏈表就是一個循環(huán)的單鏈表，和單鏈表唯一的區(qū)別就是循環(huán)鏈表的尾結(jié)點的 next 指針指向了頭結(jié)點，首尾相連了，如下圖所示：

image.png

和單鏈表相比，循環(huán)鏈表的優(yōu)點是從鏈表尾到鏈表頭很方便，當要處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)時，適合使用循環(huán)鏈表。

2.3 雙向鏈表

單鏈表只有一個方向，只有一個后繼指針 next 指向后面的節(jié)點。但是雙向鏈表支持兩個方向，除了這個后繼指針之外，還有一個前繼指針 prev 指向前面的結(jié)點，如下圖所示：

image.png

從上圖中可以看出，雙向鏈表占用的空間比單鏈表更多，雖然兩個指針比較浪費空間，但是可以支持雙向遍歷。

從結(jié)構(gòu)上來看，雙向鏈表相比于單鏈表可以支持 O(1) 時間復雜度的情況下找到前驅(qū)節(jié)點，因此在某種情況下，雙向鏈表的插入和刪除等操作比單鏈表更簡單，高效。

比如，刪除操作。從鏈表中刪除一個數(shù)據(jù)無外乎兩種情況：

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

對于第一種情況，不管是單鏈表還是雙向鏈表，為了查找值等于給定值的結(jié)點，都需要從頭結(jié)點開始依次遍歷對比，直到找到值等于給定值的結(jié)點，然后再通過指針操作將其刪除。

刪除操作的時間復雜度是 O(1)，但是遍歷查找的時間則是主要的耗時點，對應的時間復雜度為 O(n)，根據(jù)時間復雜度分析中的加法法則，刪除值等于給定值的結(jié)點對應的鏈表操作的總時間復雜度為 O(n)。

對于第二種情況，我們已經(jīng)找到了要刪除的結(jié)點，但是刪除某個節(jié)點 q 需要知道其前驅(qū)結(jié)點，但是單鏈表查找前驅(qū)結(jié)點，又得從頭開始遍歷。對于雙向鏈表來說，這種情況就很 easy 了，因為雙向鏈表中的結(jié)點已經(jīng)保存了前驅(qū)結(jié)點的指針。這種情況下，單鏈表刪除需要 O(n) 的時間復雜度，雙向鏈表只需要在 O(1)的時間復雜度內(nèi)就搞定了。

雙向鏈表其實涉及到了一個空間換時間的設(shè)計思想，當內(nèi)存空間充足的時候，我們可以選擇空間復雜度相對較高、時間復雜度相對很低的算法或數(shù)據(jù)結(jié)構(gòu)。緩存的設(shè)計就是利用了這種思想，我們把數(shù)據(jù)提前加載在內(nèi)存中，雖然比較會耗費內(nèi)存空間，但是每次數(shù)據(jù)查詢的速度就會提高了。

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

2.5 雙向循環(huán)鏈表

這玩意就是雙向鏈表和循環(huán)鏈表的結(jié)合體，如下圖所示：

image.png

3. 鏈表和數(shù)組性能PK

鏈表和數(shù)組的內(nèi)存存儲結(jié)構(gòu)不同，它們的插入、刪除、隨機訪問操作的時間復雜度相反，如下圖所示：

image.png

數(shù)組：

• 簡單易用，內(nèi)存連續(xù)
• 大小固定，需要占用整塊連續(xù)內(nèi)存空間

鏈表：

• 對 CPU 緩存不友好，無法有效預讀
• 大小沒有限制，支持動態(tài)擴容

4. 用鏈表實現(xiàn) LRU 緩存淘汰算法

大概思路：
當有一個新的數(shù)據(jù)被訪問時，從鏈表頭部開始順序遍歷鏈表
1.如果這個數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，就將這個數(shù)據(jù)對應的結(jié)點從原來位置刪除，然后插入到鏈表的頭部
2.如果數(shù)據(jù)沒有在緩存鏈表中：
2.1 如果此時緩存未滿，將此結(jié)點直接插入到鏈表的頭部
2.2 如果此時緩存滿了，將鏈表尾結(jié)點刪除，將新的數(shù)據(jù)插入鏈表的頭部

這種緩存訪問的時間復雜度為 O(n)。

5. 寫鏈表相關(guān)代碼的技巧

5.1 理解指針或者引用的含義

將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者說，指針中存儲了這個變量的內(nèi)存地址，指向了這個變量，通過指針就能找到這個變量。

比如 p->next = q，p 節(jié)點中的 next 指針存儲了 q 結(jié)點的內(nèi)存地址。

5.2 警惕指針丟失和內(nèi)存泄漏

插入或者刪除節(jié)點時要注意操作的順序和手動釋放內(nèi)存空間。

5.3 利用哨兵簡化實現(xiàn)難度

針對于鏈表的插入、刪除操作，需要對插入的第一個結(jié)點和刪除最后一個結(jié)點的情況進行特殊處理。

這種情況可以引入哨兵結(jié)點，不管鏈表是否為空，head 指針都會一直指向這個哨兵結(jié)點。有哨兵結(jié)點的鏈表叫做帶頭鏈表。

image.png

從上圖中可以發(fā)現(xiàn)，哨兵結(jié)點是不存儲數(shù)據(jù)的，所以插入第一個節(jié)點和插入其他節(jié)點，都可以統(tǒng)一為相同的代碼實現(xiàn)邏輯了。

5.4 重點留意邊界條件處理

• 鏈表為空時
• 只包含一個結(jié)點時
• 只包含兩個結(jié)點時
• 代碼邏輯在處理頭結(jié)點和為結(jié)點時
  等等

5.5 舉例畫圖，輔助思考

可以舉例畫圖

6. 練習操作

• 單鏈表的基礎(chǔ)操作：
  鏈表構(gòu)建、指定位置添加結(jié)點、指定位置刪除節(jié)點、打印鏈表、頭插法、尾插法

• 單鏈表反轉(zhuǎn)：
  迭代方法&遞歸方法實現(xiàn)

• 環(huán)的檢測
  快慢指針

• 兩個有序鏈表合并
  遞歸&迭代（增加虛擬頭結(jié)點）

• 刪除鏈表倒數(shù)第 n 個結(jié)點
  兩個指針

• 求鏈表的中間結(jié)點
  快慢指針

• 判斷鏈表是否為回文鏈表