LinkedList の使いどころ（頻繁な先頭/中間挿入） — キュー実装
Java で「リスト構造」を扱うとき、ArrayList と LinkedList が代表的です。
初心者が理解すべきポイントは「どんな場面で LinkedList が有利か」「性能の特徴」「キュー実装への応用」です。ここでは例題を交えて解説します。
LinkedList の特徴
- 内部構造: 双方向リンク（前後のノードをつなぐ）。
- 先頭・中間への挿入/削除が速い: O(1)（位置が分かっている場合）。
- ランダムアクセスは遅い: get(index) は O(n)。
- 用途: 「頻繁に先頭や中間に挿入・削除する」「キューやスタックを実装する」場面に向いている。
👉 まとめ:
- ランダムアクセス重視 → ArrayList
- 挿入・削除重視 → LinkedList
基本コード例
1. 作成と追加
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
System.out.println(list); // [Apple, Banana, Cherry]
}
}
2. 先頭への追加
list.addFirst("Orange");
System.out.println(list); // [Orange, Apple, Banana, Cherry]
3. 末尾への追加
list.addLast("Grape");
System.out.println(list); // [Orange, Apple, Banana, Cherry, Grape]
4. 中間への挿入
list.add(2, "Mango"); // インデックス2に挿入
System.out.println(list); // [Orange, Apple, Mango, Banana, Cherry, Grape]
5. 削除
list.removeFirst(); // 先頭削除
list.removeLast(); // 末尾削除
System.out.println(list); // [Apple, Mango, Banana, Cherry]
性能の考え方
| 操作 | 計算量 | 特徴 |
|---|---|---|
| addFirst / addLast | O(1) | 先頭・末尾の追加が速い |
| removeFirst / removeLast | O(1) | 先頭・末尾の削除が速い |
| add(index, value) | O(n) | 中間挿入は位置探索が必要 |
| get(index) | O(n) | ランダムアクセスは遅い |
👉 キューやスタックの実装に最適。
例題で練習
例題1: キュー（FIFO: 先入れ先出し）
LinkedList<String> queue = new LinkedList<>();
// 入れる（enqueue）
queue.addLast("Task1");
queue.addLast("Task2");
queue.addLast("Task3");
// 取り出す（dequeue）
System.out.println(queue.removeFirst()); // Task1
System.out.println(queue.removeFirst()); // Task2
System.out.println(queue); // [Task3]
例題2: スタック（LIFO: 先入れ後出し）
LinkedList<String> stack = new LinkedList<>();
// 入れる（push）
stack.addFirst("Item1");
stack.addFirst("Item2");
stack.addFirst("Item3");
// 取り出す（pop）
System.out.println(stack.removeFirst()); // Item3
System.out.println(stack.removeFirst()); // Item2
System.out.println(stack); // [Item1]
テンプレート集
先頭・末尾操作
list.addFirst(value);
list.addLast(value);
list.removeFirst();
list.removeLast();
キューとして使う
queue.addLast(task); // enqueue
Task t = queue.removeFirst(); // dequeue
スタックとして使う
stack.addFirst(item); // push
Item i = stack.removeFirst(); // pop
実務でのコツ
- ランダムアクセスは苦手:
get(index)を多用するなら ArrayList を選ぶ。 - 大量の挿入・削除: 先頭や中間での操作が多いなら LinkedList が有利。
- キュー/スタック用途: LinkedList は
Dequeインターフェースを実装しているので、自然に使える。 - スレッド安全ではない: 複数スレッドで使う場合は
ConcurrentLinkedQueueなどを検討。
まとめ
- LinkedList は「挿入・削除が多い一覧管理」に強い。
- キューやスタックの実装に最適。
- ランダムアクセスは遅いので、用途に応じて ArrayList と使い分ける。
👉 練習課題として「LinkedList を使って待ち行列（キュー）を作り、順番に処理する」コードを書いてみると、LinkedList の強みが体感できます。