Java Academy · レッスン

LinkedList と ArrayList のトレードオフ

Q: 「LinkedList と ArrayList のトレードオフ」で何を学びますか？

適切なリスト型を選べるように、挿入、削除、ランダムアクセスの性能を比較します。 ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

適切なリスト型を選べるように、挿入、削除、ランダムアクセスの性能を比較します。

「LinkedList と ArrayList のトレードオフ」はCoddyKit上の無料Java Academyレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。

核心となる問い

ArrayList と LinkedList はどちらも List を実装しているため、同じ API を共有します。違いは、それぞれの内部データ構造と、効率的に実行できる操作にあります。

ArrayList の内部構造

ArrayList は要素を連続した配列に格納します。配列が満杯になると、1.5 倍の大きさを持つ新しい配列に置き換えられ、すべての要素がコピーされます。

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

LinkedList の内部構造を再確認

各要素は、prev/next ポインターを持つ独自の Node オブジェクトに格納されます。メモリは連続しておらず、ノードはヒープ上のどこにでも配置されます。

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

ランダムアクセス：ArrayList の勝利

ArrayList.get(i) は配列のインデックスを直接参照するため O(1) です。LinkedList.get(i) は最大 n/2 個のノードを走査するため O(n) です。

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

先頭への挿入：LinkedList の勝利

ArrayList のインデックス 0 への追加では、すべての要素を移動する必要があり O(n) です。LinkedList では 2 つのポインターを更新するだけなので O(1) です。

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

末尾への追加：ほぼ同等

ArrayList と LinkedList は、どちらも末尾への追加を償却 O(1) で行えます。ArrayList ではときどきサイズ変更とコピーが発生しますが、償却計算量は O(1) です。LinkedList では新しいノードを割り当てるため、サイズ変更は必要ありません。

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

メモリ使用量

ArrayList：要素あたり約 8 バイト（配列内の参照 1 つ）。LinkedList：要素あたり約 48 バイト（データ、prev、next、およびオブジェクトヘッダーを持つ Node オブジェクト）。大規模なデータセットでは、ArrayList のほうが使用メモリを大幅に抑えられます。

反復処理のパフォーマンス

順番に走査する反復処理（for-each または iterator）は、どちらも O(n) です。ただし ArrayList は要素がメモリ上で連続しているため、CPU キャッシュのプリフェッチの恩恵を受けます。LinkedList のノードはヒープ上に分散するため、キャッシュミスが発生します。

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

中央への挿入・削除

どちらも位置を見つけるために O(n) が必要です。位置が見つかった後、ArrayList は要素を移動するため O(n) ですが、LinkedList は連結を解除するだけなので O(1) です。そのため、すでにイテレーターを保持している場合に中央部の変更を頻繁に行うなら LinkedList が有利です。それ以外では両者に大きな違いはありません。

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

選択ガイド

主な操作に基づいて選択します：

ArrayList：ランダムアクセス、反復処理、末尾への追加 — 90% の用途をカバーします
LinkedList：先頭・末尾への挿入や削除を頻繁に行う場合、キュー・deque・スタックの実装
ArrayDeque：純粋なキューまたはスタックが必要な場合（LinkedList より適しています）

ベンチマークのまとめ

パフォーマンスを理解するためのモデル：

get(i)：ArrayList は O(1)、LinkedList は O(n)
add(0,x)：ArrayList は O(n)、LinkedList は O(1)
add(x)：どちらも償却 O(1)
iterator remove：位置が決まっていればどちらも O(1)
要素あたりのメモリ：ArrayList は約 8B、LinkedList は約 48B

クイックチェック

タスクが末尾に追加され、先頭から毎秒数百万回削除されるタスクキューを構築しています。最も適切なデータ構造はどれですか？

まとめ: LinkedList と ArrayList

要点:

ArrayList はランダムアクセス（O(1)）とキャッシュ効率のよい反復処理に優れています
LinkedList は先頭および末尾での O(1) の操作に優れています
メモリ使用量: ArrayList は要素あたり約 8B、LinkedList は要素あたり約 48B です
キューやスタックには、LinkedList よりも ArrayDeque を優先してください
ほとんどの場面では、ArrayList が適切なデフォルトの選択肢です

よくある質問

「LinkedList と ArrayList のトレードオフ」レッスンは無料ですか？

はい。「LinkedList と ArrayList のトレードオフ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。

「LinkedList と ArrayList のトレードオフ」で何を学びますか？

適切なリスト型を選べるように、挿入、削除、ランダムアクセスの性能を比較します。ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Java Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン3/4です。

「LinkedList と ArrayList のトレードオフ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このJava Academyレッスンでコードを書いて実行できますか？

はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Java Academyに戻る