今天學(xué)習(xí)了鏈表（linked list）這個數(shù)據(jù)結(jié)構(gòu)蝗柔。學(xué)習(xí)鏈表有啥用呢？如何用鏈表來實現(xiàn)“LRU緩存淘汰算法”呢民泵？思路是啥呢癣丧？。
LRU 是啥栈妆？胁编？
LRU（Least Recently Used）最近最少使用策略。緩存的容量是有限的
當(dāng)緩存容量不足以存放需要緩存的新數(shù)據(jù)時鳞尔，必須丟掉最不常用的緩存數(shù)據(jù)嬉橙。
先來看看鏈表是啥吧
鏈表結(jié)構(gòu)
以前因為好奇， 我跟著豆豆一起學(xué)過一些鏈表的基本概念寥假，大概理解為：鏈表像是一個鐵鏈子市框，一環(huán)扣一環(huán)。每一環(huán)也只知道自己的前后是誰糕韧。鏈表用一個next連接這自己的下一個元素枫振。
好像這個概念和我們之前說的數(shù)組很像呢，確實很像萤彩，那有什么不一樣的地方呢蒋得？
數(shù)組是可以任意訪問的，但是鏈表要訪問其中的第n 個元素的時候乒疏，只能從頭開始找额衙。這樣，時間復(fù)雜度一直都是O(n) 鏈表不需要一個連續(xù)的存儲空間怕吴，他的每個元素可以是零散的窍侧。如果內(nèi)存不足的時候，申請一個超過內(nèi)存的鏈表也是可以成功的转绷，但是數(shù)組就不得行了伟件。
單鏈表
我比較喜歡單鏈表，人家多單純啊议经，只是單向的用next連接著自己的下一個元素斧账。最后一個結(jié)點的next指向null 就好了, 如果想給里面插入或者刪掉數(shù)據(jù)的時候，很簡單的做法就是直接改變相應(yīng)的next 指針指向就好了煞肾。循環(huán)鏈表
循環(huán)鏈表和單鏈表的區(qū)別就是最后一個next 指針指向第一個咧织，這樣就能形成一個單項的環(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）
在實際的開發(fā)中，指定新增和指定刪除的時候葫辐，雙向鏈表的性能都要高于單向鏈表
相對于數(shù)組，鏈表更適用于更加頻繁的插入伴郁，刪除耿战，和復(fù)雜度更高的場景。
如何基于鏈表實現(xiàn) LRU 緩存淘汰算法焊傅？
基礎(chǔ)思路是：
維護一個單向鏈表剂陡，越靠近鏈表尾部的結(jié)點是越早之前訪問的。當(dāng)有一個新的數(shù)據(jù)被訪問時狐胎，我們從鏈表頭開始順序遍歷鏈表鸭栖。
if 這個鏈表里，本身有這個item握巢，那么就把這個item 從原來的位置刪掉晕鹊，然后插入到鏈表頭的位置
else 直接插入到頭部（可能還需要兼容考慮此時緩存是否滿）
我感覺用數(shù)組應(yīng)該也是這個思路。只是實現(xiàn)方式不一樣而已
今天又是學(xué)習(xí)理論知識的一天暴浦，期待實踐s溅话。
