一、什么是鏈表？
- 和數(shù)組一樣，鏈表也是一種線性表。
- 從內(nèi)存結(jié)構(gòu)來看，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來，從而進行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)。
- 鏈表中的每一個內(nèi)存塊被稱為節(jié)點Node。節(jié)點除了存儲數(shù)據(jù)外，還需記錄鏈上下一個節(jié)點的地址，即后繼指針next。
二、為什么使用鏈表？即鏈表的特點
- 插入、刪除數(shù)據(jù)效率高O(1)級別（只需更改指針指向即可），隨機訪問效率低O(n)級別（需要從鏈頭至鏈尾進行遍歷）。
- 和數(shù)組相比，內(nèi)存空間消耗更大，因為每個存儲數(shù)據(jù)的節(jié)點都需要額外的空間存儲后繼指針。
三、常用鏈表：單鏈表、循環(huán)鏈表和雙向鏈表
- 單鏈表
- 每個節(jié)點只包含一個指針，即后繼指針。
- 單鏈表有兩個特殊的節(jié)點，即首節(jié)點和尾節(jié)點。為什么特殊？用首節(jié)點地址表示整條鏈表，尾節(jié)點的后繼指針指向空地址null。
-
性能特點：插入和刪除節(jié)點的時間復(fù)雜度為O（1），查找的時間復(fù)雜度為O(n)。
image.png
- 循環(huán)鏈表
- 除了尾節(jié)點的后繼指針指向首節(jié)點的地址外均與單鏈表一致。
-
適用于存儲有循環(huán)特點的數(shù)據(jù)，比如約瑟夫問題。
image.png
- 雙向鏈表
- 節(jié)點除了存儲數(shù)據(jù)外，還有兩個指針分別指向前一個節(jié)點地址（前驅(qū)指針prev）和下一個節(jié)點地址（后繼指針next）。
- 首節(jié)點的前驅(qū)指針prev和尾節(jié)點的后繼指針均指向空地址。
- 性能特點：
和單鏈表相比，存儲相同的數(shù)據(jù)，需要消耗更多的存儲空間。
插入、刪除操作比單鏈表效率更高O(1)級別。
以刪除操作為例，刪除操作分為2種情況：
給定數(shù)據(jù)值刪除對應(yīng)節(jié)點和給定節(jié)點地址刪除節(jié)點；
對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應(yīng)節(jié)點進行刪除，時間復(fù)雜度為O(n)；
對于第二種情況，要進行刪除操作必須找到前驅(qū)節(jié)點，單鏈表需要從頭到尾進行遍歷直到p->next = q，時間復(fù)雜度為O(n)，而雙向鏈表可以直接找到前驅(qū)節(jié)點，時間復(fù)雜度為O(1)。
對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因為我們可以記錄上次查找的位置p，每一次查詢時，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。
-
雙向循環(huán)鏈表：首節(jié)點的前驅(qū)指針指向尾節(jié)點，尾節(jié)點的后繼指針指向首節(jié)點。
image.png
四、選擇數(shù)組還是鏈表？
- 插入、刪除和隨機訪問的時間復(fù)雜度
數(shù)組：插入、刪除的時間復(fù)雜度是O(n)，隨機訪問的時間復(fù)雜度是O(1)。
鏈表：插入、刪除的時間復(fù)雜度是O(1)，隨機訪問的時間復(fù)雜端是O(n)。 - 數(shù)組缺點
- 若申請內(nèi)存空間很大，比如100M，但若內(nèi)存空間沒有100M的連續(xù)空間時，則會申請失敗，盡管內(nèi)存可用空間超過100M。
- 大小固定，若存儲空間不足，需進行擴容，一旦擴容就要進行數(shù)據(jù)復(fù)制，而這時非常費時的。
- 鏈表缺點
- 內(nèi)存空間消耗更大，因為需要額外的空間存儲指針信息。
- 對鏈表進行頻繁的插入和刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。
- 如何選擇？
數(shù)組簡單易用，在實現(xiàn)上使用連續(xù)的內(nèi)存空間，可以借助CPU的緩沖機制預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高，而鏈表在內(nèi)存中并不是連續(xù)存儲，所以對CPU緩存不友好，沒辦法預(yù)讀。
如果代碼對內(nèi)存的使用非常苛刻，那數(shù)組就更適合。
數(shù)組簡單易用，在實現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助 CPU 的緩存機制，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高。而鏈表在內(nèi)存中并不是連續(xù)存儲，所以對 CPU 緩存不友好，沒辦法有效預(yù)讀。
五、應(yīng)用
- 如何分別用鏈表和數(shù)組實現(xiàn)LRU緩沖淘汰策略？
什么是緩存？
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計、軟件開發(fā)中都有著非廣泛的應(yīng)用，比如常見的CPU緩存、數(shù)據(jù)庫緩存、瀏覽器緩存等等。為什么使用緩存？即緩存的特點
緩存的大小是有限的，當(dāng)緩存被用滿時，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？就需要用到緩存淘汰策略。什么是緩存淘汰策略？
指的是當(dāng)緩存被用滿時清理數(shù)據(jù)的優(yōu)先順序。有哪些緩存淘汰策略？
常見的3種包括先進先出策略FIFO（First In，F(xiàn)irst Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。鏈表實現(xiàn)LRU緩存淘汰策略
當(dāng)訪問的數(shù)據(jù)沒有存儲在緩存的鏈表中時，直接將數(shù)據(jù)插入鏈表表頭，時間復(fù)雜度為O(1)；
當(dāng)訪問的數(shù)據(jù)存在于存儲的鏈表中時，將該數(shù)據(jù)對應(yīng)的節(jié)點，插入到鏈表表頭，時間復(fù)雜度為O(n)；
如果緩存被占滿，則從鏈表尾部的數(shù)據(jù)開始清理，時間復(fù)雜度為O(1)。數(shù)組實現(xiàn)LRU緩存淘汰策略
方式一：首位置保存最新訪問數(shù)據(jù)，末尾位置優(yōu)先清理
當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時，直接將數(shù)據(jù)插入數(shù)組第一個元素位置，此時數(shù)組所有元素需要向后移動1個位置，時間復(fù)雜度為O(n)；
當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時，查找到數(shù)據(jù)并將其插入數(shù)組的第一個位置，此時亦需移動數(shù)組元素，時間復(fù)雜度為O(n)；
緩存用滿時，則清理掉末尾的數(shù)據(jù)，時間復(fù)雜度為O(1)。
方式二：首位置優(yōu)先清理，末尾位置保存最新訪問數(shù)據(jù)
當(dāng)訪問的數(shù)據(jù)未存在于緩存的數(shù)組中時，直接將數(shù)據(jù)添加進數(shù)組作為當(dāng)前最有一個元素時間復(fù)雜度為O(1)；當(dāng)訪問的數(shù)據(jù)存在于緩存的數(shù)組中時，查找到數(shù)據(jù)并將其插入當(dāng)前數(shù)組最后一個元素的位置，此時亦需移動數(shù)組元素，時間復(fù)雜度為O(n)；
緩存用滿時，則清理掉數(shù)組首位置的元素，且剩余數(shù)組元素需整體前移一位，時間復(fù)雜度為O(n)。（優(yōu)化：清理的時候可以考慮一次性清理一定數(shù)量，從而降低清理次數(shù)，提高性能。）
- 如何通過單鏈表實現(xiàn)“判斷某個字符串是否為水仙花字符串”？（回文字符串：比如 上海自來水來自海上）
- 前提：字符串以單個字符的形式存儲在單鏈表中。
- 遍歷鏈表，判斷字符個數(shù)是否為奇數(shù)，若為偶數(shù)，則不是。
- 將鏈表中的字符倒序存儲一份在另一個鏈表中。
- 同步遍歷2個鏈表，比較對應(yīng)的字符是否相等，若相等，則是水仙花字串，否則，不是。
六、設(shè)計思想
時空替換思想：“用空間換時間” 與 “用時間換空間”
當(dāng)內(nèi)存空間充足的時候，如果我們更加追求代碼的執(zhí)行速度，我們就可以選擇空間復(fù)雜度相對較高，時間復(fù)雜度小相對較低的算法和數(shù)據(jù)結(jié)構(gòu)，緩存就是空間換時間的例子。如果內(nèi)存比較緊缺，比如代碼跑在手機或者單片機上，這時，就要反過來用時間換空間的思路。
如何優(yōu)雅的寫出鏈表代碼
一、理解指針或引用的含義
- 含義：將某個變量（對象）賦值給指針（引用），實際上就是就是將這個變量（對象）的地址賦值給指針（引用）。
- 示例：
-
p—>next = q;表示p節(jié)點的后繼指針存儲了q節(jié)點的內(nèi)存地址。 -
p—>next = p—>next—>next;表示p節(jié)點的后繼指針存儲了p節(jié)點的下下個節(jié)點的內(nèi)存地址。
二、警惕指針丟失和內(nèi)存泄漏（單鏈表）
-
插入節(jié)點
在節(jié)點a和節(jié)點b之間插入節(jié)點x，b是a的下一節(jié)點，，p指針指向節(jié)點a
image.png
造成指針丟失和內(nèi)存泄漏的代碼：
p—>next = x;
x—>next = p—>next;
顯然這會導(dǎo)致x節(jié)點的后繼指針指向自身。
正確的寫法是2句代碼交換順序，即：
x—>next = p—>next;
p—>next = x;
插入結(jié)點時，一定要注意操作的順序
- 刪除節(jié)點
在節(jié)點a和節(jié)點b之間刪除節(jié)點b，b是a的下一節(jié)點，p指針指向節(jié)點a：p—>next = p—>next—>next;
刪除鏈表結(jié)點時，也一定要記得手動釋放內(nèi)存空間
三、利用“哨兵”簡化實現(xiàn)難度
- 什么是“哨兵”？
鏈表中的“哨兵”節(jié)點是解決邊界問題的，不參與業(yè)務(wù)邏輯。如果我們引入“哨兵”節(jié)點，則不管鏈表是否為空，head指針都會指向這個“哨兵”節(jié)點。我們把這種有“哨兵”節(jié)點的鏈表稱為帶頭鏈表，相反，沒有“哨兵”節(jié)點的鏈表就稱為不帶頭鏈表。 - 未引入“哨兵”的情況
如果在p節(jié)點后插入一個新節(jié)點，只需2行代碼即可搞定：
new_node—>next = p—>next;
p—>next = new_node;
但，若向空鏈表中插入一個節(jié)點，則代碼如下：
if(head == null){
head = new_node;
}
如果要刪除節(jié)點p的后繼節(jié)點，只需1行代碼即可搞定：
p—>next = p—>next—>next;
但，若是刪除鏈表的最后有一個節(jié)點（鏈表中只剩下這個節(jié)點），則代碼如下：
if(head—>next == null){
head = null;
}
從上面的情況可以看出，針對鏈表的插入、刪除操作，需要對插入第一個節(jié)點和刪除最后一個節(jié)點的情況進行特殊處理。這樣代碼就會顯得很繁瑣，所以引入“哨兵”節(jié)點來解決這個問題。
-
引入“哨兵”的情況
“哨兵”節(jié)點不存儲數(shù)據(jù)，無論鏈表是否為空，head指針都會指向它，作為鏈表的頭結(jié)點始終存在。這樣，插入第一個節(jié)點和插入其他節(jié)點，刪除最后一個節(jié)點和刪除其他節(jié)點都可以統(tǒng)一為相同的代碼實現(xiàn)邏輯了。
image.png - “哨兵”還有哪些應(yīng)用場景？
比如插入排序、歸并排序、動態(tài)規(guī)劃等。
四、重點留意邊界條件處理
經(jīng)常用來檢查鏈表是否正確的邊界4個邊界條件：
- 如果鏈表為空時，代碼是否能正常工作？
- 如果鏈表只包含一個節(jié)點時，代碼是否能正常工作？
- 如果鏈表只包含兩個節(jié)點時，代碼是否能正常工作？
- 代碼邏輯在處理頭尾節(jié)點時是否能正常工作？
五、舉例畫圖，輔助思考
核心思想：釋放腦容量，留更多的給邏輯思考，這樣就會感覺到思路清晰很多。
鏈表練習(xí)題：
- 鏈表的種類以及他們的特點、優(yōu)勢、應(yīng)用場景
- 鏈表和數(shù)組的比較
- 鏈表的插入、刪除等操作；以及加入哨兵節(jié)點之后的插入、刪除等操作
- 回文字符串
https://github.com/andavid/leetcode-java/blob/master/note/234/README.md - LRU緩存實現(xiàn)
- 單鏈表反轉(zhuǎn)（leetCode：206）
- 鏈表中環(huán)的檢測（leetCode：141）
- 兩個有序鏈表合并（leetCode：21）
- 刪除鏈表倒數(shù)第n個節(jié)點（leetCode：19）
- 求鏈表的中間節(jié)點（leetCode：876）
- 約瑟夫環(huán)問題
- 單鏈表的歸并排序
