數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 提高讀取性能的鏈表（上）
前言
鏈表（Linked list）比數(shù)組稍微復(fù)雜一點(diǎn)，在我們生活中用到最常見的應(yīng)該是緩存，它是一種提高數(shù)據(jù)讀取性能的技術(shù)，常見的如cpu緩存，瀏覽器緩存，數(shù)據(jù)庫緩存等。今天我們就來學(xué)習(xí)一下鏈表
正文
一、鏈表的定義？
1.一種線性表（數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個(gè)線性表上的數(shù)據(jù)最多有前后兩個(gè)方向）；
2.從存儲(chǔ)結(jié)構(gòu)來看，通過“指針”，將一組零散的內(nèi)存塊串聯(lián)起來使用的數(shù)據(jù)結(jié)構(gòu)；
3.鏈表中的每一個(gè)內(nèi)存塊被稱為結(jié)點(diǎn)Node，結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外，還需記錄鏈上下一個(gè)節(jié)點(diǎn)的地址（next）
二、鏈表的優(yōu)缺點(diǎn)
1.插入、刪除數(shù)據(jù)效率高，時(shí)間復(fù)雜度為O(1)（只需更改指針指向即可），隨機(jī)訪問效率低，時(shí)間復(fù)雜度為O(n)級(jí)別（需要從鏈頭至鏈尾進(jìn)行遍歷）。
2.和數(shù)組相比，內(nèi)存空間消耗更大，因?yàn)槊總€(gè)存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)都需要額外的空間存儲(chǔ)后繼指針。
三、常用鏈表：單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表和塊狀鏈表
1.單鏈表
1）每個(gè)節(jié)點(diǎn)只包含一個(gè)指針，即后繼指針。
2）單鏈表有兩個(gè)特殊的節(jié)點(diǎn)，即首節(jié)點(diǎn)和尾節(jié)點(diǎn)。
用首節(jié)點(diǎn)地址表示整條鏈表，尾節(jié)點(diǎn)的后繼指針指向空地址null。
3）性能特點(diǎn)：插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（1），查找的時(shí)間復(fù)雜度為O(n)。
2.循環(huán)鏈表
1）除了尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)的地址外均與單鏈表一致。
2）適用于存儲(chǔ)有循環(huán)特點(diǎn)的數(shù)據(jù)，比如約瑟夫問題。
3.雙向鏈表
1）節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外，還有兩個(gè)指針分別指向前一個(gè)節(jié)點(diǎn)地址（前驅(qū)指針prev）和下一個(gè)節(jié)點(diǎn)地址（后繼指針next）。
2）當(dāng)此“連接”為第一個(gè)“連接”時(shí)，指向空值或者空列表
當(dāng)此“連接”為最后一個(gè)“連接”時(shí)，指向空值或者空列表）
3）性能特點(diǎn)：
和單鏈表相比，存儲(chǔ)相同的數(shù)據(jù)，需要消耗更多的存儲(chǔ)空間。
插入、刪除操作比單鏈表效率更高O(1)級(jí)別。
以刪除操作為例，刪除操作分為2種情況：
給定數(shù)據(jù)值刪除對(duì)應(yīng)節(jié)點(diǎn)和給定節(jié)點(diǎn)地址刪除節(jié)點(diǎn)。
對(duì)于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進(jìn)行遍歷從而找到對(duì)應(yīng)節(jié)點(diǎn)進(jìn)行刪除，時(shí)間復(fù)雜度為O(n)。
對(duì)于第二種情況，要進(jìn)行刪除操作必須找到前驅(qū)節(jié)點(diǎn)，單鏈表需要從頭到尾進(jìn)行遍歷直到p->next = q，時(shí)間復(fù)雜度為O(n)，而雙向鏈表可以直接找到前驅(qū)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)。
對(duì)于一個(gè)有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。
因?yàn)槲覀兛梢杂涗浬洗尾檎业奈恢胮，每一次查詢時(shí)，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。
4.雙向循環(huán)鏈表（雙向，循環(huán)鏈表的結(jié)合）
首節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)。
5.塊狀鏈表
塊狀鏈表本身是一個(gè)鏈表，但是鏈表儲(chǔ)存的并不是一般的數(shù)據(jù)，而是由這些數(shù)據(jù)組成的順序表。每一個(gè)塊狀鏈表的節(jié)點(diǎn)，也就是順序表，可以被叫做一個(gè)塊。
塊狀鏈表通過使用可變的順序表的長度和特殊的插入、刪除方式，可以在達(dá)到{\displaystyle O({\sqrt {n}})}[圖片上傳失敗...(image-240dc2-1540194901507)]
的復(fù)雜度。塊狀鏈表另一個(gè)特點(diǎn)是相對(duì)于普通鏈表來說節(jié)省內(nèi)存，因?yàn)椴挥帽４嬷赶蛎恳粋€(gè)數(shù)據(jù)節(jié)點(diǎn)的指針。
四、數(shù)組VS鏈表
1.插入、刪除和隨機(jī)訪問的時(shí)間復(fù)雜度
數(shù)組：插入、刪除的時(shí)間復(fù)雜度是O(n)，隨機(jī)訪問的時(shí)間復(fù)雜度是O(1)。
鏈表：插入、刪除的時(shí)間復(fù)雜度是O(1)，隨機(jī)訪問的時(shí)間復(fù)雜端是O(n)。
2.數(shù)組缺點(diǎn)
1）若申請(qǐng)內(nèi)存空間很大，比如100M，但若內(nèi)存空間沒有100M的連續(xù)空間時(shí)，則會(huì)申請(qǐng)失敗，盡管內(nèi)存可用空間超過100M。
2）大小固定，若存儲(chǔ)空間不足，需進(jìn)行擴(kuò)容，一旦擴(kuò)容就要進(jìn)行數(shù)據(jù)復(fù)制，而這時(shí)非常費(fèi)時(shí)的。
3.鏈表缺點(diǎn)
1）內(nèi)存空間消耗更大，因?yàn)樾枰~外的空間存儲(chǔ)指針信息。
2）對(duì)鏈表進(jìn)行頻繁的插入和刪除操作，會(huì)導(dǎo)致頻繁的內(nèi)存申請(qǐng)和釋放，容易造成內(nèi)存碎片，如果是Java語言，還可能會(huì)造成頻繁的GC（自動(dòng)垃圾回收器）操作。
4.如何選擇
數(shù)組簡單易用，在實(shí)現(xiàn)上使用連續(xù)的內(nèi)存空間，可以借助CPU的緩沖機(jī)制預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高，而鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以對(duì)CPU緩存不友好，沒辦法預(yù)讀。
如果代碼對(duì)內(nèi)存的使用非?？量蹋菙?shù)組就更適合
CPU緩存機(jī)制指的是什么？為什么就數(shù)組更好了？
CPU在從內(nèi)存讀取數(shù)據(jù)的時(shí)候，會(huì)先把讀取到的數(shù)據(jù)加載到CPU的緩存中。而CPU每次從內(nèi)存讀取數(shù)據(jù)并不是只讀取那個(gè)特定要訪問的地址，而是讀取一個(gè)數(shù)據(jù)塊(這個(gè)大小我不太確定。。)并保存到CPU緩存中，然后下次訪問內(nèi)存數(shù)據(jù)的時(shí)候就會(huì)先從CPU緩存開始查找，如果找到就不需要再從內(nèi)存中取。這樣就實(shí)現(xiàn)了比內(nèi)存訪問速度更快的機(jī)制，也就是CPU緩存存在的意義:為了彌補(bǔ)內(nèi)存訪問速度過慢與CPU執(zhí)行速度快之間的差異而引入。
對(duì)于數(shù)組來說，存儲(chǔ)空間是連續(xù)的，所以在加載某個(gè)下標(biāo)的時(shí)候可以把以后的幾個(gè)下標(biāo)元素也加載到CPU緩存這樣執(zhí)行速度會(huì)快于存儲(chǔ)空間不連續(xù)的鏈表存儲(chǔ)。
相關(guān)文章
數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 從0編號(hào)的數(shù)組
以上內(nèi)容為個(gè)人的學(xué)習(xí)筆記，僅作為學(xué)習(xí)交流之用。
歡迎大家關(guān)注公眾號(hào)，不定時(shí)干貨，只做有價(jià)值的輸出
作者：Dawnzhang
出處：https://www.cnblogs.com/clwydjgs/p/9778394.html
版權(quán)：本文版權(quán)歸作者
轉(zhuǎn)載：歡迎轉(zhuǎn)載，但未經(jīng)作者同意，必須保留此段聲明；必須在文章中給出原文連接；否則必究法律責(zé)任
小舟從此逝，江海寄余生。 --狐貍
