数日前、Twitterで（ああ、愛しのTwitterよ。何が起ころうとも、できる限りそこに留まるつもりです。もしプラットフォームを作ることに多大なエネルギーを注いできた人々のことを思うなら、離れる前にもう一度考えてみてください）、Rustで書かれたとても出来の悪い連結リストの実装について話していました。返信の調子から、多くの人が連結リストを冗談のように捉えていると感じました。コーディング面接のためだけにある取るに足らないデータ構造で、それ以外ではまったく役に立たないものだと。一言でいえば、データ構造界のバブルソートです。私はそうは思いません。だからこそ、連結リストの好きなところを詰め込んだこのブログ記事を書こうと思いました。

ですから、これからデータ構造への愛を語る少々感傷的な記事を覚悟してください。警告しなかったとは言わせませんよ。

連結リストは教育的です。先生や本のページ、あるいは何かしらのきっかけで初めて連結リストに触れ、小さな丸から別の丸へ矢印が伸びている図を見たとき、頭の中でとてつもないことが起こります。初めて再帰を理解したときの感覚に似ています。リンクで構成されたデータ構造が本当は何なのかが分かるのです。一つひとつのノードは取るに足らない存在ですが、別のノードを参照することで、はるかに強力で複雑なものになるのだと。連結リストは、計算における空間と時間について根本的なことを教えてくれます。要素を定数時間で追加できること。そして、順序というものが本質的にコストを伴うこと。なぜなら、ある要素を「本来の位置」に挿入したいなら、一つひとつのノードをたどっていかなければならないからです。すぐに、その処理を速くする方法を考え始めます（それが次の学びへの準備になります）。同時に、O(1)やO(N)が本当は何を意味するのかを、深く理解できるようになります。

連結リストは拡張可能です。前の要素へのポインタを一つ追加すれば、両方向にたどれるようになります。ときどき「遠く」へのポインタを加えれば、まったく異なる特性を持つスキップリストになります。各ノードが複数の要素を持つように変えれば、連結リストはアンロールド連結リストとなり、キャッシュ効率の面でまったく異なる性質を示します。連結リストは埋め込むこともできます。たとえばLinuxカーネルには、あらゆる構造体にフィールドを追加してそれらを相互に連結するためのマクロが用意されています。さらにあります。連結リストは合成可能です。これは大胆な特性です。連結リストを二つに分割するのもO(1)でできますし、二つの連結リストを一つにつなぎ合わせるのもO(1)でできます。この性質を賢く使えば、面白いことが可能になります。たとえば、スレッドを使った処理を実装したRedisモジュールでは、重いリクエストを処理するスレッドが偽のクライアント構造体を扱っていました（そうすることでロックも競合も不要になります）。スレッドでのコマンド実行が最終的に終わったとき、そのクライアントの出力バッファを、本物のクライアントの実際のバッファへとつなぎ合わせることができました。出力バッファが連結リストで表現されていたからこそ、簡単にできたことでした。

連結リストは有用です。Redisが間違っていることはあっても、RedisとLinuxカーネルの両方が間違っているということはありません。有用である理由は、ある種の自然な過程によく似ているからです。届いた順に、あるいは逆順にものを追加していくのは、現実世界でも自然なことです。要素を一つずつ取り出していくことや、そうした要素を先頭から末尾へ、あるいは現在の位置のすぐ後ろへと移動させることもまた有用です。

連結リストはシンプルです。二分木やハッシュテーブルなどと並んで、記憶だけを頼りに実装しても大きな間違いを犯さずに書き上げられる、数少ないデータ構造の一つです。

連結リストは概念的です。自分自身を指すノードほど、計算の世界で自己中心的なものを私は想像できません。あの低俗な無限ループを理想的に表現したものです。NULLを指すノードは、孤独のメタファーです。末尾と先頭がつながった連結リストは、閉じた円環という力強い象徴です。

そうしたすべての理由から、私は連結リストが大好きです。皆さんも、せめて連結リストに微笑みかけてくれるようになることを願っています。