幾天前在 Twitter 上（啊，親愛的 Twitter：不管發生什麼事，我都會盡可能待在上面——如果你在乎那些為這個平台投入大量心力的人，離開前請三思）。總之，在 Twitter 上，我聊到了一個用 Rust 寫的、非常糟糕的鏈結串列實作。從某些回覆的語氣中，我感覺到很多人把鏈結串列當成一個笑話。一種微不足道的資料結構，只適合拿來應付面試，除此之外毫無用處。一言以蔽之：就是資料結構界的泡沫排序。我不這麼認為，所以想寫這篇部落格文章，來談談我喜歡鏈結串列的所有原因。

所以，準備好來讀一篇關於資料結構的多愁善感的文章吧，可別說我沒事先警告過你。

鏈結串列具有教育意義。當你的老師、或是一本書的某一頁、或是任何第一次讓你接觸到鏈結串列的東西，向你展示那個帶著箭頭指向另一個圓圈的小圓圈時，你的腦中會發生某種巨大的變化。就像你第一次搞懂遞迴時發生的事一樣。你會明白由連結所構成的資料結構真正的意義：單一節點的平凡，一旦指向另一個節點，就變得強大而複雜許多。鏈結串列向初學的程式設計師展示了關於計算中空間與時間的根本概念：如何能在常數時間內加入元素，以及順序本質上是昂貴的，因為如果你想把一個元素「就地」插入，就必須從一個節點走到另一個節點。你會立刻開始思考加速這個過程的方法（為接下來的學習做好準備），同時也能深刻地理解，O(1) 和 O(N) 真正代表的是什麼。

鏈結串列是可擴充的。加上一個指向上一個元素的指標，現在就能雙向走訪。不時加上一些「遠距」指標，你就得到了一個性質截然不同的跳躍串列。讓每個節點容納多個項目，你的鏈結串列就變成了展開式串列，提供了完全不同的快取特性。鏈結串列還可以被嵌入。舉例來說，Linux 核心就有巨集，可以在任何結構中加入一個欄位來把它們串在一起。還不只這樣：鏈結串列是可組合的。這是一個很強大的特性：你可以在 O(1) 時間內把一個鏈結串列拆成兩個，也可以在 O(1) 時間內把兩個鏈結串列接起來。如果善加利用這個特性，就能做到很有趣的事。舉例來說，在實作多執行緒操作的 Redis 模組中，處理慢速請求的執行緒會使用一個假的客戶端結構（這樣就不需要上鎖，也不會有競爭）。當多執行緒指令最終執行完畢時，客戶端的輸出緩衝區就可以直接拼接到真實客戶端的緩衝區上。之所以能這麼輕易做到，是因為輸出緩衝區就是用鏈結串列來表示的。

鏈結串列是有用的：或許 Redis 可能會搞錯，但 Redis 和 Linux 核心不可能同時都錯。它們之所以有用，是因為它們貼近某些自然的過程：按照到達的順序、或是相反的順序來加入東西，即使在現實世界中也是很自然的事。逐步取出項目也很有用，把這些項目從頭移到尾，或是移到目前位置的下一個位置，也同樣有用。

鏈結串列是簡單的。它是少數幾種稀有的資料結構之一，和二元樹、雜湊表以及其他幾種一樣，你光憑記憶就能實作出來，而且不太可能犯下大錯。

鏈結串列是概念性的。一個指向自己的節點，是我在計算領域能想像到最自我中心的事物：是更通俗的無窮迴圈最理想的體現。一個指向 NULL 的節點，則是孤獨的隱喻。而一個頭尾相連的鏈結串列，則是封閉循環的強大象徵。

基於所有這些理由，我熱愛鏈結串列，也希望你至少能開始對它們微笑。