三、链表(Linked List)（原理）
前言
經(jīng)典的鏈表應(yīng)用場景：LRU 緩存淘汰算法
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，由于緩存的大小有限，當(dāng)緩存被用滿時，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來決定。
- 常見的策略有三種：
- 先進先出策略 FIFO（First In，First Out）
- 最少使用策略 LFU（Least Frequently Used）
- 最近最少使用策略 LRU（Least Recently Used）
==》如何用鏈表來實現(xiàn) LRU 緩存淘汰策略呢？ ==》詳見 五 的解答
一、鏈表
鏈表：不需要一塊連續(xù)的內(nèi)存空間，它通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來使用.
內(nèi)存分布：
最常用的鏈表結(jié)構(gòu)：單鏈表、雙向鏈表和循環(huán)鏈表
二、單鏈表
1、基本概念
結(jié)點（Node）：單鏈表的結(jié)點結(jié)構(gòu)
鏈表中的每一個數(shù)據(jù)元素稱為 “結(jié)點” ，每個結(jié)點都由兩部分組成：數(shù)據(jù)域 + 指針域。其中，數(shù)據(jù)域存儲數(shù)據(jù)元素信息，指針域存儲鏈表的下一個結(jié)點的位置信息，是一個指針。
單鏈表：當(dāng)一個序列中只含有指向它的后繼結(jié)點的鏈接時，就稱該鏈表為單鏈表。
- 非空表(有頭結(jié)點)：
- 空表：
頭指針：是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指針。頭指針具有標識作用。任何情況下,頭指針都存在,無論鏈表是否為空。
頭結(jié)點：為了操作的統(tǒng)一和方便（插入/刪除首元結(jié)點）設(shè)立的，放在首元結(jié)點(第一元素結(jié)點)之前，其數(shù)據(jù)域一般無意義（也可以 存放鏈表的長度）。非必需要素。
最后一個結(jié)點：最后一個結(jié)點指針為“空”（通常用NULL或“^”符號表示），是鏈表的結(jié)束標志，表示它沒有后繼結(jié)點。
2、查找操作
目標：隨機訪問第 k 個元素 ==》依次遍歷 ==》時間復(fù)雜度：O(n)
3、插入操作
插入 x 結(jié)點： ==》時間復(fù)雜度：O(1)
① x->next = a2 -> next
② a2 -> next = x
4、刪除操作
刪除 a2 結(jié)點： ==》時間復(fù)雜度：O(1)
① p = a1->next
② a1->next = p->next
三、循環(huán)鏈表
循環(huán)鏈表：與單鏈表的唯一區(qū)別就是最后一個結(jié)點的指針指向鏈表的頭結(jié)點。
優(yōu)點： 從鏈尾到鏈頭比較方便。當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點時，就特別適合采用循環(huán)鏈表。eg: 約瑟夫問題
四、雙向鏈表
雙向鏈表：每個結(jié)點不止有一個后繼指針 next 指向后面的結(jié)點，還有一個前驅(qū)指針 prev 指向前面的結(jié)點。
特點：支持雙向遍歷，更具靈活性；O(1) 時間復(fù)雜度的情況下前驅(qū)結(jié)點
結(jié)點：
2、雙向鏈表的優(yōu)勢
（1）刪除
刪除的兩種情況：
- 刪除結(jié)點中“值等于某個給定值”的結(jié)點
- 刪除給定指針指向的結(jié)點
第一種情況
無論單鏈表還是雙向鏈表，均需要從頭開始遍歷對比，直至找到值等于給定值的結(jié)點，然后再執(zhí)行刪除操作。==》時間復(fù)雜度：O(n)
第二種情況
已找到需刪除的結(jié)點，但是刪除某個結(jié)點 q 需要得到其前驅(qū)結(jié)點，雙向鏈表可以不用遍歷就得到前驅(qū)結(jié)點。 ==》時間復(fù)雜度：O(1)
（2）有序鏈表的查找操作
對于有序鏈表，雙向鏈表的按值查詢的效率要比單鏈表高一些。具體來說，可以記錄上次查找的位置 p ，每次查找時，根據(jù)查詢值與 p 的大小關(guān)系，決定向前還是向后查找。
五、設(shè)計思想：空間 <-> 時間
- 當(dāng)內(nèi)存足夠時，若追求代碼的執(zhí)行速度 ==》選擇空間復(fù)雜度高、時間復(fù)雜度相對較低的算法或者數(shù)據(jù)結(jié)構(gòu)
- 當(dāng)內(nèi)存比較緊張 ==》時間換空間
鏈表實現(xiàn)LRU緩存淘汰算法：越靠近鏈表尾部的結(jié)點是越早之前訪問的
- 若此時緩存未滿 ==》此結(jié)點直接插入到鏈表的頭部；
- 若此時緩存已滿，則鏈表的最后一個結(jié)點刪除，并將新的數(shù)據(jù)結(jié)點插入鏈表的頭部
總結(jié)
以上是生活随笔為你收集整理的三、链表(Linked List)（原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
