五花八門的鏈表結(jié)構(gòu)
鏈表比數(shù)組稍微復(fù)雜一點(diǎn)。
同樣是非?；A(chǔ)非常常用的數(shù)據(jù)結(jié)構(gòu)。
鏈表不需要一塊連續(xù)的內(nèi)存空間，通過"指針"將一組零散的內(nèi)存塊串聯(lián)起來使用。
三種常用的鏈表：單鏈表、雙鏈表和循環(huán)鏈表。
單鏈表：
存在頭結(jié)點(diǎn)和尾結(jié)點(diǎn)，尾結(jié)點(diǎn)指向空地址NULL。
鏈表的插入和刪除操作不需要為了保存內(nèi)存的連續(xù)性而搬移節(jié)點(diǎn)。插入和刪除操作只需要考慮相鄰節(jié)點(diǎn)的指針改變，所以對(duì)應(yīng)的時(shí)間復(fù)雜度為O(1).
同時(shí)因?yàn)閿?shù)據(jù)并非連續(xù)存儲(chǔ)，鏈表的隨機(jī)訪問沒有數(shù)組那么高效，需要根據(jù)指針一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)得一次遍歷，需要O(n)的時(shí)間復(fù)雜度。
循環(huán)鏈表：特殊的單鏈表，尾結(jié)點(diǎn)指針指向頭節(jié)點(diǎn)，首尾相連。當(dāng)處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)特點(diǎn)時(shí)，優(yōu)先考慮。
雙向鏈表：每個(gè)節(jié)點(diǎn)不止有一個(gè)后繼指針next指向后面的節(jié)點(diǎn)，還有一個(gè)前驅(qū)指針prev指向前面的節(jié)點(diǎn)。雖然兩個(gè)指針比較浪費(fèi)存儲(chǔ)空間，但是支持雙向遍歷。
刪除操作：
單純的刪除操作復(fù)雜度是O(1),但是遍歷找到節(jié)點(diǎn)的時(shí)間為O(n),所以根據(jù)假發(fā)法則，刪除指定節(jié)點(diǎn)的的總時(shí)間復(fù)雜度為 O(n).
如果要?jiǎng)h除了指定節(jié)點(diǎn)p后，我們需要找到p的前驅(qū)節(jié)點(diǎn)o，并把其指向p的后繼節(jié)點(diǎn)q。
雙向指針有效避免了以上的問題，雙鏈表刪除指定節(jié)點(diǎn)只需要O(1).
新增同理。如java設(shè)計(jì)的LinkedHashMap也使用了雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)。
注意設(shè)計(jì)思想：空間換時(shí)間、時(shí)間換空間。
鏈表VS數(shù)組
注意 鏈表的頻繁插入、刪除操作會(huì)導(dǎo)致頻繁的內(nèi)存申請(qǐng)和釋放，容易造成內(nèi)存碎片，在java中則會(huì)導(dǎo)致頻繁的GC.
開篇問題
如何用鏈表來實(shí)現(xiàn)LRU緩存淘汰策略呢？
Least Frequently Used: 最近最不常用算法,根據(jù)數(shù)據(jù)的歷史訪問頻率來淘汰數(shù)據(jù)
核心思想是：
最近使用頻率高的數(shù)據(jù)很大概率將會(huì)再次被使用,而最近使用頻率低的數(shù)據(jù),很大概率不會(huì)再使用。
當(dāng)訪問的數(shù)據(jù)沒有存儲(chǔ)在緩存的鏈表中時(shí)，直接將數(shù)據(jù)插入鏈表表頭，需要比較數(shù)據(jù)，時(shí)間復(fù)雜度為O(N)；
當(dāng)訪問的數(shù)據(jù)存在于存儲(chǔ)的鏈表中時(shí)，將該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)，插入到鏈表表頭,時(shí)間復(fù)雜度為O(n)。
如果緩存被占滿，則從鏈表尾部的數(shù)據(jù)開始清理，時(shí)間復(fù)雜度為O(n)。
此文章為2月Day2學(xué)習(xí)筆記，內(nèi)容來源與極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)與算法之美》
