第5章 1節
配列と連結リスト
プログラムで複数のデータを扱うとき、メモリ上の並べ方ひとつで読み書きや追加・削除の速度は劇的に変わります。この「データの整理整頓のルール」がデータ構造（Data Structure）です。最も基礎的でありながら対極に位置する「配列」と「連結リスト」の違いを見ていきましょう。
1. 配列（Array）：隣り合わせの連続配置
配列（Array）は、複数のデータをメモリ上の「連続した一続きの領域」に隙間なく順番に配置するデータ構造です。
アパートの部屋が 101号室、102号室、103号室と順番に並んでいるイメージです。
配列の長所と短所
- 長所：ランダムアクセスが極めて高速
データが連続しているため、「先頭アドレス ＋ データサイズ × インデックス」という計算だけで、何番目の要素でも瞬時（O(1)）にアクセスできます。 - 短所：データの挿入・削除が非常に遅い
先頭や途中に新しいデータを挿入する場合、それ以降のすべてのデータを1マスずつ後ろにずらす必要があり、データ数Nに比例した時間がかかります（O(N)）。また、後からサイズを増やしにくい弱点もあります。
2. 連結リスト（Linked List）：アドレスで繋ぐ芋づる式
連結リスト（Linked List）は、データをメモリ上のバラバラの位置に配置し、各データが「次のデータのアドレス（ポインタ）」を保持することで、チェーンのように繋ぎ合わせるデータ構造です。
連結リストを構成する個々の箱のことをノード（Node）と呼びます。ノードは「データ本体」と「次のノードを指すポインタ」のペアでできています。
連結リストの長所と短所
- 長所：データの挿入・削除が極めて高速
途中に新しいデータを挿入する場合、前後のノードのポインタを書き換えるだけで完了します。データをずらす必要はなく、常にO(1)で処理できます。空きメモリがある限り、サイズも自由に拡張できます。 - 短所：ランダムアクセスが不可能
データがメモリ上に散らばっているため、「5番目の要素」に直接ジャンプできません。先頭ノードからポインタを1つずつ順に辿る必要があり、アクセス速度はデータ数Nに比例して遅くなります（O(N)）。
3. どっちを使うべき？（トレードオフ）
配列と連結リストは、どちらが優れているというわけではなく、用途に応じたトレードオフの関係にあります。
| 操作・特性 | 配列（Array） | 連結リスト（Linked List） |
|---|---|---|
| メモリの物理配置 | 連続した一続きの空間 | バラバラ（順不同）の空間 |
| インデックスによるアクセス | 超高速（O(1)） | 遅い（O(N) / 順次検索が必要） |
| データの挿入・削除（途中） | 遅い（O(N) / データの移動が発生） | 超高速（O(1) / ポインタ書き換えのみ） |
| メモリのオーバーヘッド | なし（データのみ保持） | あり（ポインタを保持するための余分なメモリ） |
| サイズ変更の自由度 | 難しい（事前に最大サイズを決める必要あり） | 非常に自由（動的にノードを増やせる） |
例えば、「データの数が事前に決まっており、頻繁に中のデータを読み取る」ような用途（例：画像ピクセルデータやゲームのステージデータなど）には配列が適しています。
逆に、「データの数が予測できず、頻繁にデータの追加や削除が行われる」用途（例：ブラウザの履歴リストやテキストエディタのUndo/Redoバッファなど）には連結リストが適しています。
次のセクションでは、配列やリストにあえて制限をかけることで特定の処理をシンプルに解く「スタック」と「キュー」について学びます。