List（リスト）とは｜配列ベースと連結リストの性能比較・実装上の注意と最適な選び方

2025年11月18日 最終更新日時 : 2025年11月18日 エバープレイ編集部

List とは — 概念と定義

ITやプログラミングにおける「List（リスト）」は、複数の要素を順序付けて保持するデータ構造（抽象データ型：ADT）を指します。要素の重複を許すことが多く、順序（インデックスや連結の順）が意味を持ちます。一般的な操作には「要素の参照（アクセス）」「探索」「挿入」「削除」「走査（イテレーション）」などが含まれます。

List の主な種類（実装観点）

  • 配列ベース（Dynamic Array / ArrayList 等）
    内部的に要素を連続したメモリ領域に格納する実装です。インデックスによるランダムアクセスがO(1)で高速、追加は末尾なら平均O(1)（増加時は再割当でO(n)）です。例：C++のstd::vector、JavaのArrayList、Pythonのlist。

  • 連結リスト（Linked List）
    各ノードが次（および場合によっては前）への参照を持つ実装。挿入・削除はノード参照が分かっていればO(1)で行えますが、ランダムアクセスはO(n)です。例：単方向（singly）・双方向（doubly）・循環（circular）等。

  • 言語固有・高度実装
    関数型言語の不変（immutable）リスト（Lispのcons-listやHaskellのリスト）、Clojureの永続データ構造、チャンク化リストやロープ（長いテキスト向け）など、用途や性能要件に応じた派生実装があります。

List（配列ベース）と連結リストの比較（主な操作と計算量）

一般的な比較（nは要素数、kは位置）：

  • インデックスによるランダムアクセス：配列 O(1)、連結リスト O(n)
  • 末尾への追加：配列 O(1)（平均／アモータイズド）、連結リスト O(1)（末尾ポインタがある場合）
  • 先頭への追加：配列 O(n)（シフトが必要）、連結リスト O(1)
  • 中間位置への挿入／削除：配列 O(n)（シフト）、連結リスト O(1)（操作対象のノード参照が既にある場合）、ただし位置の探索は O(n)
  • メモリ使用：配列は要素のみ（連続領域）、連結リストは各ノードごとの参照（ポインタ）と分散した割当のためオーバーヘッドが大きい
  • キャッシュ効率：配列は連続配置によりキャッシュ局所性が高く高速化されやすい

実装上の注意点とパフォーマンス要因

  • アロケーションと容量戦略
    動的配列は成長時に新しいより大きな領域を割り当ててコピーするため、成長率（例：1.5倍や2倍）が性能に影響します。これにより「アモータイズド」な挿入コストが保証されます。

  • メモリの断片化とオーバーヘッド
    連結リストは各ノードが別々にヒープ割当されるため、メモリ断片化や管理コスト、ガベージコレクション負荷が増えることがあります。

  • キャッシュ効率
    連続したメモリに格納される配列はCPUキャッシュの恩恵を受けやすく、同じ計算量でも実行時性能で有利なことが多いです。

  • イテレータと不変性（Concurrent / Immutable）
    多くの言語実装では、コレクションの変更がイテレータの整合性を乱すと例外を投げたり（JavaのConcurrentModificationException）、コピーオンライト／不変データ構造を使用してスレッド安全性を確保します。

主要言語におけるListの代表例

  • Python
    Pythonのlistは動的配列で、添字アクセスはO(1)、appendはアモータイズドO(1)、insert/removalは位置によりO(n)。ドキュメント：https://docs.python.org/3/tutorial/datastructures.html#more-on-lists

  • Java
    java.util.Listはインターフェースで、主要実装にArrayList（動的配列）とLinkedList（双方向連結リスト）がある。ArrayListはランダムアクセス高速、LinkedListは頻繁な先頭挿入／削除が得意。API：https://docs.oracle.com/javase/8/docs/api/java/util/List.html

  • C++
    std::vector（連続メモリ、配列様）とstd::list（双方向連結リスト）、std::forward_list（単方向）の違いが明確。参考：https://en.cppreference.com/w/cpp/container/vector

  • 関数型言語
    Lisp系やHaskellのリストは不変の連結リスト（consセル）が標準。先頭へのconsはO(1)で効率的に扱えるが、ランダムアクセスは非効率。

設計上の選択指南（いつどのListを選ぶか）

  • ランダムアクセスが多い／要素数が大きくCPUキャッシュ利用を重視するなら配列ベース（ArrayList, vector）。
  • 頻繁に要素を挿入・削除する（特に先頭付近・既知のノード参照がある）場合は連結リストが有利。
  • スレッド共有／不変性が重要なら不変（persistent）なリストやコピーオンライト実装を検討する。
  • 文字列や大きなテキスト編集などでは、ロープやギャップバッファなど特殊な「リスト」実装が有利な場合がある。

高度なトピック（永続データ構造／並行処理／特殊用途）

  • 永続（Persistent）リスト
    関数型言語やClojureのように、変更操作が新しいバージョンを効率的に作るデータ構造。共有部分を保ちながら不変性を確保します（例：Clojureのpersistent vectorsやlists）。

  • ロックフリー／並列リスト
    同時並行処理下でのリスト操作は、ロックを使わないアルゴリズム（CASを用いた）や高度な同期構造を使うことでスケーラブルに設計できますが実装は難しいです。

  • シリアライズと永続化
    多くの環境ではListはJSONの配列やデータベースの正規化テーブルとして表現されます。DB設計では「配列列」と「関連テーブル」の使い分け、バージョン管理や互換性に注意が必要です。

まとめ

「List」とは単に「複数要素を順序付けて扱う」概念ですが、実際には用途に応じて様々な実装やトレードオフがあります。配列ベースはランダムアクセスやキャッシュ効率に優れ、連結リストは特定の挿入／削除で有利、不変リストや永続構造は並行性や履歴管理で価値を発揮します。実運用では、期待される操作パターン（アクセス頻度、挿入削除の位置、スレッド環境、メモリ制約）を見極めて実装を選ぶことが重要です。

参考文献

カテゴリー
IT
前の記事
配列（Array）とは｜メモリ配置・性能・静的／動的・多次元の違いと実践的な使い分けガイドNew!!
2025年11月18日
次の記事
Hariprasad Chaurasia（ハリプラサド・チャウラシア）完全ガイド：バンスリ名盤・演奏スタイルと聴きどころNew!!
2025年11月18日