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