データ構造入門：Array と List
「並んだデータ」をどう持つか — 配列と連結リストの違い、使い分けの考え方、そして Java の ArrayList / LinkedList の中身まで
配列（Array）：連続した部屋に並べる
プログラムで「たくさんのデータを順番に持ちたい」とき、いちばん基本になるのが配列です。配列は、メモリ上に連続した領域を確保して、データを隙間なく並べます。
index : 0 1 2 3 +------+------+------+------+ array : | 10 | 20 | 30 | 40 | +------+------+------+------+ address: 100 104 108 112 (int = 4 バイトの場合) a[2] のアドレス = 100 + 2 * 4 = 108 → 計算一発で届く: O(1)
連続して並んでいるおかげで、「i 番目」の場所は計算一発で求まります（先頭アドレス + i × 要素サイズ）。だから添字によるアクセスは、データが何個あっても一定時間 O(1) です。
弱点は、確保した長さをあとから変えられないことです。そして途中に 1 つ挿入するには、それより後ろの要素をすべて 1 つずつずらす必要があります。
連結リスト（Linked List）：矢印でつなぐ
連結リストは、値と「次のノードへの参照（矢印）」をセットにしたノードを、鎖のようにつないだ構造です。配列と違って、メモリ上の場所はバラバラで構いません。
head | v +------+------+ +------+------+ +------+------+ | 10 | next-+---> | 20 | next-+---> | 30 | null | +------+------+ +------+------+ +------+------+ i 番目に届くには先頭から辿るしかない: O(n)
強みは書き換えです。場所さえ分かっていれば、挿入も削除も矢印をつなぎ替えるだけで済み、後ろの要素をずらす必要がありません。その代わり「i 番目」へ行くには先頭から順に辿るしかなく、データの個数に比例した時間がかかります（データが n 個あるとき、これを O(n) と書きます）。
用語に注意：「リスト」は言語によって意味が違う
Python の list は、名前に反して中身は「自動で伸びる配列」（動的配列 — 次の章で説明します）です。Java の List はインターフェースの名前で、データ構造そのものではありません（後述します）。この記事では「リスト」を連結リストの意味で使います。
計算量で比べる
実際のプログラミングでは、配列に「自動で伸びる」便利さを足した動的配列（Java の ArrayList、Python の list など）をよく使います。3 つを並べて、主な操作の計算量 — データが n 個のとき、処理時間がどう増えるかの目安 — を比べてみましょう。なお、実用的な連結リスト（Java の LinkedList など）は先頭だけでなく末尾への参照も持っているため、末尾への追加は辿らずに O(1) でできます。
| 項目 | 配列（固定長） | 動的配列（ArrayList） | 連結リスト（LinkedList） |
|---|---|---|---|
| i 番目へのアクセス | O(1) | O(1) | O(n) |
| 末尾への追加 | —（長さ固定） | ならし O(1) | O(1) |
| 先頭への挿入 | O(n)（空きがある場合） | O(n) | O(1) |
| 途中への挿入・削除 | O(n)（空きがある場合） | O(n) | つなぎ替えは O(1)（位置まで辿るのに O(n)） |
| メモリの持ち方 | 連続・むだなし | 連続・予備領域あり | 散らばる・参照の分だけ余分 |
動的配列の「末尾への追加」が「ならし（amortized）O(1)」なのは、満杯になったときだけ、より大きい配列を確保して丸ごとコピーし直すためです。コピーそのものは高くつきますが、起きる頻度がどんどん下がるので、平均すると 1 回あたり一定時間になります。
どう使い分けるか：読み取りが多いか、書き換えが多いか
判断の軸は「そのデータをどう使うか」です。読み取り（添字アクセスなどの参照）が中心なら配列系、先頭や途中への挿入・削除（書き換え）が中心なら連結リスト — これが理論上の答えです。
配列の先頭に 5 を挿入: 後ろの全員が 1 つずつずれる O(n) before: | 10 | 20 | 30 | 40 | after : | 5 | 10 | 20 | 30 | 40 | -> -> -> -> 連結リストの先頭に 5 を挿入: 矢印を 1 本つなぎ替えるだけ O(1) before: head -> [10] -> [20] -> [30] after : head -> [5] -> [10] -> [20] -> [30]
| こういう使い方なら | これを選ぶ |
|---|---|
| 添字でよく読む（読み取りが多い） | 配列・ArrayList |
| 末尾に追加していくのが中心 | ArrayList（ならし O(1)） |
| 先頭・途中への挿入・削除が中心（書き換えが多い） | LinkedList（位置まで辿るコストに注意） |
| 両端から出し入れする（キュー・両端キュー） | ArrayDeque（Java の定石） |
| 迷ったら | ArrayList |
現代の CPU では「配列が既定」
計算量の表にはもう 1 つ、実務で大事な事情が隠れています。CPU はメモリをキャッシュにまとめて読み込むため、連続した領域に並ぶ配列は「先読み」が効いて非常に速く、バラバラに散らばる連結リストはキャッシュに乗りにくいのです。計算量が同じでも実測では配列系が勝つことが多く、「迷ったら動的配列」が実務の既定になっています。
補足：Java の ArrayList と LinkedList の中身
Java では、ここまでの話が型の名前にそのまま現れています。List はインターフェース — 「追加できる・取り出せる・数えられる」といった、できることの契約 — で、実際にどんな構造で持つかは実装クラスが決めます。
// 「List」はインターフェース（できることの契約） // ArrayList / LinkedList はその実装（実際のデータ構造） List<String> a = new ArrayList<>(); // 中身は配列 List<String> b = new LinkedList<>(); // 中身は双方向連結リスト
ArrayList の中身は、名前のとおり配列です。要素は Object 型の配列 elementData に入っていて、満杯になると約 1.5 倍の長さの新しい配列を確保し、丸ごとコピーします（初期容量は 10 で、最初の追加時に確保されます）。
// ArrayList の内部構造（OpenJDK を簡略化） public class ArrayList<E> { Object[] elementData; // 実データはただの配列 int size; // 実際に入っている個数 public boolean add(E e) { if (size == elementData.length) { // 満杯なら約 1.5 倍の配列を確保して丸ごとコピー int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); elementData = Arrays.copyOf(elementData, newCapacity); } elementData[size++] = e; return true; } }
だから ArrayList の get(i) は O(1)、末尾への add はならし O(1)、途中への挿入・削除は後ろの要素をずらすコピーを伴う O(n) — さきほどの表の「動的配列」そのものの性質です。
一方 LinkedList の中身は双方向連結リストです。各ノードが前と次への参照を持ち、本体は先頭 first と末尾 last の 2 つだけを覚えています。
// LinkedList の内部構造（OpenJDK を簡略化） public class LinkedList<E> { Node<E> first; // 先頭ノード Node<E> last; // 末尾ノード int size; private static class Node<E> { E item; // 値 Node<E> next; // 次のノードへの参照 Node<E> prev; // 前のノードへの参照（双方向） } // get(i) は近い方の端から辿る（それでも O(n)） Node<E> node(int index) { if (index < (size >> 1)) { // 前半なら first から Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 後半なら last から Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } }
双方向なので、get(i) は前半なら先頭から、後半なら末尾から、近い方の端を選んで辿ります。賢い工夫ですが、それでも O(n) です。先頭・末尾への追加・削除は O(1) で、キューや両端キューとしても使えます。
実務メモ
Java でも、迷ったときの既定は ArrayList です。LinkedList が勝てるのは「要素を先頭から順にたどりながら（イテレータで走査しながら）、その場で頻繁に挿入・削除する」ような限られた場面で、両端キューが欲しいだけなら ArrayDeque の方が速いのが定石です。
まとめ
配列は「場所」で覚える構造。連続領域と添字計算のおかげで読み取りは O(1)、その代わり挿入・削除（書き換え）は苦手。
連結リストは「つながり」で覚える構造。つなぎ替えだけで書き換えできる、その代わり読み取りは O(n)。
読み取りが多いなら配列系、書き換えが多いなら連結リストを検討 — ただしキャッシュの事情で、実務の既定は動的配列（ArrayList）。
Java の「List」はインターフェース（できることの契約）、ArrayList / LinkedList は実装（実際の構造）。名前が中身の構造を教えてくれる。