あなたは連結リストを使わない。しかし、ソフトウェアの半分はそれによって動いている。

Translated for your language. 原文を読む.

AI-assisted draft.

連結リストは使わない。しかし、それらはソフトウェアの半分を動かしている。

本番環境のJavaScriptプロジェクトで、連結リストを自分で実装することはまずありません。言語組み込みの配列の方が、動的なサイズ変更をより高速に処理できるからです。面接官はホワイトボードを使ってその作り方を教えますが、それは誤ったメンタルモデルを生み出すことになります。

連結リストは、実装するために学ぶべきではありません。毎日使っているツールを理解するために学ぶものなのです。

それらは至る所に存在します： • ブラウザの「戻る」と「進む」ボタン。 • テキストエディタのUndo（元に戻す）履歴。 • WebサーバーやデータベースにおけるLRUキャッシュ。 • Redisのlistコマンド。 • Linuxカーネルのプロセススケジューラ。

それらは遺物ではありません。インフラなのです。

連結リストが不利になる本当の理由は、キャッシュの局所性（cache locality）にあります。CPUはRAMを一度に1バイトずつ読み込むわけではありません。「キャッシュライン」と呼ばれる64バイトの塊をまとめて取り込みます。

配列が高速なのは、メモリ上に連続して配置されているからです。CPUが最初の要素を読み込むと、残りの15個もついでに手に入ります。

連結リストはこの利点を台無しにします。各ノードはメモリ上の異なる場所に存在します。ポインタを辿るたびに、CPUは新しいアドレスへジャンプすることを余儀なくされます。これにより、新たなRAMフェッチが発生し、数百のCPUサイクルを消費します。

モダンなハードウェアでは、配列の走査は連結リストの走査よりも10倍から100倍高速になることがあります。Big-O記法では、この定数コストは無視されてしまいます。

では、いつ使うのでしょうか？

片方の端からのみ追加または削除を行うスタックや、単純なタスクキューには、単方向連結リストを使用します。

ノードへの直接参照を用いてO(1)の削除が必要な場合は、双方向連結リストを使用します。これがLRUキャッシュの秘訣です。

LRUキャッシュには以下が必要です：

配列では、要素を移動させる際に他のすべての要素をずらす必要があるため、これは不可能です。また、ハッシュマップ単体でも、順序を持たないためこれは実現できません。

解決策は組み合わせです。ハッシュマップがルックアップを提供し、双方向連結リストが順序を維持します。ハッシュマップはノードへの参照を格納します。キーにアクセスすると、リストから直接ノードを取り出し、先頭に移動させます。探索も、ずらし処理も必要ありません。

面接に受かるためだけにデータ構造を学ぶのはやめましょう。ソフトウェアがどのようにハードウェアと相互作用するかを理解するために学ぶのです。