一团赏、什么是鏈表？

和數(shù)組一樣耐薯，鏈表也是一種線性表舔清。
從內(nèi)存結(jié)構(gòu)來看，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間曲初，是將一組零散的內(nèi)存塊串聯(lián)起來体谒，從而進(jìn)行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)。
鏈表中的每一個內(nèi)存塊被稱為節(jié)點Node臼婆。節(jié)點除了存儲數(shù)據(jù)外营密，還需記錄鏈上下一個節(jié)點的地址，即后繼指針next目锭。

二评汰、為什么使用鏈表？即鏈表的特點

插入痢虹、刪除數(shù)據(jù)效率高O(1)級別（只需更改指針指向即可）被去，隨機(jī)訪問效率低O(n)級別（需要從鏈頭至鏈尾進(jì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é)點会烙；
對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進(jìn)行遍歷從而找到對應(yīng)節(jié)點進(jìn)行刪除筒捺，時間復(fù)雜度為O(n)柏腻；
對于第二種情況，要進(jìn)行刪除操作必須找到前驅(qū)節(jié)點系吭，單鏈表需要從頭到尾進(jìn)行遍歷直到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ù)組還是鏈表啥箭？

插入谍珊、刪除和隨機(jī)訪問的時間復(fù)雜度
數(shù)組：插入、刪除的時間復(fù)雜度是O(n)捉蚤，隨機(jī)訪問的時間復(fù)雜度是O(1)抬驴。
鏈表：插入、刪除的時間復(fù)雜度是O(1)缆巧，隨機(jī)訪問的時間復(fù)雜端是O(n)。
數(shù)組缺點

若申請內(nèi)存空間很大豌拙，比如100M陕悬，但若內(nèi)存空間沒有100M的連續(xù)空間時，則會申請失敗按傅，盡管內(nèi)存可用空間超過100M捉超。
大小固定胧卤，若存儲空間不足，需進(jìn)行擴(kuò)容拼岳，一旦擴(kuò)容就要進(jìn)行數(shù)據(jù)復(fù)制枝誊，而這時非常費時的。

鏈表缺點

內(nèi)存空間消耗更大惜纸，因為需要額外的空間存儲指針信息叶撒。
對鏈表進(jìn)行頻繁的插入和刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放耐版，容易造成內(nèi)存碎片祠够，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作粪牲。

如何選擇古瓤？
數(shù)組簡單易用，在實現(xiàn)上使用連續(xù)的內(nèi)存空間腺阳，可以借助CPU的緩沖機(jī)制預(yù)讀數(shù)組中的數(shù)據(jù)落君，所以訪問效率更高，而鏈表在內(nèi)存中并不是連續(xù)存儲亭引，所以對CPU緩存不友好叽奥，沒辦法預(yù)讀。
如果代碼對內(nèi)存的使用非惩词蹋苛刻朝氓，那數(shù)組就更適合。

數(shù)組簡單易用主届，在實現(xiàn)上使用的是連續(xù)的內(nèi)存空間赵哲，可以借助 CPU 的緩存機(jī)制，預(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種包括先進(jìn)先出策略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ù)添加進(jìn)數(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)存比較緊缺缸夹，比如代碼跑在手機(jī)或者單片機(jī)上痪寻，這時，就要反過來用時間換空間的思路虽惭。

如何優(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é)點的情況進(jìn)行特殊處理弄兜。這樣代碼就會顯得很繁瑣，所以引入“哨兵”節(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)問題
單鏈表的歸并排序