前言

我們通常會(huì)去想缎除，學(xué)習(xí)鏈表有啥用呢？其實(shí)鏈表在實(shí)際的開發(fā)中應(yīng)用非常廣泛，比如經(jīng)典的 LRU 緩存淘汰算法亩进，比如Objective-c 中的 autoreleasepool 底層實(shí)現(xiàn)，包括常用的 hash缩歪、圖等等均用到了鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)归薛？
那你可能還會(huì)問(wèn)，有數(shù)組了為啥還要用鏈表匪蝙？下面我將著重圍繞這幾個(gè)問(wèn)題進(jìn)行分析主籍。

鏈表是什么

數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)，對(duì)內(nèi)存的要求比較高逛球。如果我們申請(qǐng)一個(gè) 100MB 大小的數(shù)組千元，當(dāng)內(nè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ǎn)捂湵怼㈦p向鏈表和循環(huán)鏈表

鏈表的數(shù)據(jù)結(jié)構(gòu)

• 單鏈表
  單向鏈表的節(jié)點(diǎn)通常由兩個(gè)部分構(gòu)成溢谤，一個(gè)是節(jié)點(diǎn)儲(chǔ)存的值val,另一個(gè)就是節(jié)點(diǎn)的指針next瞻凤。

• 雙向鏈表
  單向鏈表只有一個(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)。
  雙向鏈表的缺點(diǎn)就是比單向鏈表占用更多的內(nèi)存空間所刀，我們從后面也可以知道單鏈表的刪除和插入的時(shí)間復(fù)雜度是 O(1)的衙荐，但是實(shí)際的應(yīng)用場(chǎng)景確是要遍歷得到結(jié)點(diǎn)，才能刪除浮创，所以依舊需要先查詢忧吟，單向鏈表則是要從頭開始查詢，耗費(fèi)時(shí)間資源斩披，而雙向鏈表卻可以選擇從雙向進(jìn)行遍歷溜族，這樣找到尾節(jié)點(diǎn)的時(shí)間復(fù)雜度就是O(1)讹俊，雙向鏈表比單向鏈表更加靈活

• 循壞鏈表
  循環(huán)鏈表是一種特殊的單鏈表。實(shí)際上煌抒，循環(huán)鏈表也很簡(jiǎn)單仍劈。它跟單鏈表唯一的區(qū)別就在尾結(jié)點(diǎn)。我們知道寡壮，單鏈表的尾結(jié)點(diǎn)指針指向空地址贩疙，表示這就是最后的結(jié)點(diǎn)了。而循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)况既。它像一個(gè)環(huán)一樣首尾相連这溅，所以叫作“循環(huán)”鏈表。

鏈表和數(shù)組一樣坏挠，都支持查詢芍躏、刪除、插入操作

鏈表的查詢

單向鏈表的查找操作通常是這樣的:
從頭節(jié)點(diǎn)進(jìn)入,開始比對(duì)節(jié)點(diǎn)的值,如果不同則通過(guò)指針進(jìn)入下一個(gè)節(jié)點(diǎn)
重復(fù)上面的動(dòng)作,直到找到相同的值,或者節(jié)點(diǎn)的指針指向null
鏈表的查找性能與數(shù)組一樣降狠，都是時(shí)間復(fù)雜度為O(n)对竣。
注：數(shù)組查找特定位置的時(shí)間復(fù)雜度是O(n)

鏈表的插入和刪除

鏈表與數(shù)組最大的不同就在于刪除、插入的性能優(yōu)勢(shì),由于鏈表是非連續(xù)的內(nèi)存,所以不用像數(shù)組一樣在插入榜配、刪除操作的時(shí)候需要進(jìn)行大面積的成員位移,比如在a否纬、b節(jié)點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)c,鏈表只需要:

• a斷開指向b的指針，將指針指向c
• c節(jié)點(diǎn)將指針指向b蛋褥，完畢
  這個(gè)插入操作僅僅需要移動(dòng)一下指針即可临燃，插入、刪除的時(shí)間復(fù)雜度只有O(1).

用鏈表如何實(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ù)沒有在緩存鏈表中丹喻，又可以分為兩種情況：如果此時(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)椴还芫彺嬗袥]有滿贼涩，我們都需要遍歷一遍鏈表巧涧，所以這種基于鏈表的實(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)缩筛。
“數(shù)組簡(jiǎn)單易用，在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間堡称，可以借助 CPU 的緩存機(jī)制瞎抛，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問(wèn)效率更高却紧。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)桐臊，所以對(duì) CPU 緩存不友好，沒辦法有效預(yù)讀晓殊《闲祝” 這里的CPU緩存機(jī)制指的是什么？為什么就數(shù)組更好了巫俺？

LRU 淘汰算法的實(shí)現(xiàn)來(lái)源于王錚老師的數(shù)據(jù)結(jié)構(gòu)與算法之美專欄

總結(jié)

CPU在從內(nèi)存讀取數(shù)據(jù)的時(shí)候认烁，會(huì)先把讀取到的數(shù)據(jù)加載到CPU的緩存中。而CPU每次從內(nèi)存讀取數(shù)據(jù)并不是只讀取那個(gè)特定要訪問(wèn)的地址介汹，而是讀取一個(gè)數(shù)據(jù)塊(這個(gè)大小我不太確定）却嗡。并保存到CPU緩存中，然后下次訪問(wèn)內(nèi)存數(shù)據(jù)的時(shí)候就會(huì)先從CPU緩存開始查找嘹承，如果找到就不需要再?gòu)膬?nèi)存中取窗价。這樣就實(shí)現(xiàn)了比內(nèi)存訪問(wèn)速度更快的機(jī)制，也就是CPU緩存存在的意義:為了彌補(bǔ)內(nèi)存訪問(wèn)速度過(guò)慢與CPU執(zhí)行速度快之間的差異而引入赶撰。

對(duì)于數(shù)組來(lái)說(shuō)舌镶，存儲(chǔ)空間是連續(xù)的，所以在加載某個(gè)下標(biāo)的時(shí)候可以把以后的幾個(gè)下標(biāo)元素也加載到CPU緩存這樣執(zhí)行速度會(huì)快于存儲(chǔ)空間不連續(xù)的鏈表存儲(chǔ)豪娜。