經(jīng)典的鏈表應(yīng)用場(chǎng)景就是 LRU 緩存淘汰算法姨伤。
1. 鏈表結(jié)構(gòu)
數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲(chǔ),對(duì)內(nèi)存的要求比較高。而鏈表不需要斋否,它通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來使用叙赚。
三種常見的鏈表結(jié)構(gòu):?jiǎn)捂湵砝峡汀㈦p向鏈表和循環(huán)鏈表。
單鏈表:頭結(jié)點(diǎn)記錄鏈表的基地址震叮,可以用來遍歷整條鏈表胧砰。尾結(jié)點(diǎn)的指針指向空地址 NULL,表示最后的結(jié)點(diǎn)苇瓣。每個(gè)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù) data 和后繼指針 next尉间,如下:
針對(duì)鏈表的插入和刪除操作,只需要考慮相鄰結(jié)點(diǎn)的指針改變击罪,所以對(duì)應(yīng)的時(shí)間復(fù)雜度是 O(1)哲嘲。但是,隨機(jī)訪問需要從頭結(jié)點(diǎn)開始遍歷媳禁,所以時(shí)間復(fù)雜度是 O(n)撤蚊。
循環(huán)鏈表是一種特殊的單鏈表,它的尾結(jié)點(diǎn)指針指向鏈表的頭結(jié)點(diǎn)损话,優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便侦啸。當(dāng)要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點(diǎn)時(shí)槽唾,就特別適合采用循環(huán)鏈表,比如約瑟夫問題光涂。
雙向鏈表支持兩個(gè)方向庞萍,每個(gè)結(jié)點(diǎn)有個(gè)后繼指針 next 指向后面的結(jié)點(diǎn)和一個(gè)前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)。它支持雙向遍歷忘闻,帶來了操作的靈活性钝计。雙向鏈表可以支持 O(1) 時(shí)間復(fù)雜度的情況下找到前驅(qū)結(jié)點(diǎn),這使得它在某些情況下的插入齐佳、刪除等操作比單鏈表簡(jiǎn)單高效私恬。對(duì)于一個(gè)有序鏈表,雙向鏈表的按值查詢的效率也要比單鏈表高一些炼吴。
在實(shí)際的軟件開發(fā)中本鸣,雙向鏈表盡管比較費(fèi)內(nèi)存,但比單鏈表的應(yīng)用更加廣泛硅蹦。Java 語(yǔ)言中的 LinkedHashMap 就用到了雙向鏈表荣德,這是用空間換時(shí)間的設(shè)計(jì)思想。
2. 鏈表童芹、數(shù)組性能比較
時(shí)間復(fù)雜度 | 數(shù)組 | 鏈表 |
---|---|---|
插入涮瞻、刪除 | O(n) | O(1) |
隨機(jī)訪問 | O(1) | O(n) |
數(shù)組簡(jiǎn)單易用,在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間假褪,可以借助 CPU 的緩存機(jī)制署咽,預(yù)讀數(shù)組中的數(shù)據(jù),所以訪問效率更高生音。而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)宁否,所以對(duì) CPU 緩存不友好,沒辦法有效預(yù)讀久锥。(此處是局部性原理)
數(shù)組的缺點(diǎn)是大小固定家淤,要占用整塊連續(xù)內(nèi)存空間。如果數(shù)組過大瑟由,容易導(dǎo)致 OOM絮重。擴(kuò)容時(shí)需要拷貝數(shù)組,非常耗時(shí)歹苦。鏈表本身沒有大小的限制青伤,天然地支持動(dòng)態(tài)擴(kuò)容。
如果代碼對(duì)內(nèi)存的使用非撑故荩苛刻狠角,那數(shù)組就是更適合的選擇。鏈表需要額外存儲(chǔ)指針結(jié)點(diǎn)蚪腋,頻繁的增刪操作容易造成內(nèi)存碎片丰歌,如果用 Java 語(yǔ)言姨蟋,就可能導(dǎo)致頻繁 GC。
如何用鏈表實(shí)現(xiàn) LRU 緩存呢立帖?
維護(hù)一個(gè)有序單鏈表眼溶,靠近尾部的結(jié)點(diǎn)是最早訪問的。當(dāng)有數(shù)據(jù)被訪問時(shí)晓勇,從頭開始遍歷鏈表堂飞。
- 如果數(shù)據(jù)被緩存過,遍歷得到對(duì)應(yīng)的結(jié)點(diǎn)绑咱,把它從原來位置刪除绰筛,插入到鏈表頭部。
- 如果沒有緩存過描融,那么分兩種情況:
- 如果緩存沒滿铝噩,那么直接把新數(shù)據(jù)插入鏈表尾部;
- 如果緩存已滿稼稿,那么把尾結(jié)點(diǎn)刪除薄榛,新數(shù)據(jù)插入鏈表頭部讳窟。
基于鏈表的實(shí)現(xiàn)思路让歼,緩存訪問的時(shí)間復(fù)雜度為 O(n)±龇龋考慮一下優(yōu)化谋右,比如引入散列表老記錄每個(gè)數(shù)據(jù)的位置,使訪問時(shí)間復(fù)雜度降到 O(1)补箍。
思考題:
如何判斷一個(gè)字符串是否是回文字符串改执?如果字符串是通過單鏈表來存儲(chǔ)的,那該如何來判斷是一個(gè)回文串呢坑雅?