經(jīng)典的鏈表應(yīng)用場(chǎng)景耿焊，那就是 LRU 緩存淘汰算法
常見的緩存淘汰策略：
- 先進(jìn)先出策略 FIFO（First In茶鉴，F(xiàn)irst Out）
- 最少使用策略 LFU（Least Frequently Used）
- 最近最少使用策略 LRU（Least Recently Used）
這些策略你不用死記枕磁，我打個(gè)比方你很容易就明白了。假如說(shuō)，你買了很多本技術(shù)書热某，但有一天你發(fā)現(xiàn)，這些書太多了，太占書房空間了昔馋，你要做個(gè)大掃除筹吐，扔掉一些書籍。那這個(gè)時(shí)候秘遏，你會(huì)選擇扔掉哪些書呢丘薛？對(duì)應(yīng)一下，你的選擇標(biāo)準(zhǔn)是不是和上面的三種策略神似呢邦危？
五花八門的鏈表結(jié)構(gòu)
從底層的存儲(chǔ)結(jié)構(gòu)看
數(shù)組
數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)榔袋，對(duì)內(nèi)存的要求比較高。如果我們申請(qǐng)一個(gè) 100MB 大小的數(shù)組铡俐，當(dāng)內(nèi)存中沒(méi)有連續(xù)的凰兑、足夠大的存儲(chǔ)空間時(shí)，即便內(nèi)存的剩余總可用空間大于 100MB审丘，仍然會(huì)申請(qǐng)失敗吏够。
鏈表
鏈表并不需要一塊連續(xù)的內(nèi)存空間，它通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用滩报，所以如果我們申請(qǐng)的是 100MB 大小的鏈表锅知，根本不會(huì)有問(wèn)題。
三種最常見的鏈表結(jié)構(gòu)
- 單鏈表
- 雙向鏈表
- 循環(huán)鏈表
單鏈表
鏈表通過(guò)指針將一組零散的內(nèi)存塊串聯(lián)在一起脓钾。其中售睹，我們把內(nèi)存塊稱為鏈表的“結(jié)點(diǎn)”。為了將所有的結(jié)點(diǎn)串起來(lái)可训，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外昌妹，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)的地址。如圖所示握截，我們把這個(gè)記錄下個(gè)結(jié)點(diǎn)地址的指針叫作后繼指針 next飞崖。
從單鏈表圖中，你應(yīng)該可以發(fā)現(xiàn)谨胞，其中有兩個(gè)結(jié)點(diǎn)是比較特殊的固歪，它們分別是第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。我們習(xí)慣性地把第一個(gè)結(jié)點(diǎn)叫作頭結(jié)點(diǎn)胯努，把最后一個(gè)結(jié)點(diǎn)叫作尾結(jié)點(diǎn)牢裳。其中，頭結(jié)點(diǎn)用來(lái)記錄鏈表的基地址叶沛。有了它蒲讯，我們就可以遍歷得到整條鏈表。而尾結(jié)點(diǎn)特殊的地方是：指針不是指向下一個(gè)結(jié)點(diǎn)恬汁，而是指向一個(gè)空地址 NULL伶椿，表示這是鏈表上最后一個(gè)結(jié)點(diǎn)辜伟。
插入和刪除：
- 數(shù)組：插入和刪除時(shí)，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性脊另，需要做大量的數(shù)據(jù)搬移导狡，時(shí)間復(fù)雜度為O(n)。
- 鏈表：鏈表的插入和刪除操作偎痛，我們只需要考慮相鄰節(jié)點(diǎn)的指針改變旱捧，時(shí)間復(fù)雜度為O(1)。
查找：
- 鏈表中的數(shù)據(jù)并非連續(xù)存儲(chǔ)的踩麦，所以無(wú)法像數(shù)組那樣枚赡，根據(jù)首地址和下標(biāo)，通過(guò)尋址公式就能直接計(jì)算出對(duì)應(yīng)的內(nèi)存地址谓谦，而是需要根據(jù)指針一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)地依次遍歷贫橙，直到找到相應(yīng)的結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)反粥。
循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表卢肃。
與單鏈表唯一的區(qū)別在尾節(jié)點(diǎn)：
- 單鏈表的尾節(jié)點(diǎn)指針指向空指針，表示這是最后的節(jié)點(diǎn)才顿。
- 循環(huán)鏈表的尾節(jié)點(diǎn)指針指向鏈表的頭結(jié)點(diǎn)莫湘，
與單鏈表比優(yōu)點(diǎn)：從鏈尾到鏈頭比較方便。
雙向鏈表
單鏈表只有一個(gè)方向郑气，節(jié)點(diǎn)只有一個(gè)后繼指針 next 指向后面的節(jié)點(diǎn)幅垮。
而雙向鏈表，它支持兩個(gè)方向尾组，每個(gè)節(jié)點(diǎn)不止有一個(gè)后繼指針 next 指向后面的節(jié)點(diǎn)忙芒，還有一個(gè)前驅(qū)指針 prev 指向前面的節(jié)點(diǎn)。(LinkedHashMap)
從圖中可以看出來(lái)演怎，雙向鏈表需要額外的兩個(gè)空間來(lái)存儲(chǔ)前繼節(jié)點(diǎn)和前驅(qū)節(jié)點(diǎn)的地址匕争。所以，如果存儲(chǔ)同樣多的數(shù)據(jù)爷耀，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。
雖然兩個(gè)指針比較浪費(fèi)存儲(chǔ)空間拍皮，但可以支持雙向遍歷歹叮，這樣也帶來(lái)了雙向鏈表操作的靈活性。
從結(jié)構(gòu)上來(lái)看铆帽，雙向鏈表可以支持 O(1) 時(shí)間復(fù)雜度的情況下找到前驅(qū)結(jié)點(diǎn)咆耿，正是這樣的特點(diǎn)，也使雙向鏈表在某些情況下的插入爹橱、刪除等操作都要比單鏈表簡(jiǎn)單萨螺、高效。
刪除操作
在實(shí)際的軟件開發(fā)中，從鏈表中刪除一個(gè)數(shù)據(jù)無(wú)外乎這兩種情況：
- 1.刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)慰技；
- 2.刪除給定指針指向的結(jié)點(diǎn)椭盏。
1. 刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)
不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點(diǎn)吻商，都需要從頭結(jié)點(diǎn)開始一個(gè)一個(gè)依次遍歷對(duì)比掏颊，直到找到值等于給定值的結(jié)點(diǎn)，然后再通過(guò)我前面講的指針操作將其刪除艾帐。
盡管單純的刪除操作時(shí)間復(fù)雜度是 O(1)乌叶，但遍歷查找的時(shí)間是主要的耗時(shí)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為 O(n)柒爸。根據(jù)時(shí)間復(fù)雜度分析中的加法法則准浴，刪除值等于給定值的結(jié)點(diǎn)對(duì)應(yīng)的鏈表操作的總時(shí)間復(fù)雜度為 O(n)。
2.刪除給定指針指向的結(jié)點(diǎn)
我們已經(jīng)找到了要?jiǎng)h除的結(jié)點(diǎn)捎稚，但是刪除某個(gè)結(jié)點(diǎn) q 需要知道其前驅(qū)結(jié)點(diǎn)兄裂，而單鏈表并不支持直接獲取前驅(qū)結(jié)點(diǎn)，所以阳藻，為了找到前驅(qū)結(jié)點(diǎn)晰奖，我們還是要從頭結(jié)點(diǎn)開始遍歷鏈表，直到 p->next=q腥泥，說(shuō)明 p 是 q 的前驅(qū)結(jié)點(diǎn)匾南。
雙向鏈表這種情況比較有優(yōu)勢(shì)。因?yàn)殡p向鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針蛔外，不需要像單鏈表那樣遍歷蛆楞。所以，針對(duì)第二種情況夹厌，單鏈表刪除操作需要 O(n) 的時(shí)間復(fù)雜度豹爹，而雙向鏈表只需要在 O(1) 的時(shí)間復(fù)雜度內(nèi)就搞定了！
如果我們希望在鏈表的某個(gè)指定結(jié)點(diǎn)前面插入一個(gè)結(jié)點(diǎn)矛纹，雙向鏈表比單鏈表有很大的優(yōu)勢(shì)臂聋。雙向鏈表可以在 O(1) 時(shí)間復(fù)雜度搞定，而單向鏈表需要 O(n) 的時(shí)間復(fù)雜度或南。
查詢：
除了插入孩等、刪除操作有優(yōu)勢(shì)之外，對(duì)于一個(gè)有序鏈表采够，雙向鏈表的按值查詢的效率也要比單鏈表高一些肄方。因?yàn)椋覀兛梢杂涗浬洗尾檎业奈恢?p蹬癌，每次查詢時(shí)权她，根據(jù)要查找的值與 p 的大小關(guān)系虹茶，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)隅要。
- 對(duì)于執(zhí)行較慢的程序蝴罪，可以通過(guò)消耗更多的內(nèi)存（空間換時(shí)間）來(lái)進(jìn)行優(yōu)化；
- 而消耗過(guò)多內(nèi)存的程序拾徙，可以通過(guò)消耗更多的時(shí)間（時(shí)間換空間）來(lái)降低內(nèi)存的消耗洲炊。
雙向循環(huán)鏈表
鏈表 VS 數(shù)組性能大比拼
數(shù)組和鏈表是兩種截然不同的內(nèi)存組織方式。正是因?yàn)閮?nèi)存存儲(chǔ)的區(qū)別尼啡，它們插入暂衡、刪除、隨機(jī)訪問(wèn)操作的時(shí)間復(fù)雜度正好相反崖瞭。
| 時(shí)間復(fù)雜度 | 數(shù)組 | 鏈表 |
|---|---|---|
| 插入刪除 | O(n) | O(1) |
| 隨機(jī)訪問(wèn) | O(1) | O(n) |
- 數(shù)組簡(jiǎn)單易用狂巢，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，可以借助CPU的緩存機(jī)制书聚，預(yù)讀數(shù)組中的數(shù)據(jù)唧领，所以訪問(wèn)效率更高。
- 鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)雌续，所以對(duì)CPU緩存不友好斩个，沒(méi)辦法有效預(yù)讀。
- 數(shù)組的缺點(diǎn)是大小固定驯杜，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間受啥。如果聲明的數(shù)組過(guò)大，系統(tǒng)可能沒(méi)有足夠的連續(xù)內(nèi)存空間分配給它鸽心，導(dǎo)致“內(nèi)存不足（out of memory）”滚局。如果聲明的數(shù)組過(guò)小，則可能出現(xiàn)不夠用的情況顽频。這時(shí)只能再申請(qǐng)一個(gè)更大的內(nèi)存空間藤肢，把原數(shù)組拷貝進(jìn)去，非常費(fèi)時(shí)糯景。
- 鏈表本身沒(méi)有大小的限制嘁圈，天然地支持動(dòng)態(tài)擴(kuò)容，這也是它與數(shù)組最大的區(qū)別莺奸。
你可能會(huì)說(shuō)丑孩，我們 Java 中的 ArrayList 容器，也可以支持動(dòng)態(tài)擴(kuò)容懊鸫？我們上一節(jié)課講過(guò)略贮，當(dāng)我們往支持動(dòng)態(tài)擴(kuò)容的數(shù)組中插入一個(gè)數(shù)據(jù)時(shí)甚疟，如果數(shù)組中沒(méi)有空閑空間了仗岖，就會(huì)申請(qǐng)一個(gè)更大的空間，將數(shù)據(jù)拷貝過(guò)去览妖，而數(shù)據(jù)拷貝的操作是非常耗時(shí)的轧拄。
我舉一個(gè)稍微極端的例子。如果我們用 ArrayList 存儲(chǔ)了了 1GB 大小的數(shù)據(jù)讽膏，這個(gè)時(shí)候已經(jīng)沒(méi)有空閑空間了檩电，當(dāng)我們?cè)俨迦霐?shù)據(jù)的時(shí)候，ArrayList 會(huì)申請(qǐng)一個(gè) 1.5GB 大小的存儲(chǔ)空間府树，并且把原來(lái)那 1GB 的數(shù)據(jù)拷貝到新申請(qǐng)的空間上俐末。聽起來(lái)是不是就很耗時(shí)趴泌？
除此之外着撩，如果你的代碼對(duì)內(nèi)存的使用非惩ぃ苛刻馏鹤，那數(shù)組就更適合你币励。因?yàn)殒湵碇械拿總€(gè)結(jié)點(diǎn)都需要消耗額外的存儲(chǔ)空間去存儲(chǔ)一份指向下一個(gè)結(jié)點(diǎn)的指針梧奢，所以內(nèi)存消耗會(huì)翻倍棘催。而且倦西，對(duì)鏈表進(jìn)行頻繁的插入弯洗、刪除操作旅急，還會(huì)導(dǎo)致頻繁的內(nèi)存申請(qǐng)和釋放，容易造成內(nèi)存碎片牡整，如果是 Java 語(yǔ)言藐吮，就有可能會(huì)導(dǎo)致頻繁的 GC（Garbage Collection，垃圾回收）果正。
所以炎码，在我們實(shí)際的開發(fā)中，針對(duì)不同類型的項(xiàng)目秋泳，要根據(jù)具體情況潦闲，權(quán)衡究竟是選擇數(shù)組還是鏈表。
如何基于鏈表實(shí)現(xiàn) LRU 緩存淘汰算法迫皱？
我的思路是這樣的：我們維護(hù)一個(gè)有序單鏈表歉闰，越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪問(wèn)的。當(dāng)有一個(gè)新的數(shù)據(jù)被訪問(wèn)時(shí)卓起，我們從鏈表頭開始順序遍歷鏈表和敬。
如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個(gè)數(shù)據(jù)對(duì)應(yīng)的結(jié)點(diǎn)戏阅，并將其從原來(lái)的位置刪除昼弟，然后再插入到鏈表的頭部。
如果此數(shù)據(jù)沒(méi)有在緩存鏈表中奕筐，又可以分為兩種情況：
- 如果此時(shí)緩存未滿舱痘，則將此結(jié)點(diǎn)直接插入到鏈表的頭部变骡；
- 如果此時(shí)緩存已滿，則鏈表尾結(jié)點(diǎn)刪除芭逝，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部塌碌。
這樣我們就用鏈表實(shí)現(xiàn)了一個(gè) LRU 緩存，是不是很簡(jiǎn)單旬盯？
現(xiàn)在我們來(lái)看下 m 緩存訪問(wèn)的時(shí)間復(fù)雜度是多少台妆。因?yàn)椴还芫彺嬗袥](méi)有滿，我們都需要遍歷一遍鏈表胖翰，所以這種基于鏈表的實(shí)現(xiàn)思路接剩，緩存訪問(wèn)的時(shí)間復(fù)雜度為 O(n)。
實(shí)際上泡态，我們可以繼續(xù)優(yōu)化這個(gè)實(shí)現(xiàn)思路搂漠，比如引入散列表（Hash table）來(lái)記錄每個(gè)數(shù)據(jù)的位置，將緩存訪問(wèn)的時(shí)間復(fù)雜度降到 O(1)某弦。因?yàn)橐婕拔覀冞€沒(méi)有講到的數(shù)據(jù)結(jié)構(gòu)桐汤，所以這個(gè)優(yōu)化方案，我現(xiàn)在就不詳細(xì)說(shuō)了靶壮，等講到散列表的時(shí)候怔毛，我會(huì)再拿出來(lái)講。
個(gè)人總結(jié)
- 數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)腾降。
- 鏈表是通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)起來(lái)使用拣度。
單鏈表的第一個(gè)結(jié)點(diǎn)叫頭結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)叫作尾結(jié)點(diǎn)螃壤，尾結(jié)點(diǎn)指向一個(gè)空指針NULL抗果。插入和刪除的時(shí)間復(fù)雜度為O(1)，查找的時(shí)間復(fù)雜度為O(n)奸晴。
循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)指向鏈表頭結(jié)點(diǎn)冤馏，適合處理環(huán)形數(shù)據(jù)結(jié)構(gòu)。
雙向鏈表不止有一個(gè)后繼指針 next 還有一個(gè)前驅(qū)指針 prev 寄啼，同樣的數(shù)據(jù)雙向鏈表比單鏈表占更多的內(nèi)存空間逮光。
刪除給定的結(jié)點(diǎn)，雙向鏈表時(shí)間復(fù)雜度為O(1)墩划，單鏈表的時(shí)間復(fù)雜度為O(n)涕刚。
ArrayList：支持動(dòng)態(tài)擴(kuò)容的數(shù)組，但當(dāng)沒(méi)有空閑空間了乙帮，就會(huì)申請(qǐng)一個(gè)更大的空間杜漠，將數(shù)據(jù)拷貝過(guò)去，而數(shù)據(jù)拷貝是非常耗時(shí)的。
