06 | 鏈表（上）：如何實現(xiàn)LRU緩存淘汰算法?
今天我們來聊聊“鏈表（Linked
list）”這個數(shù)據(jù)結(jié)構(gòu)魏保。學(xué)習(xí)鏈表有什么用呢熬尺？為了回答這個問題，我們先來討論一個經(jīng)典的鏈表應(yīng)用場景谓罗，那就是LRU緩存淘汰算法粱哼。
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計檩咱、軟件開發(fā)中都有著非常廣泛的應(yīng)用揭措，比如常見的CPU緩存、數(shù)據(jù)庫緩存刻蚯、瀏覽器緩存等等绊含。
緩存的大小有限，當(dāng)緩存被用滿時炊汹，哪些數(shù)據(jù)應(yīng)該被清理出去躬充，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來決定。常見的策略有三種：先進(jìn)先出策略FIFO（First
In充甚，F(xiàn)irst Out）以政、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently
Used）伴找。
這些策略你不用死記妙蔗，我打個比方你很容易就明白了。假如說疆瑰，你買了很多本技術(shù)書眉反，但有一天你發(fā)現(xiàn)，這些書太多了穆役，太占書房空間了寸五，你要做個大掃除，扔掉一些書籍耿币。那這個時候梳杏，你會選擇扔掉哪些書呢？對應(yīng)一下淹接，你的選擇標(biāo)準(zhǔn)是不是和上面的三種策略神似呢十性？
好了，回到正題塑悼，我們今天的開篇問題就是： 如何用鏈表來實現(xiàn)LRU緩存淘汰策略呢劲适？ 帶著這個問題，我們開始今天的內(nèi)容吧厢蒜！
五花八門的鏈表結(jié)構(gòu)
相比數(shù)組霞势，鏈表是一種稍微復(fù)雜一點的數(shù)據(jù)結(jié)構(gòu)。對于初學(xué)者來說斑鸦，掌握起來也要比數(shù)組稍難一些愕贡。這兩個非常基礎(chǔ)巷屿、非常常用的數(shù)據(jù)結(jié)構(gòu)固以，我們常常將會放到一塊兒來比較。所以我們先來看嘱巾，這兩者有什么區(qū)別憨琳。
我們先從 底層的存儲結(jié)構(gòu) 上來看一看。
為了直觀地對比浓冒，我畫了一張圖栽渴。從圖中我們看到，數(shù)組需要一塊 連續(xù)的內(nèi)存空間
來存儲稳懒，對內(nèi)存的要求比較高闲擦。如果我們申請一個100MB大小的數(shù)組慢味，當(dāng)內(nèi)存中沒有連續(xù)的、足夠大的存儲空間時墅冷，即便內(nèi)存的剩余總可用空間大于100MB纯路，仍然會申請失敗。
而鏈表恰恰相反寞忿，它并不需要一塊連續(xù)的內(nèi)存空間驰唬，它通過“指針”將一組 零散的內(nèi)存塊
串聯(lián)起來使用，所以如果我們申請的是100MB大小的鏈表腔彰，根本不會有問題叫编。
鏈表結(jié)構(gòu)五花八門，今天我重點給你介紹三種最常見的鏈表結(jié)構(gòu)霹抛，它們分別是：單鏈表搓逾、雙向鏈表和循環(huán)鏈表。我們首先來看最簡單杯拐、最常用的 單鏈表 霞篡。
我們剛剛講到，鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起端逼。其中朗兵，我們把內(nèi)存塊稱為鏈表的“ 結(jié)點
”。為了將所有的結(jié)點串起來顶滩，每個鏈表的結(jié)點除了存儲數(shù)據(jù)之外余掖，還需要記錄鏈上的下一個結(jié)點的地址。如圖所示诲祸，我們把這個記錄下個結(jié)點地址的指針叫作
后繼指針next 浊吏。
從我畫的單鏈表圖中，你應(yīng)該可以發(fā)現(xiàn)救氯，其中有兩個結(jié)點是比較特殊的，它們分別是第一個結(jié)點和最后一個結(jié)點歌憨。我們習(xí)慣性地把第一個結(jié)點叫作 頭結(jié)點
着憨，把最后一個結(jié)點叫作 尾結(jié)點
。其中务嫡，頭結(jié)點用來記錄鏈表的基地址甲抖。有了它，我們就可以遍歷得到整條鏈表心铃。而尾結(jié)點特殊的地方是：指針不是指向下一個結(jié)點准谚，而是指向一個 空地址NULL
，表示這是鏈表上最后一個結(jié)點去扣。
與數(shù)組一樣柱衔，鏈表也支持?jǐn)?shù)據(jù)的查找、插入和刪除操作。
我們知道唆铐，在進(jìn)行數(shù)組的插入哲戚、刪除操作時，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性艾岂，需要做大量的數(shù)據(jù)搬移顺少，所以時間復(fù)雜度是O(n)。而在鏈表中插入或者刪除一個數(shù)據(jù)王浴，我們并不需要為了保持內(nèi)存的連續(xù)性而搬移結(jié)點脆炎，因為鏈表的存儲空間本身就不是連續(xù)的。所以氓辣，在鏈表中插入和刪除一個數(shù)據(jù)是非趁朐＃快速的。
為了方便你理解筛婉，我畫了一張圖簇爆，從圖中我們可以看出，針對鏈表的插入和刪除操作爽撒，我們只需要考慮相鄰結(jié)點的指針改變入蛆，所以對應(yīng)的時間復(fù)雜度是O(1)。
但是硕勿，有利就有弊哨毁。鏈表要想隨機(jī)訪問第k個元素，就沒有數(shù)組那么高效了源武。因為鏈表中的數(shù)據(jù)并非連續(xù)存儲的扼褪，所以無法像數(shù)組那樣，根據(jù)首地址和下標(biāo)粱栖，通過尋址公式就能直接計算出對應(yīng)的內(nèi)存地址话浇，而是需要根據(jù)指針一個結(jié)點一個結(jié)點地依次遍歷，直到找到相應(yīng)的結(jié)點闹究。
你可以把鏈表想象成一個隊伍幔崖，隊伍中的每個人都只知道自己后面的人是誰，所以當(dāng)我們希望知道排在第k位的人是誰的時候渣淤，我們就需要從第一個人開始赏寇，一個一個地往下數(shù)。所以价认，鏈表隨機(jī)訪問的性能沒有數(shù)組好嗅定，需要O(n)的時間復(fù)雜度。
好了用踩，單鏈表我們就簡單介紹完了渠退，接著來看另外兩個復(fù)雜的升級版忙迁， 循環(huán)鏈表 和 雙向鏈表 。
循環(huán)鏈表是一種特殊的單鏈表
智什。實際上动漾，循環(huán)鏈表也很簡單。它跟單鏈表唯一的區(qū)別就在尾結(jié)點荠锭。我們知道旱眯，單鏈表的尾結(jié)點指針指向空地址，表示這就是最后的結(jié)點了证九。而循環(huán)鏈表的尾結(jié)點指針是指向鏈表的頭結(jié)點删豺。從我畫的循環(huán)鏈表圖中，你應(yīng)該可以看出來愧怜，它像一個環(huán)一樣首尾相連呀页，所以叫作“循環(huán)”鏈表。
和單鏈表相比拥坛， 循環(huán)鏈表
的優(yōu)點是從鏈尾到鏈頭比較方便蓬蝶。當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點時，就特別適合采用循環(huán)鏈表猜惋。比如著名的約瑟夫問題丸氛。盡管用單鏈表也可以實現(xiàn)，但是用循環(huán)鏈表實現(xiàn)的話著摔，代碼就會簡潔很多缓窜。
單鏈表和循環(huán)鏈表是不是都不難？接下來我們再來看一個稍微復(fù)雜的谍咆，在實際的軟件開發(fā)中禾锤，也更加常用的鏈表結(jié)構(gòu)： 雙向鏈表 。
單向鏈表只有一個方向摹察，結(jié)點只有一個后繼指針next指向后面的結(jié)點恩掷。而雙向鏈表，顧名思義供嚎，它支持兩個方向螃成，每個結(jié)點不止有一個后繼指針next指向后面的結(jié)點，還有一個前驅(qū)指針prev指向前面的結(jié)點查坪。
從我畫的圖中可以看出來，雙向鏈表需要額外的兩個空間來存儲后繼結(jié)點和前驅(qū)結(jié)點的地址宁炫。所以偿曙，如果存儲同樣多的數(shù)據(jù)，雙向鏈表要比單鏈表占用更多的內(nèi)存空間羔巢。雖然兩個指針比較浪費(fèi)存儲空間望忆，但可以支持雙向遍歷罩阵，這樣也帶來了雙向鏈表操作的靈活性。那相比單鏈表启摄，雙向鏈表適合解決哪種問題呢稿壁？
從結(jié)構(gòu)上來看，雙向鏈表可以支持O(1)時間復(fù)雜度的情況下找到前驅(qū)結(jié)點歉备，正是這樣的特點傅是，也使雙向鏈表在某些情況下的插入、刪除等操作都要比單鏈表簡單蕾羊、高效喧笔。
你可能會說，我剛講到單鏈表的插入龟再、刪除操作的時間復(fù)雜度已經(jīng)是O(1)了书闸，雙向鏈表還能再怎么高效呢？別著急利凑，剛剛的分析比較偏理論浆劲，很多數(shù)據(jù)結(jié)構(gòu)和算法書籍中都會這么講，但是這種說法實際上是不準(zhǔn)確的哀澈，或者說是有先決條件的牌借。我再來帶你分析一下鏈表的兩個操作。
我們先來看 刪除操作 日丹。
在實際的軟件開發(fā)中走哺，從鏈表中刪除一個數(shù)據(jù)無外乎這兩種情況：
刪除結(jié)點中“值等于某個給定值”的結(jié)點；
刪除給定指針指向的結(jié)點哲虾。
對于第一種情況丙躏，不管是單鏈表還是雙向鏈表，為了查找到值等于給定值的結(jié)點束凑，都需要從頭結(jié)點開始一個一個依次遍歷對比晒旅，直到找到值等于給定值的結(jié)點，然后再通過我前面講的指針操作將其刪除汪诉。
盡管單純的刪除操作時間復(fù)雜度是O(1)废恋，但遍歷查找的時間是主要的耗時點，對應(yīng)的時間復(fù)雜度為O(n)扒寄。根據(jù)時間復(fù)雜度分析中的加法法則鱼鼓，刪除值等于給定值的結(jié)點對應(yīng)的鏈表操作的總時間復(fù)雜度為O(n)。
對于第二種情況该编，我們已經(jīng)找到了要刪除的結(jié)點迄本，但是刪除某個結(jié)點q需要知道其前驅(qū)結(jié)點，而單鏈表并不支持直接獲取前驅(qū)結(jié)點课竣，所以嘉赎，為了找到前驅(qū)結(jié)點置媳，我們還是要從頭結(jié)點開始遍歷鏈表，直到p->next=q公条，說明p是q的前驅(qū)結(jié)點拇囊。
但是對于雙向鏈表來說，這種情況就比較有優(yōu)勢了靶橱。因為雙向鏈表中的結(jié)點已經(jīng)保存了前驅(qū)結(jié)點的指針寥袭，不需要像單鏈表那樣遍歷。所以抓韩，針對第二種情況纠永，單鏈表刪除操作需要O(n)的時間復(fù)雜度，而雙向鏈表只需要在O(1)的時間復(fù)雜度內(nèi)就搞定了谒拴！
同理尝江，如果我們希望在鏈表的某個指定結(jié)點前面插入一個結(jié)點，雙向鏈表比單鏈表有很大的優(yōu)勢英上。雙向鏈表可以在O(1)時間復(fù)雜度搞定炭序，而單向鏈表需要O(n)的時間復(fù)雜度。你可以參照我剛剛講過的刪除操作自己分析一下苍日。
除了插入惭聂、刪除操作有優(yōu)勢之外，對于一個有序鏈表相恃，雙向鏈表的按值查詢的效率也要比單鏈表高一些辜纲。因為，我們可以記錄上次查找的位置p拦耐，每次查詢時耕腾，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找杀糯，所以平均只需要查找一半的數(shù)據(jù)扫俺。
現(xiàn)在，你有沒有覺得雙向鏈表要比單鏈表更加高效呢固翰？這就是為什么在實際的軟件開發(fā)中狼纬，雙向鏈表盡管比較費(fèi)內(nèi)存，但還是比單鏈表的應(yīng)用更加廣泛的原因骂际。如果你熟悉Java語言疗琉，你肯定用過LinkedHashMap這個容器。如果你深入研究LinkedHashMap的實現(xiàn)原理歉铝，就會發(fā)現(xiàn)其中就用到了雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)没炒。
實際上，這里有一個更加重要的知識點需要你掌握，那就是 用空間換時間
的設(shè)計思想送火。當(dāng)內(nèi)存空間充足的時候，如果我們更加追求代碼的執(zhí)行速度先匪，我們就可以選擇空間復(fù)雜度相對較高种吸、但時間復(fù)雜度相對很低的算法或者數(shù)據(jù)結(jié)構(gòu)。相反呀非，如果內(nèi)存比較緊缺坚俗，比如代碼跑在手機(jī)或者單片機(jī)上，這個時候岸裙，就要反過來用時間換空間的設(shè)計思路猖败。
還是開篇緩存的例子。緩存實際上就是利用了空間換時間的設(shè)計思想降允。如果我們把數(shù)據(jù)存儲在硬盤上恩闻，會比較節(jié)省內(nèi)存，但每次查找數(shù)據(jù)都要詢問一次硬盤剧董，會比較慢幢尚。但如果我們通過緩存技術(shù)，事先將數(shù)據(jù)加載在內(nèi)存中翅楼，雖然會比較耗費(fèi)內(nèi)存空間尉剩，但是每次數(shù)據(jù)查詢的速度就大大提高了。
所以我總結(jié)一下毅臊，對于執(zhí)行較慢的程序理茎，可以通過消耗更多的內(nèi)存（空間換時間）來進(jìn)行優(yōu)化；而消耗過多內(nèi)存的程序管嬉，可以通過消耗更多的時間（時間換空間）來降低內(nèi)存的消耗皂林。你還能想到其他時間換空間或者空間換時間的例子嗎？
了解了循環(huán)鏈表和雙向鏈表宠蚂，如果把這兩種鏈表整合在一起就是一個新的版本： 雙向循環(huán)鏈表
式撼。我想不用我多講，你應(yīng)該知道雙向循環(huán)鏈表長什么樣子了吧求厕？你可以自己試著在紙上畫一畫著隆。
鏈表VS數(shù)組性能大比拼
通過前面內(nèi)容的學(xué)習(xí)，你應(yīng)該已經(jīng)知道呀癣，數(shù)組和鏈表是兩種截然不同的內(nèi)存組織方式美浦。正是因為內(nèi)存存儲的區(qū)別，它們插入项栏、刪除浦辨、隨機(jī)訪問操作的時間復(fù)雜度正好相反。
不過沼沈，數(shù)組和鏈表的對比流酬，并不能局限于時間復(fù)雜度币厕。而且，在實際的軟件開發(fā)中芽腾，不能僅僅利用復(fù)雜度分析就決定使用哪個數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)旦装。
數(shù)組簡單易用，在實現(xiàn)上使用的是連續(xù)的內(nèi)存空間摊滔，可以借助CPU的緩存機(jī)制阴绢，預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高艰躺。而鏈表在內(nèi)存中并不是連續(xù)存儲呻袭，所以對CPU緩存不友好，沒辦法有效預(yù)讀腺兴。
數(shù)組的缺點是大小固定左电，一經(jīng)聲明就要占用整塊連續(xù)內(nèi)存空間。如果聲明的數(shù)組過大含长，系統(tǒng)可能沒有足夠的連續(xù)內(nèi)存空間分配給它券腔，導(dǎo)致“內(nèi)存不足（out of
memory）”。如果聲明的數(shù)組過小拘泞，則可能出現(xiàn)不夠用的情況纷纫。這時只能再申請一個更大的內(nèi)存空間，把原數(shù)組拷貝進(jìn)去陪腌，非常費(fèi)時辱魁。鏈表本身沒有大小的限制，天然地支持動態(tài)擴(kuò)容诗鸭，我覺得這也是它與數(shù)組最大的區(qū)別染簇。
你可能會說，我們Java中的ArrayList容器强岸，也可以支持動態(tài)擴(kuò)容岸凸？我們上一節(jié)課講過蝌箍，當(dāng)我們往支持動態(tài)擴(kuò)容的數(shù)組中插入一個數(shù)據(jù)時青灼，如果數(shù)組中沒有空閑空間了，就會申請一個更大的空間妓盲，將數(shù)據(jù)拷貝過去杂拨，而數(shù)據(jù)拷貝的操作是非常耗時的。
我舉一個稍微極端的例子悯衬。如果我們用ArrayList存儲了了1GB大小的數(shù)據(jù)弹沽，這個時候已經(jīng)沒有空閑空間了，當(dāng)我們再插入數(shù)據(jù)的時候，ArrayList會申請一個1.5GB大小的存儲空間策橘，并且把原來那1GB的數(shù)據(jù)拷貝到新申請的空間上炸渡。聽起來是不是就很耗時？
除此之外役纹，如果你的代碼對內(nèi)存的使用非撑妓ぃ苛刻，那數(shù)組就更適合你促脉。因為鏈表中的每個結(jié)點都需要消耗額外的存儲空間去存儲一份指向下一個結(jié)點的指針，所以內(nèi)存消耗會翻倍策州。而且瘸味，對鏈表進(jìn)行頻繁的插入、刪除操作够挂，還會導(dǎo)致頻繁的內(nèi)存申請和釋放旁仿，容易造成內(nèi)存碎片，如果是Java語言孽糖，就有可能會導(dǎo)致頻繁的GC（Garbage
Collection枯冈，垃圾回收）。
所以办悟，在我們實際的開發(fā)中尘奏，針對不同類型的項目，要根據(jù)具體情況病蛉，權(quán)衡究竟是選擇數(shù)組還是鏈表炫加。
解答開篇
好了，關(guān)于鏈表的知識我們就講完了铺然。我們現(xiàn)在回過頭來看下開篇留給你的思考題俗孝。如何基于鏈表實現(xiàn)LRU緩存淘汰算法？
我的思路是這樣的：我們維護(hù)一個有序單鏈表魄健，越靠近鏈表尾部的結(jié)點是越早之前訪問的赋铝。當(dāng)有一個新的數(shù)據(jù)被訪問時，我們從鏈表頭開始順序遍歷鏈表沽瘦。
1.如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了革骨，我們遍歷得到這個數(shù)據(jù)對應(yīng)的結(jié)點，并將其從原來的位置刪除其垄，然后再插入到鏈表的頭部苛蒲。
2.如果此數(shù)據(jù)沒有在緩存鏈表中，又可以分為兩種情況：
如果此時緩存未滿绿满，則將此結(jié)點直接插入到鏈表的頭部臂外；
如果此時緩存已滿，則鏈表尾結(jié)點刪除，將新的數(shù)據(jù)結(jié)點插入鏈表的頭部漏健。
這樣我們就用鏈表實現(xiàn)了一個LRU緩存嚎货，是不是很簡單？
現(xiàn)在我們來看下m緩存訪問的時間復(fù)雜度是多少蔫浆。因為不管緩存有沒有滿殖属，我們都需要遍歷一遍鏈表，所以這種基于鏈表的實現(xiàn)思路瓦盛，緩存訪問的時間復(fù)雜度為O(n)洗显。
實際上，我們可以繼續(xù)優(yōu)化這個實現(xiàn)思路原环，比如引入 散列表 （Hash
table）來記錄每個數(shù)據(jù)的位置挠唆，將緩存訪問的時間復(fù)雜度降到O(1)。因為要涉及我們還沒有講到的數(shù)據(jù)結(jié)構(gòu)嘱吗，所以這個優(yōu)化方案玄组，我現(xiàn)在就不詳細(xì)說了，等講到散列表的時候谒麦，我會再拿出來講俄讹。
除了基于鏈表的實現(xiàn)思路，實際上還可以用數(shù)組來實現(xiàn)LRU緩存淘汰策略绕德。如何利用數(shù)組實現(xiàn)LRU緩存淘汰策略呢患膛？我把這個問題留給你思考。
內(nèi)容小結(jié)
今天我們講了一種跟數(shù)組“相反”的數(shù)據(jù)結(jié)構(gòu)迁匠，鏈表剩瓶。它跟數(shù)組一樣，也是非吵巧ィ基礎(chǔ)延曙、非常常用的數(shù)據(jù)結(jié)構(gòu)。不過鏈表要比數(shù)組稍微復(fù)雜，從普通的單鏈表衍生出來好幾種鏈表結(jié)構(gòu)，比如雙向鏈表佩厚、循環(huán)鏈表、雙向循環(huán)鏈表趴荸。
和數(shù)組相比宦焦，鏈表更適合插入发钝、刪除操作頻繁的場景顿涣，查詢的時間復(fù)雜度較高。不過酝豪，在具體軟件開發(fā)中涛碑，要對數(shù)組和鏈表的各種性能進(jìn)行對比，綜合來選擇使用兩者中的哪一個孵淘。
如何判斷一個字符串是否是回文字符串的問題蒲障，我想你應(yīng)該聽過，我們今天的題目就是基于這個問題的改造版本瘫证。如果字符串是通過單鏈表來存儲的，那該如何來判斷是一個回文串呢余黎？你有什么好的解決思路呢？相應(yīng)的時間空間復(fù)雜度又是多少呢载萌？
歡迎留言和我分享，我會第一時間給你反饋巡扇。
