鏈表經(jīng)典應(yīng)用場景：LRU緩存算法稿辙。
緩存淘汰策略常見的有三種：
- 先進先出策略（FIFO）
- 最少使用策略（LFU）
- 最近最少使用策略LRU
鏈表
鏈表與數(shù)據(jù)不同的之處在于赋咽，內(nèi)存不是連續(xù)的脓匿，可以將分散的內(nèi)存塊串聯(lián)起來使用陪毡。
鏈表結(jié)構(gòu)大概有三種：單鏈表毡琉，雙向鏈表桅滋，循環(huán)鏈表
單鏈表
單鏈表丐谋，摘自極客時間
鏈表需要有頭節(jié)點與尾節(jié)點泌豆。單鏈表中頭結(jié)點表示：鏈表的基地址；尾節(jié)點志向的地址是空地址NULL陨倡。
數(shù)組進行插入語刪除操作的時候许布，為了保證內(nèi)存的連續(xù)性蜜唾，需要做數(shù)據(jù)的搬移操作袁余，時間復(fù)雜度是O(N)棚饵；
鏈表中插入刪除操作噪漾，不需要保證內(nèi)存的連續(xù)性题翰，插入與刪除是十分快速的。
但是隨機訪問效率就特別低焦匈，需要從頭結(jié)點開始查找。隨機查找的時間復(fù)雜度就是O(N)荚虚。
循環(huán)鏈表
相對于單鏈表來說版述，尾節(jié)點指向頭結(jié)點即可。
最著名的是 約瑟夫環(huán)問題.
雙向鏈表
雙向鏈表支持兩個 方向，在一個實體中有指向上一個節(jié)點漓帚，也有指向下一個節(jié)點的指針尝抖。
雙向鏈表，來自極客時間
缺點：
占用的空間多搅荞，浪費存儲空間
優(yōu)點：
操作上更加靈活，插入與刪除操作更加簡單與高效。
- 刪除給定的某個值節(jié)點： 需要從頭開始遍歷婉称，時間復(fù)雜度是O(1),主要耗時是查找時間是O(N).
- 對于刪除給定的指針指向的節(jié)點： 找到要刪除的節(jié)點，要刪除前一個節(jié)點俗壹，或者向前面插入一個節(jié)點藻烤。都是十分方便的不需要再查詢涎显。
雙向循環(huán)鏈表
把循環(huán)鏈表與雙向鏈表組合在一起形成。
實現(xiàn)LRU緩存淘淘算法
思路：
- 單向鏈表存儲數(shù)據(jù)讨勤，每次從頭遍歷數(shù)據(jù)潭千，如果存在那么刪除原先的位置脊岳，再把數(shù)據(jù)插入到頭部即可。
- 如果此數(shù)據(jù)不存在緩存表中亿驾，緩存沒有滿莫瞬，直接插入到鏈表的頭部疼邀。滿了旁振，就刪除尾節(jié)點吉嚣，再插入到頭部指針尝哆。
