配列と連結リスト

配列と連結リストは、要素の順序付けられたシーケンスを格納する2つの基本的な方法です。配列は要素を連続したメモリに配置し、定数時間でのインデックスアクセスを可能にする一方、連結リストはポインタを介して要素を連結し、挿入と削除を低コストで行います。

Definition

配列は、要素を位置によってインデックス付けされた連続したメモリ位置に格納し、定数時間のランダムアクセスを可能にします。連結リストは、各要素が次の（そして場合によっては前の）ノードへの参照を保持する別々のノードに要素を格納し、ノード参照が与えられた場合に定数時間での挿入または削除を可能にします。

Scope

このトピックでは、線形なシーケンスベースの構造と、それら上に構築される抽象データ型（静的配列と動的配列、単方向および双方向連結リスト、スタックとキューADT）について扱います。アクセス、挿入、削除のコストを比較し、動的配列のリサイズとその償却解析、キャッシュ局所性などのメモリレイアウトの影響について説明します。ハッシュテーブルや探索木で扱われる連想構造や階層構造は除外します。

Core questions

• 連続した（配列）ストレージがポインタで連結された（リスト）ストレージよりも優れているのはどのような場合ですか？
• 動的配列は、時折リサイズが発生するにもかかわらず、どのようにして償却定数時間の追加を実現するのですか？
• 挿入、削除、アクセスに関して、配列と連結リストのコストトレードオフは何ですか？
• これらの構造の上にスタックとキューはどのように実装されますか？
• メモリレイアウトは、キャッシュの動作を通じて実際のパフォーマンスにどのように影響しますか？

Key concepts

• 連続メモリ
• インデックスアクセス
• 動的配列のリサイズ
• 単方向および双方向連結リスト
• スタック（LIFO）
• キュー（FIFO）
• 償却コスト
• キャッシュ局所性

Key theories

ランダムアクセスとシーケンシャルリンケージ

配列はO(1)のインデックスアクセスをサポートしますが、途中での挿入または削除はO(n)です。一方、連結リストはノードが与えられればO(1)の連結をサポートしますが、位置によるアクセスはO(n)です。適切な選択は、操作の組み合わせに依存します。

動的配列の償却成長

満杯になったときに容量を2倍にする動的配列は、時折O(n)のコピーを実行しますが、集計法またはポテンシャル法により、任意の操作シーケンス全体で追加あたりの償却コストはO(1)になります。

Clinical relevance

配列とリストは、ほぼすべてのプログラムの基盤です。動的配列はほとんどの言語でデフォルトのリスト/ベクター型を実装し、キューはスケジューリングと幅優先探索の基礎となり、スタックは関数呼び出し管理と式評価の基礎となります。また、配列とリストのトレードオフは、パフォーマンスに影響を与える日常的な実用的な設計上の決定事項です。

History

配列は最も初期のデータ構造の一つであり、最初のプログラミング言語に存在していました。連結リストは、1950年代後半に記号処理とリスト処理（特にNewell、Shaw、SimonのIPL、後にLisp）のために導入されました。Knuthの『The Art of Computer Programming』における体系的な扱いは、それらの標準的な解析を確立しました。

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

配列が高速なランダムアクセスをサポートするのに、なぜ連結リストを使用するのですか？

連結リストは、ノードへの参照が与えられた場合、他の要素をシフトすることなく定数時間で挿入または削除を可能にします。これは配列が途中で行うことができない操作です。シーケンスが頻繁に変更され、位置によるランダムアクセスが必要ない場合に役立ちます。

リサイズですべてがコピーされるのに、なぜ配列の追加は定数時間と見なされるのですか？

容量は通常2倍になるため、リサイズはめったに発生しません。したがって、n回の追加にわたる総コピー作業はnに比例します。すべての追加に分散すると、個々のリサイズはO(n)であるにもかかわらず、追加あたりの償却定数コストが得られます。