（小伙伴們，準(zhǔn)備好閱讀一篇關(guān)于鏈表的“情詩(shī)”吧！感謝張同學(xué)和岳老師對(duì)翻譯工作的貢獻(xiàn)與指導(dǎo)）

鏈表具有教育意義

當(dāng)從老師、教材等資料那里第一次接觸到鏈表的時(shí)候，帶有箭頭的圓圈通過(guò)箭頭指向另一個(gè)圓圈，你的腦海中自然會(huì)建立對(duì)應(yīng)的構(gòu)圖。就像你第一次對(duì)遞歸有所理解時(shí)候的體悟。你會(huì)感受到由鏈接而成數(shù)據(jù)結(jié)構(gòu)的真正要義：不起眼的單個(gè)節(jié)點(diǎn)，一旦它指向另一個(gè)節(jié)點(diǎn)，就會(huì)被賦予更強(qiáng)的能力和更高的復(fù)雜度。鏈表為新手程序員很好地引入了計(jì)算中關(guān)于空間和時(shí)間的基本知識(shí)：你會(huì)思考如何高效添加元素，思考順序存儲(chǔ)所帶來(lái)的代價(jià)。因?yàn)槿绻朐谔囟ㄎ恢貌迦胍粋€(gè)元素，那么必須從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)按順序遍歷，由此你會(huì)馬上轉(zhuǎn)而思考加快執(zhí)行的方法（為接下來(lái)的任務(wù)做好準(zhǔn)備），同時(shí)也能夠深入地理解了?O?(1) 和?O?(N) 的真正含義。

鏈表是可擴(kuò)展的

可以添加指向前一個(gè)元素的指針，也可以添加指向后一個(gè)元素是指針，鏈表支持雙向訪問(wèn)。再添加“遠(yuǎn)”指針，可以在鏈表內(nèi)部跳躍訪問(wèn)。除此之外，還可以對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行更改，容納多個(gè)屬性和操作，進(jìn)而拓充功能，擁有不同的存儲(chǔ)策略。鏈表同時(shí)也支持嵌入。例如，Linux 內(nèi)核具有宏，能夠?qū)⒆侄翁砑拥饺魏谓Y(jié)構(gòu)體，進(jìn)而組成鏈表。這是鏈表的一個(gè)?bold?屬性：可以在?O?(1) 復(fù)雜度內(nèi)將一個(gè)鏈表拆分為兩個(gè)，也可以在?O?(1)復(fù)雜度內(nèi)將兩個(gè)鏈表融合在一起。如果巧妙利用這個(gè)屬性，可以完成很多有意思的任務(wù)。例如，在 Redis 模塊中進(jìn)行線程操作，處理慢速請(qǐng)求的線程處理了一個(gè)偽造的客戶端結(jié)構(gòu)體（沒(méi)有鎖，沒(méi)有爭(zhēng)用），當(dāng)線程指令最終結(jié)束執(zhí)行時(shí)，偽造客戶端的輸出緩沖區(qū)可以鏈接到真實(shí)客戶端的緩沖區(qū)中。因?yàn)檩敵鼍彌_區(qū)是用鏈表表示的，使得這種操作簡(jiǎn)單易行。

鏈表很有用

Redis 可能會(huì)出錯(cuò)，但 Redis 和 Linux 內(nèi)核不會(huì)。它們就這樣自然而然地發(fā)生了：按照它們到達(dá)的順序，或者相反的順序依次添加。以增量方式拉動(dòng)項(xiàng)目也很有用，因?yàn)樗鼤?huì)將這些項(xiàng)目從頭到尾移動(dòng)，或者將它們移動(dòng)到當(dāng)前項(xiàng)目之后的位置。鏈表很簡(jiǎn)單它是稀有的，遇見(jiàn)“她”花費(fèi)了我不少運(yùn)氣。與二叉樹(shù)、哈希表等結(jié)構(gòu)一起，可以僅從內(nèi)存中實(shí)現(xiàn)，且不會(huì)出現(xiàn)什么大問(wèn)題。

鏈表是概念性的

指向自身的節(jié)點(diǎn)是我能想象到的計(jì)算中最以自我為中心的東西：更粗俗的無(wú)限循環(huán)的理想表示。指向?NULL?的節(jié)點(diǎn)是孤獨(dú)的隱喻。首尾相連的鏈表，是閉環(huán)的有力象征。所以，我深愛(ài)著鏈表，多么希望你也能喜歡“她”，至少，從今天開(kāi)始，可以給“她”一個(gè)微笑！

大家學(xué)習(xí)鏈表的時(shí)候，是怎樣去理解它的呢？

“一般都和數(shù)組一起！”

沒(méi)錯(cuò)，我們來(lái)對(duì)比看看數(shù)組和鏈表的區(qū)別~

假設(shè)我們要存儲(chǔ)一份有 3 個(gè)項(xiàng)目的待辦清單：

如果使用數(shù)組，占用連續(xù)的存儲(chǔ)空間，那么它存在內(nèi)存里是這樣的：

如果使用鏈表，每個(gè)項(xiàng)目可以存在內(nèi)存的任何地方，就是這樣的：

顯然，數(shù)組看起來(lái)更好理解。但是假設(shè)你現(xiàn)在要加入第 4 個(gè)待辦項(xiàng)目，放在哪里呢？這時(shí)就需要重新找到一個(gè)可以連續(xù)放 4 個(gè)項(xiàng)目的位置，添加第 5 個(gè)項(xiàng)目時(shí)呢？還需要重新找。太麻煩了，雖然我們可以通過(guò)提前預(yù)留位置來(lái)減少移動(dòng)這份清單的次數(shù)，但還是避免不了浪費(fèi)位置的情況。鏈表就不同了，它更像一個(gè)尋寶游戲，每個(gè)格子里寫著下一個(gè)格子位置的“線索”，只要內(nèi)存里還有位置，就可以無(wú)限添加，不用移動(dòng)已經(jīng)存好的數(shù)據(jù)。鏈表完美了嗎？當(dāng)然不是！
排行榜網(wǎng)站總是使用“卑鄙”的手段來(lái)增加頁(yè)面瀏覽量。比如“十大電視反派”排行，它不在一個(gè)頁(yè)面中顯示整個(gè)排行榜，而是 TOP10 在第 1 頁(yè)，剩下 9 個(gè)都單獨(dú)放在一個(gè)頁(yè)面中，讓你不停地單擊“Next”才能看到第一大反派，好讓這 10 個(gè)頁(yè)面中的廣告都增加展示次數(shù)，真是煩！

鏈表就存在類似的問(wèn)題。如何解決呢？聰明的你快來(lái)評(píng)論區(qū)聊聊吧！數(shù)據(jù)結(jié)構(gòu)魅力無(wú)限，僅僅是數(shù)組和鏈表就有這么多精彩的細(xì)節(jié)，想要了解更多有趣的數(shù)據(jù)結(jié)構(gòu)和算法故事？下面兩本書推薦給大家！

第 1 本

第?2?本

這兩本書

雙十一期間 5 折直降！

錯(cuò)過(guò)等一年！

關(guān)注圖靈社區(qū)

10號(hào)程序員專場(chǎng)圖書