?最近有一些粉絲問了我個(gè)問題，我平時(shí)是怎樣學(xué)習(xí)一門新的技術(shù)的，文章開始之前我先來分享一下我的制勝法寶。
?博主學(xué)習(xí)方法
“三刷”官方文檔或源碼是我高效學(xué)習(xí)一門新的技能的制勝法寶：
1刷從頭看到尾，掃清知識(shí)盲點(diǎn)，搞清楚概念；
2刷必須手敲，而且要寫注釋和總結(jié)；
3刷先只寫注釋，不看文檔實(shí)現(xiàn)功能，遇到問題再和文檔比較，加深理解。
?前言
上篇我們總結(jié)了對數(shù)組的理解，這篇再談?wù)剬︽湵淼睦斫狻?/p>
本篇文章主要分析如下幾個(gè)問題：
- 鏈表和數(shù)組相比有哪些不同點(diǎn)？它的優(yōu)點(diǎn)是什么？
- 鏈表有哪些類別？它們各自的優(yōu)缺點(diǎn)是什么？
- 如何使用鏈表實(shí)現(xiàn)LRU算法？
鏈表相對于數(shù)組而言，是兩種不同的內(nèi)存組織方式，鏈表不需要連續(xù)的內(nèi)存空間，天然支持動(dòng)態(tài)擴(kuò)容，而且不像數(shù)組擴(kuò)容那樣需要搬運(yùn)數(shù)據(jù)。鏈表大小等于實(shí)際使用大小，不存在浪費(fèi)空間的現(xiàn)象。鏈表適合插入和刪除操作，時(shí)間復(fù)雜度為O(1)，但是并不意味著適合非常頻繁地插入和刪除，因?yàn)槟菢訒?huì)導(dǎo)致頻繁地申請內(nèi)存和釋放內(nèi)存，容易造成內(nèi)存碎片，從而提高GC的頻率。
??單向鏈表
每一塊內(nèi)存區(qū)域稱為一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有兩塊區(qū)域，數(shù)據(jù)域保存節(jié)點(diǎn)數(shù)據(jù)，指針域指向下一個(gè)節(jié)點(diǎn)的地址。其中，頭節(jié)點(diǎn)是整個(gè)鏈表的基地址，通過它可以遍歷整個(gè)鏈表；尾節(jié)點(diǎn)的指針值為空，不指向任何地址。
單鏈表比較適合插入和刪除操作，時(shí)間復(fù)雜度為O(1)，注意此處不包含查找到該元素的時(shí)間，但是查詢操作效率較低，時(shí)間復(fù)雜度為O(n)；
單鏈表結(jié)構(gòu)示意
???雙向鏈表
每一塊內(nèi)存區(qū)域稱為一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有三塊區(qū)域，前指針域指向上一個(gè)節(jié)點(diǎn)的地址，數(shù)據(jù)域保存節(jié)點(diǎn)數(shù)據(jù)，后指針域指向下一個(gè)節(jié)點(diǎn)的地址。和單向鏈表相比，存儲(chǔ)相同多的數(shù)據(jù)，雙向鏈表需要的存儲(chǔ)空間更多。
雙向鏈表的插入、刪除和查詢操作都要比單向鏈表的相同操作的效率更高：
- 插入
- 如果需要在第k個(gè)節(jié)點(diǎn)處插入一個(gè)新的節(jié)點(diǎn)，那么單鏈表需要找到前一個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)，而雙向鏈表只需要往前遍歷一個(gè)節(jié)點(diǎn)就能找到，時(shí)間復(fù)雜度為O(1)。
- 刪除
- 如果是需要?jiǎng)h除給定的元素，那么就只能從第一個(gè)節(jié)點(diǎn)開始遍歷，這種情況兩種鏈表的時(shí)間復(fù)雜度是一樣的；但是如果是給定需要?jiǎng)h除元素的指針，那么單鏈表因?yàn)橐业角耙粋€(gè)元素p，使得p.next指向待刪除元素的下一個(gè)節(jié)點(diǎn)，所以時(shí)間復(fù)雜度為O(n)，而雙向鏈表則只需要往前遍歷一個(gè)節(jié)點(diǎn)就能找到，時(shí)間復(fù)雜度為O(1)。
- 查詢
- 對于有序鏈表，每次查找元素k，雙向鏈表可以根據(jù)和當(dāng)前節(jié)點(diǎn)的值得大小比較來決定往前遍歷還是往后遍歷，而單鏈表只能往后或者從頭結(jié)點(diǎn)重新開始遍歷。
因此，即便雙向鏈表比較占用空間，但這是一種空間換時(shí)間的設(shè)計(jì)思想，使用場景反而比單向鏈表更多。
雙向鏈表結(jié)構(gòu)示意
????循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表，區(qū)別是其尾節(jié)點(diǎn)的指針域不是空，而是指向頭節(jié)點(diǎn)。其優(yōu)點(diǎn)就是從鏈表尾部到鏈表頭部比較方便，當(dāng)我們需要處理環(huán)形結(jié)構(gòu)的數(shù)據(jù)時(shí)，就比較合適。
循環(huán)鏈表結(jié)構(gòu)示意
當(dāng)然，將雙向鏈表和循環(huán)鏈表組合起來，就能形成一個(gè)雙向循環(huán)鏈表，這個(gè)用得不多，不贅述。
雙向循環(huán)鏈表結(jié)構(gòu)示意
?????使用鏈表實(shí)現(xiàn)LRU
常見的緩存淘汰策略有三種，F(xiàn)IFO（先進(jìn)先出Firt In First Out）、LFU（最少使用Least Frequently Used）、LRU（最近最少使用Least Recently Used）。
- 對于當(dāng)前數(shù)據(jù)，遍歷鏈表，如果在鏈表中已經(jīng)存在了，那么刪除該節(jié)點(diǎn)，并在鏈表頭插入該數(shù)據(jù)；
- 如果在鏈表中不存在，判斷當(dāng)前鏈表是否小于最大長度，如果沒有，直接插入到頭部；
- 如果已經(jīng)等于最大長度，那么刪除尾節(jié)點(diǎn)后，再插入到頭部；
- 該算法的時(shí)間復(fù)雜度為O(n)，因?yàn)闊o論如何，都要遍歷一次鏈表；
