LinkedList の内部構造
LinkedList の双方向リンクノード構造と、その時間計算量の特徴を詳しく見ていきます。
「LinkedList の内部構造」はCoddyKit上の無料Java Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。
LinkedList の内部構造
Java の LinkedList は双方向連結リストです。各ノードは前後のノードへの参照と要素の値を保持します。ArrayList とは異なり、内部配列はなく、ノードごとにメモリが割り当てられます。
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}時間計算量の特徴
LinkedList のパフォーマンス特性は ArrayList と大きく異なります：
- addFirst / addLast：O(1)
- get(index)：O(n) — 先頭または末尾から走査する必要があります
- remove(index)：検索に O(n)、その後の連結解除に O(1)
- Iterator による走査：O(n)
先頭や末尾への挿入を頻繁に行う必要があり、ランダムアクセスが不要な場合に LinkedList を使用します。
LinkedList の作成と走査
LinkedList の作成と反復処理には、すでに学んだ List インターフェースをそのまま使用できます。違いは内部構造にあります。
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst、addLast、removeFirst、removeLast
LinkedList は、ArrayList では効率的に利用できない先頭・末尾の操作を提供します：
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]ノードの連結解除：検索後の削除は O(1)
ノードへの参照を（イテレーター経由で）取得した後は、next と prev のポインターを更新するだけなので、削除は O(1) です。ArrayList のように要素を移動する必要はありません。
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]ArrayList とのメモリオーバーヘッド比較
LinkedList の各ノードは、要素への参照に加えて、2 つの参照（prev、next）を持ちます。64 ビット JVM では、エントリごとに約 48 バイトです。ArrayList は連続した配列内に要素への参照だけを格納するため、8 バイトです。
大規模で読み取りの多いデータセットでは、通常 ArrayList のほうがキャッシュ効率に優れ、使用メモリも少なくなります。
Deque の操作：スタックとキュー
LinkedList は Deque インターフェースを実装しているため、スタックとしてもキューとしても使用できます。
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topPriorityQueue の概要
PriorityQueue はヒープベースのキューです。自然順序または comparator に基づいて最小の要素が常に先に取り出されます。連結リストを基盤としているわけではなく、二分ヒープ配列を使用します。
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40カスタム Comparator を使った PriorityQueue
順序を逆にしたり、カスタムフィールドでソートしたりするには、Comparator を渡します：
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowLinkedList と ArrayList の選択
基本的な指針：
- ランダムアクセス、反復処理、ほとんどの用途には ArrayList を使用します。
- 両端での O(1) の挿入・削除を頻繁に行い、インデックスアクセスが不要な場合は LinkedList を使用します。
- 順序に従った処理（タスクのスケジューリングやダイクストラ法）が必要な場合は PriorityQueue を使用します。
よくある落とし穴
LinkedList に対してループ内で get(i) を呼び出すのは避けてください。合計計算量が O(n²) になります：
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}クイックチェック
リストのサイズに関係なく O(1) となる LinkedList の操作はどれですか？
まとめ：LinkedList と Deque
重要なポイント：
- LinkedList は双方向連結リストで、先頭・末尾の操作が O(1) です
- ランダムアクセス（インデックスによる get/set）は O(n) です
- Deque を実装しており、スタックまたはキューとして使用できます
- PriorityQueue はヒープ順序に従った処理を提供します
- ほとんどの用途では ArrayList を優先し、先頭・末尾の変更を頻繁に行う場合に LinkedList を使用します
よくある質問
「LinkedList の内部構造」レッスンは無料ですか？
はい。「LinkedList の内部構造」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。
「LinkedList の内部構造」で何を学びますか？
LinkedList の双方向リンクノード構造と、その時間計算量の特徴を詳しく見ていきます。 ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Java Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「LinkedList の内部構造」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このJava Academyレッスンでコードを書いて実行できますか？
はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。