數據結構 – 鏈表
簡介
鏈表是一種和數組不同的線性表結構，數組的存儲使用了一組連續的內存空間，而鏈表通過鏈接的方式將零散的內存空間串聯起來使用。
鏈表的定義需要注意兩點：鏈表仍然是一個線性表結構；鏈表不使用連續的內存空間進行存儲。
因此，鏈表克服了數組需要預先知道數據大小的缺點，並且能充分利用計算機內存空間，實現靈活的內存動態管理。
但鏈表也失去了快速隨機存取的優點，同時由於增加了結點的指針域，空間開銷較大。
基本概念
鏈表是通過指針將零散的內存塊串聯在一起的，這裡的內存塊被稱為鏈表的結點。
結點除了存儲數據之外，還會存儲下一個結點的地址，這個記錄下一個結點地址的指針被稱為後繼指針。在雙向鏈表中，還會存儲上一個結點的地址，這個記錄上一個結點地址的指針被稱為前驅指針。
鏈表中存在兩個比較特殊的結點，分別是第一個結點和最後一個結點。因此也給這兩個結點取了名稱，第一個結點被稱為頭結點，最後一個結點被稱為尾結點。
隨機存儲
把鏈表和數組作比較，數組具有快速隨機存取的優點，而鏈表是隨機存取效率非常低的數據結構。
如果通過下標去訪問鏈表中的結點，是不能使用尋址公式的，只能通過頭結點作為入口，根據指針一個結點一個結點地依次遍歷，直到找到對應的結點。
綜合計算下來，鏈表做隨機訪問的時間複雜度為 \(O(n)\)，效率比數組低得多。
插入、刪除
雖然鏈表沒有了數組隨機存取的優點，但在插入、刪除結點的時候，效率比數組高很多。
假設，要在鏈表中插入一個結點，在知道插入位置的前後兩個相鄰結點的前提下，只需將新結點的後繼指針指向下一個結點，然後將上一個結點的後繼指針指向這個新結點，即可完成插入結點的操作。刪除結點也是類似的操作，非常方便。
但是，插入、刪除結點時效率高的前提是知道操作位置的相鄰結點，否則仍需要從頭結點開始尋找到對應位置，這樣的效率會非常低。
五花八門的鏈表
鏈表有很多不同的類型，在上面說的都是最簡單的單向鏈表，複雜一點的還有雙向鏈表、循環鏈表。
單向鏈表
單向鏈表是最簡單的鏈表結構，它包含兩個域，一個信息域和一個指針域。
信息域存儲實際的數據，指針域存儲此結點的下一個結點位置。
在實際編碼中，為了方便，頭結點的信息域是空的，其指針域存儲實際的第一個結點所在位置，尾結點的指針域一般會是 NULL 地址。
雙向鏈表
雙向鏈表是在單向鏈表的基礎上多增加了一個指針域，這個新增加的指針域會存儲上一個結點所在位置。
也就是說，在雙向鏈表中，除頭結點的任意結點都可以訪問到上一個結點，因此稱為雙向鏈表。
循環鏈表
循環鏈表是一個頭結點和尾結點連接在一起的特殊鏈表，通過單向鏈表或雙向鏈表都能夠實現。
循環鏈表的優點就是從鏈表的尾結點到頭結點非常方便，也方便處理具有環形結構特點的數據，如約瑟夫問題。
使用上的問題
數組和鏈表如何選擇
僅特性和效率而言，數組擁有快速隨機訪問的特性，鏈表可以快速插入、刪除。經常利用下標訪問元素可以使用數組，經常插入、刪除元素可以使用鏈表。
但是，不能僅僅只用複雜度分析決定使用哪種數據結構。數組簡單易用，而且能夠藉助 CPU 緩存機制預讀數組中的數據；而鏈表在內存中不是連續存儲的，對 CPU 緩存不友好，沒辦法有效預讀。
數組的缺點是數據大小固定，而且一經聲明要佔用整塊連續內存空間，如果聲明的數組過大，系統可能沒有足夠的連續內存空間分配給它。即使是在 Java 中使用可以動態擴容的 ArrayList 類型，也存在擴容耗時的問題。而鏈表本身沒有大小的限制，天生支持動態擴容。
實現鏈表的技巧
編寫一個正確的鏈表是比較難的，但是其中也有一些技巧：
- 理解指針或引用的含義。將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者反過來說，指針中存儲了這個變量的內存地址，這個內存地址存儲這個變量，通過指針能找到這個變量
- 警惕指針丟失。插入結點時，先將插入結點的後繼指針指向下一個結點，再把前一個結點的指針指向插入結點，這樣才不會丟失指針
- 避免內存泄漏。刪除結點時，要記得手動釋放內存空間
- 利用哨兵簡化實現難度。在實際開發當中，如果向空鏈表中插入第一個結點的時候，還需要判斷鏈表中是否已經存在頭結點，嵌入代碼比較嚴重；但是，如果增加一個哨兵結點，哨兵結點的後繼指針指向頭結點，則可以省略這一步操作
- 重點留意邊界條件處理。當鏈表為空的時候，代碼是否能正常工作？當鏈表只有一個結點的時候，代碼是否能正常工作等等
- 舉例畫圖，輔助思考。鏈表的指針指向會比較複雜，這種情況可以通過舉例畫圖的辦法將各種情況列舉出來，這樣思路會更加清晰
- 多寫多練，熟能生巧。寫鏈表代碼是非常考驗邏輯思維能力的，多多嘗試練習可以提高邏輯思維能力
