對(duì)于不少開發(fā)者而言，鏈表(linked list)這種數(shù)據(jù)結(jié)構(gòu)既熟悉又陌生，熟悉是因?yàn)樗_實(shí)是非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，陌生的原因是我們在業(yè)務(wù)開發(fā)中用到它的幾率的確不大。

在很多情況下，我們用數(shù)組就能很好的完成工作，而且不會(huì)產(chǎn)生太多的差異，那么鏈表存在的意義是什么？鏈表相比于數(shù)組有什么優(yōu)勢或者不足嗎？

什么是鏈表

鏈表是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。

從本質(zhì)上來講,鏈表與數(shù)組的確有相似之處，他們的相同點(diǎn)是都是線性數(shù)據(jù)結(jié)構(gòu)，這與樹和圖不同，而它們的不同之處在于數(shù)組是一塊連續(xù)的內(nèi)存，而鏈表可以不是連續(xù)內(nèi)存，鏈表的節(jié)點(diǎn)與節(jié)點(diǎn)之間通過指針來聯(lián)系。

當(dāng)然,鏈表也有不同的形態(tài)，主要分為三種：單向鏈表、雙向鏈表、循環(huán)鏈表。

單向鏈表

單向鏈表的節(jié)點(diǎn)通常由兩個(gè)部分構(gòu)成，一個(gè)是節(jié)點(diǎn)儲(chǔ)存的值val，另一個(gè)就是節(jié)點(diǎn)的指針next。

鏈表與數(shù)組類似,也可以進(jìn)行查找、插入、刪除、讀取等操作，但是由于鏈表與數(shù)組的特性不同，導(dǎo)致不同操作的復(fù)雜度也不同。

查找性能

單向鏈表的查找操作通常是這樣的：

（1）從頭節(jié)點(diǎn)進(jìn)入，開始比對(duì)節(jié)點(diǎn)的值，如果不同則通過指針進(jìn)入下一個(gè)節(jié)點(diǎn)

（2）重復(fù)上面的動(dòng)作，直到找到相同的值，或者節(jié)點(diǎn)的指針指向null

鏈表的查找性能與數(shù)組一樣，都是時(shí)間復(fù)雜度為O(n)。

插入刪除性能

鏈表與數(shù)組最大的不同就在于刪除、插入的性能優(yōu)勢，由于鏈表是非連續(xù)的內(nèi)存，所以不用像數(shù)組一樣在插入、刪除操作的時(shí)候需要進(jìn)行大面積的成員位移，比如在a、b節(jié)點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)c，鏈表只需要：

a斷開指向b的指針，將指針指向c

c節(jié)點(diǎn)將指針指向b，完畢

這個(gè)插入操作僅僅需要移動(dòng)一下指針即可，插入、刪除的時(shí)間復(fù)雜度只有O(1).

鏈表的插入操作如下：

鏈表的刪除操作如下：

讀取性能

鏈表相比之下也有劣勢，那就是讀取操作遠(yuǎn)不如數(shù)組，數(shù)組的讀取操作之所以高效，是因?yàn)樗且粔K連續(xù)內(nèi)存，數(shù)組的讀取可以通過尋址公式快速定位，而鏈表由于非連續(xù)內(nèi)存，所以必須通過指針一個(gè)一個(gè)節(jié)點(diǎn)遍歷。

比如,對(duì)于一個(gè)數(shù)組，我們要讀取第三個(gè)成員，我們僅需要arr[2]就能快速獲取成員，而鏈表則需要從頭部節(jié)點(diǎn)進(jìn)入，在通過指針進(jìn)入后續(xù)節(jié)點(diǎn)才能讀取。

應(yīng)用場景

由于雙向鏈表的存在，單向鏈表的應(yīng)用場景比較少，因?yàn)楹芏鄨鼍半p向鏈表可以更出色地完成。

但是單向鏈表并非無用武之地，在以下場景中依然會(huì)有單向鏈表的身影：

（1）撤銷功能，這種操作最多見于各種文本、圖形編輯器中，撤銷重做在編輯器場景下屬于家常便飯，單向鏈表由于良好的刪除特性在這個(gè)場景很適用。

（2）實(shí)現(xiàn)圖、hashMap等一些高級(jí)數(shù)據(jù)結(jié)構(gòu)

