導入：なぜリストの選択が重要なのか
Java開発において、Listインターフェースの実装であるArrayListとLinkedListは最も頻繁に利用されます。しかし、単に「どちらもリストだから」という理由で選んでいませんか？不適切なコレクション選択は、要素数が増大した際にアプリケーションのパフォーマンスを著しく低下させます。本稿では、計算量（Big O記法）の観点から、現場でどちらを選ぶべきかの判断基準を解説します。
基礎知識：ArrayListとLinkedListの仕組み
ArrayListは、内部で「配列（Array）」を使用しています。メモリ上に連続した領域を確保するため、インデックスによるアクセスが非常に高速です。
LinkedListは、内部で「二重連結リスト（Doubly Linked List）」を使用しています。各要素が「前の要素」と「次の要素」への参照を持っているため、メモリ上の連続性は不要ですが、アクセスには先頭または末尾から順に辿る必要があります。
実装・計算量比較
以下の表は、主要な操作における計算量（O記法）をまとめたものです。
操作 | ArrayList | LinkedList
— | — | —
末尾への追加 (add) | O(1) ※償却計算量 | O(1)
先頭への追加/削除 | O(n) | O(1)
中間の挿入/削除 | O(n) | O(n) ※検索コスト含む
ランダムアクセス (get) | O(1) | O(n)
サンプルプログラム：パフォーマンスの差を実感する
以下のコードは、リストの先頭に要素を追加する際の速度差を検証するサンプルです。
import java.util.;
public class ListPerformance {
public static void main(String[] args) {
int count = 100000;
// ArrayListの検証
List<Integer> arrayList = new ArrayList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
// ArrayListは先頭挿入時に全要素をずらすため時間がかかる
arrayList.add(0, i);
}
System.out.println("ArrayListの処理時間: " + (System.currentTimeMillis() - start) + "ms");
// LinkedListの検証
List<Integer> linkedList = new LinkedList<>();
start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
// LinkedListは参照を繋ぎ変えるだけなので高速
linkedList.add(0, i);
}
System.out.println("LinkedListの処理時間: " + (System.currentTimeMillis() - start) + "ms");
}
}
応用・現場での注意点
1. デフォルトはArrayListを選択せよ：現代のCPUキャッシュ効率を考慮すると、メモリの局所性が高いArrayListの方が、ほとんどのケースで高速に動作します。「LinkedListの方が速い」という古い定説は、現在のハードウェア環境では誤りである場合が多いです。
2. LinkedListの出番は限定的：LinkedListが真価を発揮するのは、リストの先頭や末尾に対して頻繁にadd/removeを行う場合（Queueとして利用する場合など）のみです。もしキュー操作が必要なら、LinkedListではなくArrayDequeの使用を強く推奨します。ArrayDequeの方がメモリ効率とキャッシュ効率に優れているためです。
3. Sequenced Collectionsの活用：Java 21から導入されたSequencedCollectionインターフェースにより、ArrayListやLinkedListの先頭・末尾へのアクセスがより直感的になりました。現場での実装時は、これらのモダンなAPIを活用しましょう。
結論として、特別な理由がない限りArrayListを選択し、特定の要素操作でパフォーマンス上のボトルネックが特定された場合にのみ、データ構造を見直すというのがシニアエンジニアとしての賢明なアプローチです。
コメント