? ? ? ? 鏈表是一種不連續(xù)的線性數(shù)據(jù)結(jié)構(gòu)吗货。常見的有單鏈表，循環(huán)鏈表狈网，雙鏈表宙搬。
? ? ? ? 鏈表通過指針將一組零散的內(nèi)存塊串聯(lián)在一起，我們把內(nèi)存塊稱為鏈表的結(jié)點(diǎn)拓哺。結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外勇垛，還存有指向其他結(jié)點(diǎn)的指針。指向后一個(gè)結(jié)點(diǎn)的指針稱為后繼指針(next)士鸥，指向前一個(gè)結(jié)點(diǎn)的指針稱為前驅(qū)指針(pre)闲孤。
單鏈表.jpg
? ? ? ? 單鏈表的尾結(jié)點(diǎn)指向一個(gè)null地址，代表這是鏈表的最后一個(gè)結(jié)點(diǎn)烤礁。與數(shù)組一樣崭放，鏈表也支持?jǐn)?shù)據(jù)的查找哨苛，刪除，插入币砂。因?yàn)閿?shù)組是一組連續(xù)的內(nèi)存空間建峭，所以在數(shù)組上進(jìn)行插入刪除操作時(shí)，需要做大量的數(shù)據(jù)搬移决摧，時(shí)間復(fù)雜度是O(n)亿蒸，但是也正因?yàn)檫@種特性，數(shù)組適合隨機(jī)訪問數(shù)據(jù)(addr=base_addr+i*data_type_size)掌桩。而在鏈表上進(jìn)行插入刪除操作時(shí)边锁，只需要改變結(jié)點(diǎn)的指針即可，對(duì)應(yīng)的時(shí)間復(fù)雜度是O(1)波岛。
image.png
? ? ? ? 循環(huán)列表是一種特殊的單鏈表茅坛，單鏈表的最后一個(gè)結(jié)點(diǎn)next指針為null，變成循環(huán)列表只需要把該指針重新指向頭結(jié)點(diǎn)即可则拷。
image.png
? ? ? ? 循環(huán)列表的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便贡蓖，當(dāng)要處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)特點(diǎn)時(shí)，適合采用循環(huán)鏈表煌茬。
雙向鏈表結(jié)點(diǎn)含有兩個(gè)指針斥铺，next和pre，分別指向后一個(gè)結(jié)點(diǎn)和前一個(gè)結(jié)點(diǎn)坛善。
image.png
? ? ? ? 所以晾蜘，如果存儲(chǔ)同樣的數(shù)據(jù)，雙鏈表比單鏈表更費(fèi)內(nèi)存空間眠屎，但是它也具有更好的靈活性剔交。單鏈表結(jié)構(gòu)需要找到一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)時(shí)，需要從頭結(jié)點(diǎn)遍歷改衩，而雙鏈表結(jié)點(diǎn)本身就存儲(chǔ)了前驅(qū)結(jié)點(diǎn)的地址省容。
? ? ? ? 這里說一種非常重要的設(shè)計(jì)思想空間換時(shí)間。當(dāng)內(nèi)存空間充足時(shí)燎字，我們更追求代碼的執(zhí)行速度腥椒，此時(shí)可以采用空間復(fù)雜度相對(duì)較高但時(shí)間復(fù)雜度較低的數(shù)據(jù)結(jié)構(gòu)或算法。比如著名的LRU緩存淘汰算法就是利用了空間換時(shí)間的設(shè)計(jì)思想候衍。如果我們把數(shù)據(jù)存儲(chǔ)在硬盤上會(huì)比較節(jié)省內(nèi)存笼蛛，但是每一次查找數(shù)據(jù)都需要訪問硬盤，會(huì)比較慢蛉鹿。但如果我們通過緩存技術(shù)滨砍，先將數(shù)據(jù)緩存在內(nèi)存中，雖然比較耗費(fèi)內(nèi)存空間，但是數(shù)據(jù)查詢速度大大提高惋戏。
? ? ? ? 引申领追，雙向循環(huán)列表
image.png
? ? ? ?CPU從內(nèi)存中讀取數(shù)據(jù)的時(shí)候，會(huì)先把讀取到的數(shù)據(jù)加載到CPU的緩存中响逢。而CPU每次從內(nèi)存中讀取數(shù)據(jù)并不只是讀取那個(gè)特定的地址绒窑，而是讀取一個(gè)數(shù)據(jù)塊并加載到CPU緩存中，當(dāng)下次要訪問數(shù)據(jù)的時(shí)候舔亭，會(huì)先從緩存中開始查找些膨，如果找到了就不需要再從內(nèi)存中讀取，這樣就實(shí)現(xiàn)了比內(nèi)存訪問速度更快的機(jī)制钦铺。而對(duì)于數(shù)組來說订雾，存儲(chǔ)空間是連續(xù)的，所以CPU會(huì)把要訪問數(shù)據(jù)的周邊數(shù)據(jù)一并加載到CPU緩存中矛洞，訪問效率更高洼哎，而鏈表是不連續(xù)的存儲(chǔ)空間，所以對(duì)CPU緩存不太友好沼本。
