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

というわけで、データ構造についての感傷的な投稿を読む心の準備をしてほしい。警告しなかったとは言わせないぞ。

連結リストは教育的だ。先生や本のページや、何であれ初めて連結リストに触れるきっかけが、矢印で別の丸につながった小さな丸を見せてくれたとき、頭の中で何か途方もなく大きなことが起こる。初めて再帰を理解したときに起こることとよく似ている。リンクでできたデータ構造が本当は何なのかがわかるのだ。一つだけでは取るに足らない単一のノードが、別のノードを参照した途端にはるかに強力で複雑なものになるということが。連結リストは、駆け出しのプログラマに計算における空間と時間の根源的なことを教えてくれる。要素を定数時間で追加できるということ、そして順序というものが根本的にコストがかかるということだ。なぜなら、ある要素を「あるべき場所」に挿入したいと思ったら、一つのノードから次のノードへと辿っていかなければならないからだ。すぐに、このプロセスをどうすれば速くできるか考え始めるようになる（それが次の学びへの準備になる）、そして同時に、O(1)やO(N)が本当に何を意味するのかを深く理解するのだ。

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

連結リストは有用だ。Redisが間違っていることはありうるが、RedisとLinuxカーネルの両方が間違っていることはありえない。有用なのは、ある種の自然なプロセスに似ているからだ。到着した順に、あるいは逆順にものを追加していくことは、現実の世界でも自然なことだ。要素を少しずつ取り出すことも有用だし、そうした要素を先頭から末尾へ移動させたり、現在の要素の直後に移動させたりすることも有用だ。

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

連結リストは概念的だ。自分自身を指すノードは、コンピューティングの中で想像しうる最も自己中心的なものだ。ありふれた無限ループを理想的に表現している。NULLを指すノードは孤独のメタファーだ。末尾と先頭がつながった連結リストは、閉じた循環の力強い象徴だ。

こうしたすべての理由から、僕は連結リストが大好きだ。そしてあなたも、少なくとも連結リストに微笑みかけるようになってくれることを願っている。