今天學(xué)習(xí)了鏈表（linked list）這個數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)鏈表有啥用呢？如何用鏈表來實(shí)現(xiàn)“LRU緩存淘汰算法”呢？思路是啥呢？。
LRU 是啥？？
LRU（Least Recently Used）最近最少使用策略。緩存的容量是有限的
當(dāng)緩存容量不足以存放需要緩存的新數(shù)據(jù)時，必須丟掉最不常用的緩存數(shù)據(jù)。

先來看看鏈表是啥吧

鏈表結(jié)構(gòu)

以前因?yàn)楹闷妫?我跟著豆豆一起學(xué)過一些鏈表的基本概念，大概理解為：鏈表像是一個鐵鏈子，一環(huán)扣一環(huán)。每一環(huán)也只知道自己的前后是誰。鏈表用一個next連接這自己的下一個元素。

好像這個概念和我們之前說的數(shù)組很像呢，確實(shí)很像，那有什么不一樣的地方呢？
數(shù)組是可以任意訪問的，但是鏈表要訪問其中的第n 個元素的時候，只能從頭開始找。這樣，時間復(fù)雜度一直都是O(n) 鏈表不需要一個連續(xù)的存儲空間，他的每個元素可以是零散的。如果內(nèi)存不足的時候，申請一個超過內(nèi)存的鏈表也是可以成功的，但是數(shù)組就不得行了。

• 單鏈表
  我比較喜歡單鏈表，人家多單純啊，只是單向的用next連接著自己的下一個元素。最后一個結(jié)點(diǎn)的 next指向null 就好了, 如果想給里面插入或者刪掉數(shù)據(jù)的時候，很簡單的做法就是直接改變相應(yīng)的next 指針指向就好了。

• 循環(huán)鏈表
  循環(huán)鏈表和單鏈表的區(qū)別就是最后一個next 指針指向第一個，這樣就能形成一個單項(xiàng)的環(huán)。

• 雙向鏈表
  前面的單鏈表和循環(huán)鏈表都只是單向的，那么雙向鏈接的區(qū)別就是除了有next,還會定義prev。這樣每個item 不僅僅需要存儲next ，還需要存儲prev，這樣肯定會更多的消耗空間，那它相對于單向的好處是什么呢？
  ``

• 雙向循環(huán)鏈表
  雙向循環(huán)鏈表 就是雙向鏈表 + 循環(huán)鏈表。兩個特性的結(jié)合
  ``

從結(jié)構(gòu)上來看，雙向鏈表可以在O（1）的時間復(fù)雜度里面，找到前一個item。但是在單鏈表里面，需要重新再循環(huán)一次整個鏈表，時間復(fù)雜度就是O（n）

在實(shí)際的開發(fā)中，指定新增和指定刪除的時候，雙向鏈表的性能都要高于單向鏈表
相對于數(shù)組，鏈表更適用于更加頻繁的插入，刪除，和復(fù)雜度更高的場景。

如何基于鏈表實(shí)現(xiàn) LRU 緩存淘汰算法？

基礎(chǔ)思路是：

維護(hù)一個單向鏈表，越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪問的。當(dāng)有一個新的數(shù)據(jù)被訪問時，我們從鏈表頭開始順序遍歷鏈表。  
if 這個鏈表里，本身有這個item，那么就把這個item 從原來的位置刪掉，然后插入到鏈表頭的位置 
else 直接插入到頭部（可能還需要兼容考慮此時緩存是否滿）

我感覺用數(shù)組應(yīng)該也是這個思路。只是實(shí)現(xiàn)方式不一樣而已

今天又是學(xué)習(xí)理論知識的一天，期待實(shí)踐s。