前幾節(jié)學(xué)習(xí)了「鏈表」鹉动、「時間與空間復(fù)雜度」的概念，本節(jié)將結(jié)合「循環(huán)鏈表」缸血、「雙向鏈表」與 「用空間換時間的設(shè)計(jì)思想」來設(shè)計(jì)一個很有意思的緩存淘汰策略：LRU緩存淘汰算法械筛。
循環(huán)鏈表的概念
如上圖所示：單鏈表的尾結(jié)點(diǎn)指針指向空地址，表示這就是最后的結(jié)點(diǎn)了埋哟。而循環(huán)鏈表的尾結(jié)點(diǎn)指針是指向鏈表的頭結(jié)點(diǎn)。
因此循環(huán)鏈表是一種特殊的單鏈表闯狱。它跟單鏈表唯一的區(qū)別就在于尾結(jié)點(diǎn)抛计。它像一個環(huán)一樣首尾相連，所以叫作「循環(huán)鏈表」吹截。
循環(huán)鏈表的特點(diǎn)
和單鏈表相比，循環(huán)鏈表的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便波俄，當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點(diǎn)時，適合采用循環(huán)鏈表捉貌。
雙向鏈表概念
雙向鏈表也叫雙鏈表，是鏈表的一種昏翰，它的鏈接方向是雙向的苍匆，它的每個數(shù)據(jù)結(jié)點(diǎn)中都包含有兩個指針棚菊，分別指向直接后繼和直接前驅(qū)。
所以检碗，從雙向鏈表中的任意一個結(jié)點(diǎn)開始码邻，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。
雙向鏈表的數(shù)據(jù)結(jié)構(gòu)中像屋，會有兩個比較重要的參數(shù)： pre 和 next 。
-
pre指向前一個數(shù)據(jù)結(jié)構(gòu) -
next指向下一個數(shù)據(jù)結(jié)構(gòu)
雙向鏈表的特點(diǎn)
與單鏈表對比奏甫，雙鏈表需要多一個指針用于指向前驅(qū)節(jié)點(diǎn)凌受，因此如果存儲同樣多的數(shù)據(jù)，雙向鏈表要比單鏈表占用更多的內(nèi)存空間
雙鏈表的插入和刪除需要同時維護(hù) next 和 prev 兩個指針胜蛉。
雙鏈表中的元素訪問需要通過順序訪問，支持雙向遍歷誊册，這就是雙向鏈表操作的靈活性根本
雙向鏈表的基本操作
1.添加元素。
與單向鏈表相對比雙向鏈表可以在 O(1) 時間復(fù)雜度搞定君旦，而單向鏈表需要 O(n) 的時間復(fù)雜度殴泰。
雙向鏈表的添加元素包括頭插法和尾插法浮驳。
頭插法：將鏈表的左邊稱為鏈表頭部，右邊稱為鏈表尾部至会。頭插法是將右邊固定，每次新增的元素都在左邊頭部增加宵蛀。
尾插法：將鏈表的左邊稱為鏈表頭部昆著，右邊稱為鏈表尾部术陶。尾插法是將左邊固定，每次新增都在鏈表的右邊最尾部接谨。
2.查詢元素
雙向鏈表的靈活處就是知道鏈表中的一個元素結(jié)構(gòu)就可以向左或者向右開始遍歷查找需要的元素結(jié)構(gòu)塘匣。因此對于一個有序鏈表，雙向鏈表的按值查詢的效率比單鏈表高一些忌卤。因?yàn)椋覀兛梢杂涗浬洗尾檎业奈恢?p笤闯，每次查詢時辣垒，根據(jù)要查找的值與 p 的大小關(guān)系，決定是往前還是往后查找勋桶，所以平均只需要查找一半的數(shù)據(jù)。
3.刪除元素
在實(shí)際的軟件開發(fā)中例驹，從鏈表中刪除一個數(shù)據(jù)無外乎這兩種情況：
刪除結(jié)點(diǎn)中“值等于某個給定值”的結(jié)點(diǎn)
刪除給定指針指向的結(jié)點(diǎn)
對于雙向鏈表來說鹃锈，雙向鏈表中的結(jié)點(diǎn)已經(jīng)保存了前驅(qū)結(jié)點(diǎn)的指針，刪除時不需要像單鏈表那樣遍歷屎债。所以，針對第二種情況盆驹，單鏈表刪除操作需要 O(n) 的時間復(fù)雜度，而雙向鏈表只需要在 O(1) 的時間復(fù)雜度辫封。
雙向循環(huán)鏈表
如圖所示，雙向循環(huán)鏈表的概念很好理解：「雙向鏈表」 + 「循環(huán)鏈表」的組合倦微。
緩存淘汰策略
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計(jì)责球、軟件開發(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）。
在各個語言的第三方框架中都大量使用到了 LRU 緩存策略说榆。程序員小吳接觸到的有Java中的 「 Mybatis 」寸认，iOS中的 「YYCache」與「Lottie」等。
LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫偏塞，是根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過油宜，那么將來被訪問的幾率也更高”怜姿。
鏈表實(shí)現(xiàn)LRU
將Cache的所有位置都用雙鏈表連接起來，當(dāng)一個位置被命中之后沧卢，通過調(diào)整鏈表的指向，將該位置調(diào)整到鏈表頭的位置披诗，新加入的Cache直接加到鏈表頭中。
這樣呈队，在多次進(jìn)行Cache操作后唱歧，最近被命中的，就會被向鏈表頭方向移動颅崩，而沒有命中的，而想鏈表后面移動沿彭，鏈表尾則表示最近最少使用的Cache。
當(dāng)需要替換內(nèi)容時候喉刘，鏈表的最后位置就是最少被命中的位置漆弄，我們只需要淘汰鏈表最后的部分即可。
鏈表實(shí)現(xiàn)LRU動畫演示
- 如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了置逻，通過遍歷得到這個數(shù)據(jù)對應(yīng)的結(jié)點(diǎn)，并將其從原來的位置刪除鬓催，然后再插入到鏈表的頭部恨锚。
- 如果此數(shù)據(jù)沒有在緩存鏈表中，可以分為兩種情況：
- 如果此時緩存未滿猴伶，則將此結(jié)點(diǎn)直接插入到鏈表的頭部塌西；
- 如果此時緩存已滿筝尾，則鏈表尾結(jié)點(diǎn)刪除，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部筹淫。
通過動圖可以發(fā)現(xiàn)，如果緩存空間足夠大饰剥，那么存儲的數(shù)據(jù)也就足夠多摧阅，通過緩存中命中數(shù)據(jù)的概率就越大，也就提高了代碼的執(zhí)行速度棒卷。這就是空間換時間的設(shè)計(jì)思想。
對于程序開發(fā)來說岩齿，時間復(fù)雜度和空間復(fù)雜度是可以相互轉(zhuǎn)化的。說通俗一點(diǎn)盹沈，就是：
對于執(zhí)行的慢的程序吃谣，可以通過消耗內(nèi)存（即構(gòu)造新的數(shù)據(jù)結(jié)構(gòu)）來進(jìn)行優(yōu)化；
而消耗內(nèi)存的程序岗憋，可以通過消耗時間來降低內(nèi)存的消耗。
本篇文章的動畫與動圖花了較多時間與精力去處理关串，如果讀者看完之后覺得有所收獲监徘，煩請點(diǎn)一下 「贊」晋修。
學(xué)習(xí)愉快：）