雙向鏈表

我們上文已經(jīng)提到，單向鏈表的應(yīng)用場景并不多，而真正在生產(chǎn)環(huán)境中被廣泛運(yùn)用的正是雙向鏈表。

雙向鏈表與單向鏈表相比有何特殊之處？

我們看到雙向鏈表多了一個(gè)新的指針prev指向節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn),當(dāng)然由于多了一個(gè)指針，所以雙向鏈表要更占內(nèi)存。

別小看雙向鏈表多了一個(gè)前置指針，在很多場景里由于多了這個(gè)指針，它的效率更高，也更加實(shí)用。

比如編輯器的「undo/redo」操作，雙向鏈表就更加適用，由于擁有前后指針，用戶可以自由得進(jìn)行前后操作，如果這個(gè)是一個(gè)單向鏈表，那么用戶需要遍歷鏈表這時(shí)的時(shí)間復(fù)雜度是O(n)。

真正生產(chǎn)級(jí)應(yīng)用中的編輯器采用的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)模式更加復(fù)雜，比如Word就是采用Piece Table數(shù)據(jù)結(jié)構(gòu)加上Command queue模式實(shí)現(xiàn)「undo/redo」的，不過這是后話了。

循環(huán)鏈表

循環(huán)鏈表,顧名思義，他就是將單向鏈表的尾部指針指向了鏈表頭節(jié)點(diǎn)：

循環(huán)鏈表一個(gè)應(yīng)用場景就是操作系統(tǒng)的分時(shí)問題，比如有一臺(tái)計(jì)算機(jī)，但是有多個(gè)用戶使用，CPU要處理多個(gè)用戶的請求很可能會(huì)出現(xiàn)搶占資源的情況，這個(gè)時(shí)候計(jì)算機(jī)會(huì)采取分時(shí)策略來保證每個(gè)用戶的使用體驗(yàn)。

每個(gè)用戶都可以看成循環(huán)鏈表上的節(jié)點(diǎn)，CPU會(huì)給每個(gè)節(jié)點(diǎn)分配一定的處理時(shí)間，在一定的處理時(shí)間后進(jìn)入下一個(gè)節(jié)點(diǎn),然后無限循環(huán)，這樣可以保證每個(gè)用戶的體驗(yàn)，不會(huì)出現(xiàn)一個(gè)用戶搶占CPU而導(dǎo)致其他用戶無法響應(yīng)的情況。

當(dāng)然，約瑟夫環(huán)的問題是單向循環(huán)鏈表的代表性應(yīng)用，感興趣的可以深入了解下。

當(dāng)然如果是雙向鏈表首尾相接呢？這就是雙向循環(huán)鏈表。

在Node中有一類場景，沒有查詢，但是卻有大量的插入和刪除，這就是Timer模塊。

幾乎所有的網(wǎng)絡(luò)I/O請求，都會(huì)提供timeout操作控制socket的超時(shí)狀況，這里就會(huì)大量使用到setTimeout，并且這些timeout定時(shí)器，絕大部分都是用不到的（數(shù)據(jù)按時(shí)正常響應(yīng)），那么又會(huì)有響應(yīng)的大量clearTimeout操作，因此node采用了雙向循環(huán)鏈表來提高Timer模塊的性能,至于其中的細(xì)節(jié)就不再贅述了。

【代碼】

小結(jié)

至此,我們對(duì)鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)知,由于其非連續(xù)內(nèi)存的特性導(dǎo)致鏈表非常適用于頻繁插入、刪除的場景，而不見長于讀取場景，這跟數(shù)組的特性恰好形成互補(bǔ)，所以現(xiàn)在也可以回到題目中的問題了，鏈表的特性與數(shù)組互補(bǔ)，各有所長，而且鏈表由于指針的存在可以形成環(huán)形鏈表，在特定場景也非常有用，因此鏈表的存在是很有必要的。

作者：尋找海藍(lán)96

另外的話為了幫助大家，輕松，高效學(xué)習(xí)C語言/C++，我給大家分享我收集的資源，從最零基礎(chǔ)開始的教程到C語言項(xiàng)目案例，幫助大家在學(xué)習(xí)C語言的道路上披荊斬棘！

整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）