導入
Java開発において、リストを扱う際に真っ先に思い浮かぶのはArrayListかもしれません。しかし、データの挿入や削除が頻繁に発生する場面では、連結リスト構造を持つjava.util.LinkedListが強力な武器となります。本記事では、LinkedListの仕組みを理解し、適切に使い分けるための技術的知見を解説します。
基礎知識
LinkedListは、各要素が「前後の要素への参照（ポインタ）」を持つノードで構成されています。ArrayListが内部的に配列を使用しており、要素の追加時に配列のコピーが発生する可能性があるのに対し、LinkedListはノードをメモリ上に配置し、参照を書き換えるだけで済みます。また、Listインターフェースだけでなく、Deque（両端キュー）インターフェースも実装しているため、スタックやキューとしての活用も可能です。
実装/解決策
LinkedListの最大の特徴は、リストの先頭や末尾への追加・削除コストがO(1)である点です。一方で、インデックスによるランダムアクセスはO(n)となり、ArrayListに劣ります。したがって、「データの末尾追加」や「先頭への割り込み処理」が頻発するアルゴリズムで採用するのが最適解です。また、Java 21以降のSequenced Collections導入により、先頭や末尾へのアクセスがより直感的に行えるようになりました。
サンプルプログラム
以下のコードは、LinkedListを使用してキュー処理を実装し、先頭と末尾を操作する例です。
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// LinkedListの生成
LinkedList<String> queue = new LinkedList<>();
// 末尾に追加 (エンキュー)
queue.addLast("タスク1");
queue.addLast("タスク2");
// 先頭に追加
queue.addFirst("優先タスク");
// 先頭から取り出し (デキュー)
String first = queue.removeFirst();
System.out.println("処理中: " + first);
// 現在のリスト状態を表示
System.out.println("残りのタスク: " + queue);
// 拡張for文での走査も可能
for (String task : queue) {
System.out.println("待機中: " + task);
}
}
}
応用・注意点
現場でLinkedListを使用する際に最も注意すべきは、「不用意なインデックス指定によるアクセス」です。例えば、forループでget(i)を使って全要素を走査すると、毎回先頭から辿るため計算量がO(n^2)となり、巨大なデータセットでは致命的なパフォーマンス低下を招きます。走査が必要な場合は、必ずIteratorを使用するか、拡張for文を利用してください。また、単なるリストとして使うだけであれば、現代のCPUキャッシュ効率を考えるとArrayListの方が高速であるケースが多いです。LinkedListは「Dequeとしての機能が必要か」「頻繁な挿入・削除が発生するか」という要件を明確にした上で選択しましょう。
コメント