😎 「リンクリストはもう使われない」のか？

📌 この記事は Zenn に投稿した内容のアーカイブです。

――2026年のハードウェア前提で考えるデータ構造の現実

エンジニア向けの記事や SNS で、
「リンクリストはもう終わった」
という表現を見かけることがあります。

最初にこの話を聞いたとき、正直かなり極端だなと思いました。
ただ、実務でパフォーマンスを意識した設計や実装を重ねていくと、この言い方が完全に間違っているとも言い切れない 、という感覚になってきます。

この記事では、「リンクリストがなぜ避けられるようになったのか」「それでも今なお使われ続けている理由」を、現代の CPU・メモリ構成を前提に 整理してみます。

教科書的な理解と、現実のズレ

学生時代にデータ構造を学んだとき、ほとんどの人が次のように習ったはずです。

• 配列：途中への挿入・削除は O(N)

• リンクリスト：挿入・削除は O(1)

理論としては正しいです。
ただし、ここには重要な前提条件 があります。

メモリアクセスのコストはすべて同じである

現実のハードウェアでは、これは成立しません。

キャッシュ階層という「無視できない現実」

現代の CPU では、メモリは階層構造になっています。

• L1 キャッシュ：数サイクル

• L2 キャッシュ：十数サイクル

• L3 キャッシュ：数十サイクル

• メインメモリ（RAM）：数百サイクル

この差は無視できるものではありません。
特に問題になるのが、アクセスパターンが予測できない場合 です。

リンクリストが不利になる理由

典型的なリンクリストは、ノードがメモリ上に散らばって配置されます。

Node A -> Node B -> Node C

見た目はシンプルですが、実際のアドレスは次のようになっているかもしれません。

0x1000 -> 0x8F20 -> 0x3A10

リンクリストを走査する場合、

1. 現在のノードを読み込む

2. next ポインタを読む

3. 次のアドレスが分かってから、次の読み込みを行う

という強い依存関係のある処理 になります。

CPU のプリフェッチ機構は、連続したアクセス（配列など）は得意ですが、
リンクリストのようなポインタ追跡はほとんど先読みできません。

結果として、キャッシュミスが頻発 します。

配列（vector）が速い本当の理由

std::vector や配列を順番に処理しているとき、
実際には CPU はすでに次のデータをキャッシュに読み込んでいます。

つまり私たちは、

• メモリを読んでいるつもりでも

• 実際にはキャッシュを読んでいる時間がほとんど

という状態になります。

この差は、データ量が数千～数万程度でもはっきり現れます。

「O(1) の挿入」は実務では罠になる

リンクリストの O(1) 挿入は、すでに挿入位置のノードを持っている ことが前提です。

現実のコードでは、

• 挿入位置を探すために走査が必要

• ノード生成のためにメモリ確保が発生

• アロケータのオーバーヘッド

• キャッシュのコールドスタート

といったコストが重なります。

実際、要素数がそれほど多くない場合は、
vector の memmove のほうが速いケースは珍しくありません。

それでもリンクリストは「消えていない」

では、リンクリストは完全に不要になったのでしょうか。

答えは No です。

ただし、使われるレイヤーが変わりました。

侵入型リスト（Intrusive List）

Linux カーネルなどで多用されているのが、侵入型リストです。

これは、

• ノードを別途確保しない

• 構造体の中に next / prev を直接持たせる

という設計です。

この方式では、

• 追加・削除でメモリ確保が発生しない

• オブジェクトが複数のリストに同時に属せる

といった利点があります。

カーネルや低レイヤーでは、今でも不可欠な構造です。

並行処理・ロックフリー構造

マルチスレッド環境では、配列は扱いづらくなります。

途中への挿入・削除では、

• 広範囲の要素移動が必要

• 大きなロックが必要

一方、リンクリストは局所的な更新が可能です。

CAS（Compare-And-Swap）命令を使えば、
ロックフリーキューやスタックを実装できます。

Michael-Scott Queue など、実績のあるアルゴリズムの多くは
リンク構造をベースにしています。

メモリアロケータの内部でも使われている

malloc の実装（glibc / jemalloc / tcmalloc）では、
空きメモリ管理にリンクリストが使われています。

空いているメモリ自身にポインタを持たせることで、
追加の管理領域を不要にしているのです。

この用途では、リンクリストは非常に理にかなっています。

データ指向設計とリンクリスト

近年、ゲーム開発を中心に
Data-Oriented Design（DOD） が広く使われています。

Unity の ECS などが典型例ですが、

• データをオブジェクト単位でまとめない

• 同種のデータを連続した配列で持つ

という設計です。

この思想では、リンクリストは明確に不利です。
キャッシュ効率を最優先するためです。

配列でリンクを表現するという妥協点

最近よく使われる手法として、

• ポインタではなくインデックスを使う

• 大きな配列をオブジェクトプールとして使う

という設計があります。

これは、

• 物理的には配列（連続メモリ）

• 論理的にはリンク構造

という折衷案です。

Rust や Zig の文化とも相性が良く、
高性能なシステムでよく見かける形です。

結論：リンクリストは「役割が変わった」

• アプリケーション層の汎用コンテナとしてのリンクリスト
  → ほぼ使われなくなった

• システム・低レイヤー・並行処理・メモリ管理
  → 今も現役

「リンクリストはもう使わない」という言葉は、
無条件に否定すべきものではありません 。

それは、

抽象だけを信じて、ハードウェアを無視するな

という警告として受け取るのが、ちょうど良いと思います。

これからコードを書くとき、
少しだけキャッシュラインやメモリアクセスを意識すると、
データ構造の選び方が変わってくるはずです。