常見的緩存淘汰策略有三種：先進(jìn)先出策略 FIFO（First In清酥，F(xiàn)irst Out）、最少使用策略 LFU（Least Frequently Used）禾乘、最近最少使用策略 LRU（Least Recently Used）
鏈表（Linked list）回顧
1.底層的存儲(chǔ)結(jié)構(gòu)
數(shù)組需要一塊連續(xù)的內(nè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)存空間网缝，它通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來使用，所以如果我們申請(qǐng)的是 100MB 大小的鏈表蟋定，根本不會(huì)有問題粉臊。
2.三種最常見的鏈表結(jié)構(gòu)：單鏈表、雙向鏈表和循環(huán)鏈表
鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起溢吻。维费，我們把內(nèi)存塊稱為鏈表的“結(jié)點(diǎn)”果元。為了將所有的結(jié)點(diǎn)串起來促王，每個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外，還需要記錄鏈上的下一個(gè)結(jié)點(diǎn)的地址而晒。如圖所示蝇狼，我們把這個(gè)記錄下個(gè)結(jié)點(diǎn)地址的指針叫作后繼指針 next。
我們習(xí)慣性地把第一個(gè)結(jié)點(diǎn)叫作頭結(jié)點(diǎn)倡怎，把最后一個(gè)結(jié)點(diǎn)叫作尾結(jié)點(diǎn)迅耘。其中贱枣，頭結(jié)點(diǎn)用來記錄鏈表的基地址。有了它颤专，我們就可以遍歷得到整條鏈表纽哥。尾結(jié)點(diǎn)的指針不是指向下一個(gè)結(jié)點(diǎn)，而是指向一個(gè)空地址 NULL栖秕，表示這是鏈表上最后一個(gè)結(jié)點(diǎn)春塌。與數(shù)組一樣，鏈表也支持?jǐn)?shù)據(jù)的查找簇捍、插入和刪除操作只壳。
數(shù)組的插入、刪除操作時(shí)暑塑，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性吼句，需要做大量的數(shù)據(jù)搬移，所以時(shí)間復(fù)雜度是O(n)事格。針對(duì)鏈表的插入和刪除操作惕艳，我們只需要考慮相鄰結(jié)點(diǎn)的指針改變，所以對(duì)應(yīng)的時(shí)間復(fù)雜度是 O(1)驹愚。
鏈表要想隨機(jī)訪問第 k 個(gè)元素尔艇，就沒有數(shù)組那么高效了。因?yàn)殒湵碇械臄?shù)據(jù)并非連續(xù)存儲(chǔ)的么鹤，所以無法像數(shù)組那樣终娃，根據(jù)首地址和下標(biāo)，通過尋址公式就能直接計(jì)算出對(duì)應(yīng)的內(nèi)存地址蒸甜，而是需要根據(jù)指針一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)地依次遍歷棠耕，直到找到相應(yīng)的結(jié)點(diǎn)。所以柠新，鏈表隨機(jī)訪問的性能沒有數(shù)組好窍荧，需要 O(n) 的時(shí)間復(fù)雜度。
循環(huán)鏈表是一種特殊的單鏈表
循環(huán)鏈表的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便恨憎。當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點(diǎn)時(shí)蕊退，就特別適合采用循環(huán)鏈表。比如著名的約瑟夫問題憔恳。
在實(shí)際的軟件開發(fā)中更加常用的鏈表結(jié)構(gòu)：雙向鏈表
單向鏈表只有一個(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)点把。
如果存儲(chǔ)同樣多的數(shù)據(jù)橘荠，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。雖然兩個(gè)指針比較浪費(fèi)存儲(chǔ)空間郎逃，但可以支持雙向遍歷哥童，這樣也帶來了雙向鏈表操作的靈活性。
在實(shí)際的軟件開發(fā)中褒翰，從鏈表中刪除一個(gè)數(shù)據(jù)無外乎這兩種情況：刪除結(jié)點(diǎn)中“值等于某個(gè)給定值”的結(jié)點(diǎn)如蚜；刪除給定指針指向的結(jié)點(diǎn)。對(duì)于第一種情況影暴，不管是單鏈表還是雙向鏈表错邦，為了查找到值等于給定值的結(jié)點(diǎn)，都需要從頭結(jié)點(diǎn)開始一個(gè)一個(gè)依次遍歷對(duì)比型宙，直到找到值等于給定值的結(jié)點(diǎn)撬呢，然后再通過我前面講的指針操作將其刪除。盡管單純的刪除操作時(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)芯勘。對(duì)于第二種情況，我們已經(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够委，說明 p 是 q 的前驅(qū)結(jié)點(diǎn)荐类。但是對(duì)于雙向鏈表來說，這種情況就比較有優(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)就搞定了战秋！
了解了循環(huán)鏈表和雙向鏈表璧亚，如果把這兩種鏈表整合在一起就是一個(gè)新的版本：雙向循環(huán)鏈表
如何基于鏈表實(shí)現(xiàn) LRU 緩存淘汰算法讨韭？
思路：我們維護(hù)一個(gè)有序單鏈表脂信，越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪問的癣蟋。當(dāng)有一個(gè)新的數(shù)據(jù)被訪問時(shí)，我們從鏈表頭開始順序遍歷鏈表狰闪。
- 如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了疯搅，我們遍歷得到這個(gè)數(shù)據(jù)對(duì)應(yīng)的結(jié)點(diǎn)，并將其從原來的位置刪除埋泵，然后再插入到鏈表的頭部幔欧。
- 如果此數(shù)據(jù)沒有在緩存鏈表中，又可以分為兩種情況：
如果此時(shí)緩存未滿丽声，則將此結(jié)點(diǎn)直接插入到鏈表的頭部礁蔗；
如果此時(shí)緩存已滿，則鏈表尾結(jié)點(diǎn)刪除雁社，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部浴井。
這樣我們就用鏈表實(shí)現(xiàn)了一個(gè) LRU 緩存。
