幾天前，我在 Twitter 上（噢，親愛的 Twitter：無論發生什麼事，我都會盡可能待在那裡——如果你在乎那些投入大量心力打造這個平台的人，離開前請三思）。所以，我在 Twitter 上談到一個用 Rust 寫的、非常糟糕的鏈結串列實作。從某些回覆的語氣看來，我感覺許多人把鏈結串列當成笑話。一種只適合用來應付程式面試、除此之外完全無用的平凡資料結構。一言以蔽之，就是資料結構界的氣泡排序。我不認同，所以想寫這篇部落格文章，細數我喜愛鏈結串列的一切。

所以，準備好來讀一篇關於資料結構的感性文章吧，別說我沒先提醒過你。

鏈結串列具有教育意義。當你的老師、或書本的某一頁、或是任何讓你第一次接觸鏈結串列的媒介，向你展示那個帶著箭頭指向另一個圓圈的小圓圈時，你的腦中會發生巨大的變化。那種感覺，就像你第一次理解遞迴時一樣。你會明白由連結所構成的資料結構真正的意義：單一節點的平凡，一旦指向另一個節點，便化為強大而複雜得多的整體。鏈結串列讓初學者深刻體會到運算中空間與時間的基本課題：如何在常數時間內新增元素，以及為何維持順序在本質上是昂貴的，因為如果你想「就地」插入一個元素，就必須逐一走訪節點。你會立刻開始思考加快這個過程的方法（為接下來的學習做好準備），同時也深刻理解了 O(1) 與 O(N) 真正的含義。

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

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

鏈結串列是簡單的。它是少數幾種罕見的資料結構之一，和二元樹、雜湊表等少數幾種一樣，你可以憑記憶就實作出來，而且不太會犯下嚴重的錯誤。

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

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