数据结构算法入门--链表
2019?年第?76?篇文章，總第?100?篇文章
本文大約?3200?字，閱讀大約需要?10?分鐘
數據結構算法系列：
數據結構算法入門系列第三篇--鏈表，鏈表也是非常常見的數據結構，面試過程中也會經?？嫉较嚓P的題目。
本文首先介紹鏈表的基本情況，比如單向鏈表、雙向鏈表等，然后會介紹一些技巧。
今日推薦閱讀：
?
鏈表也是一個非常常見的數據結構，和數組相比，它不需要連續(xù)的內存空間，對內存的要求不高。
鏈表結構非常多，這里介紹常見的三種結構：單鏈表、雙向鏈表和循環(huán)鏈表。
單鏈表
鏈表是通過指針將一組零散的內存塊串聯在一起，其中，內存塊稱為鏈表的 "結點"，如下圖所示，結點分為兩個部分，存儲數據以及記錄下一個結點的地址的指針，這個指針也稱為后繼指針 next。
從圖中可以看到有兩個結點比較特殊，頭結點和尾結點。其中，頭結點保存鏈表的基地址，而尾結點的指針指向一個空地址 NULL。
鏈表也是支持查找、插入和刪除操作的，對于鏈表的插入和刪除操作，可以如下圖所示，插入和刪除操作，其實僅僅需要改變相鄰結點的指針，對應的時間復雜度是?O(1)。
當然了，有利就有弊，和數組可以實現快速隨機訪問操作相反，鏈表這操作需要?O(n)?的時間復雜度。因為鏈表因為不是連續(xù)的內存塊，所以不能根據首地址和下標，通過尋址公式計算得到目標位置的內存，只能從首結點開始遍歷每個結點，直到找到目標結點。
循環(huán)鏈表
介紹完單鏈表，第二個介紹的就是升級版--循環(huán)鏈表。
循環(huán)鏈表，和單鏈表的區(qū)別主要是**尾結點指向的是鏈表的頭結點，**如下圖所示，因此循環(huán)鏈表構成一個環(huán)，因此稱為循環(huán)鏈表。
循環(huán)鏈表的優(yōu)點就是從鏈尾到鏈頭比較方便。它適合解決具有環(huán)型結構特點的數據，比如著名的約瑟夫問題[^1]。
雙向鏈表
第三個升級版--雙向鏈表，也是比較常用的一種鏈表結構。它的特點就是每個結點包含兩個指針，分別指向前一個結點和后一個結點，也就是兩個方向，所以稱為雙向鏈表，如下圖所示：
相比于單鏈表，因為多一個指針，所以雙向鏈表會占用更多的內存空間，但它也更加靈活，此外，它可以在?O(1)?時間復雜度的情況下找到前驅結點，在某些情況下，插入、刪除等操作會比單鏈表更加簡單和高效。
盡管介紹單鏈表的插入和刪除操作，提到其時間復雜度是?O(1)?，但這里是有一個前提的，就是僅僅插入或者刪除操作，并沒有考慮查找的時間，如果結合查找到結點并插入或者刪除操作，那么時間復雜度應該是?O(n)?。
而雙向鏈表可以在需要查找結點的前驅結點時候，比單鏈表更加高效。
這也是一個重要的設計思想--空間換時間。當內存空間充足的時候，如果追求速度，可以采用一些時間復雜度相對比較低，但空間復雜度相對比較高的算法或者數據結構；當然如果內存空間不足，那就反向考慮，時間換空間的設計思路。
比較經典的例子就是緩存，事先將數據加載在內存中，盡管會比較耗費內存空間，但查找速度就大大提高了。
總結一下，對于執(zhí)行較慢的程序，可以采用空間換時間的思路優(yōu)化；而消耗過多內存的程序，可以通過時間換空間的思路來優(yōu)化。
雙向鏈表還可以和循環(huán)鏈表結合--雙向循環(huán)鏈表，如下圖所示：
鏈表 vs 數組性能大比拼
和數組進行對比，兩者在插入、刪除、隨機訪問操作的時間復雜度是正好相反的，如下表所示：
| 插入&刪除 | O(n) | O(1) |
| 隨機訪問 | O(1) | O(n) |
當然，并不能僅僅通過時間復雜度來對比數組和鏈表，實際應用需要考慮更多的因素。
數組的優(yōu)缺點：
-
優(yōu)點：簡單易用，采用連續(xù)的內存空間，可以借助 CPU 的緩沖機制，預讀數組中的數據，訪問效率更高；
-
缺點：大小固定，一經聲明就需要占用整塊連續(xù)內存空間，占用空間過大和過小都有各自的問題。
而鏈表的優(yōu)缺點其實剛好相反：
-
優(yōu)點：沒有限制大小，天然支持動態(tài)擴容；
-
缺點：占用的內存并不是連續(xù)存儲，對 CPU 緩存不友好，無法有效預讀，訪問效率不高。
鏈表技巧
1. 理解指針或引用的含義
有些語言，比如 C 語言，有指針的概念；但有些語言沒有指針，取而代之的是“引用”的概念，比如 Python。不過，這兩者表示的意思都一樣，都是存儲所指對象的內存地址。
實際上，對于指針或者引用的理解，只需要記住這句話：
將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，也可以說，指針存儲了這個變量的內存地址，指向了這個變量，可以通過指針來找到這個變量。
用代碼舉例說明，比如：p->next= q?，這段代碼表示?p?結點的?next指針指向了?q?結點的內存地址。
更復雜點的例子，p->next=p->next->next?，這段代碼表示?p?結點的?next?指針存儲了?p?結點的下下一個結點的內存地址。
2. 警惕指針丟失和內存泄露
對于鏈表，最重要的是確保指針指向正確的結點，一旦寫錯，就會導致丟失指針，那么這種情況一般是怎么發(fā)生的呢，下面給出一個單鏈表插入操作的例子，如下圖所示：
?
上述例子是希望在結點 a 和 b 之間插入新的結點 x，假設當前指針 p 指向結點 a，如果采用下面的代碼，那么就會發(fā)生指針丟失和內存泄露。
p->next = x; // 將 p 的 next 指針指向 x 結點； x->next = p->next; // 將 x 的結點的 next 指針指向 b 結點；這段代碼是這樣執(zhí)行的：
首先指針 p->next 會指向結點 x；
接著，x->next 執(zhí)行 p->next，也就是說 x->next 指向結點 x，也就是結點 x 自己構成一個閉環(huán)了，那么后續(xù)結點都無法訪問了。
正確的代碼，其實是將上述代碼交換執(zhí)行順序，即先讓 x->next 指向 p->next，也就是結點 b，然后再將 x 賦值給 p->next。
所以，插入結點，需要注意操作的順序；而刪除結點，對于沒有內存管理的編程語言，需要手動釋放內存空間。
3. 利用哨兵簡化實現難度
正常的單鏈表的插入操作，代碼實現如下所示，
new_node->next = p->next p->next = new_node但如果是在鏈表首部插入新的結點，則必須單獨處理：
if head == null: head = new_node同理對于刪除結點操作，代碼如下所示，也就是對鏈表最后一個結點需要特殊處理。
if head->next == null: head = null p->next = p->next->next那么是否有辦法可以不用單獨處理呢，這里就可以采用哨兵，即引入哨兵結點，在任何時候，不管鏈表是否為空，head?指針都會一直指向這個哨兵結點。這種帶有哨兵結點的鏈表叫做帶頭鏈表，沒有帶的則是不帶頭鏈表。如下所示：
4. 重點留意邊界條件處理
通常在邊界或者異常情況下，最容易產生 Bug。對于鏈表，也不例外，在寫代碼過程和寫完后，都需要檢查代碼添加是否考慮全面，以及代碼在邊界條件下能否正常運行。
通常用于檢查鏈表代碼是否正確的邊界條件有這幾個：
-
如果鏈表為空，是否能正常工作？
-
如果鏈表只有一個結點，是否可以正常工作？
-
如果鏈表包含兩個結點，是否可以正常工作？
-
代碼邏輯在處理頭結點和尾結點的時候，是否可以正常工作？
當然，邊界條件并不局限上述這些，不同場景，還有特點的邊界條件。
5. 舉例畫圖，輔助思考
對于復雜的鏈表操作，比如單鏈表反轉，可以采用舉例法和畫圖法進行輔助。
比如，對于鏈表插入的操作，如下圖給出不同情況下，插入前后的鏈表變化：
通過舉例和畫圖，會非常直觀形象的了解應該如何用代碼實現相應的操作。
6. 多寫多練，沒有捷徑
最重要的還是多寫多練，不斷總結錯誤。
參考：
-
極客時間的數據結構與算法之美課程
歡迎關注我的微信公眾號--算法猿的成長，或者掃描下方的二維碼，大家一起交流，學習和進步！
?
?
?
總結
以上是生活随笔為你收集整理的数据结构算法入门--链表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 前端：闭包的概念
- 下一篇： 【经验分享】PC端免费高效的同声翻译