きっかけ
「ランダムアクセスが遅い」というのは知識として持っていた。でも、なぜ遅いのかを自分の言葉で説明できるかというと、あやしかった。
ArrayList か LinkedList かを選ぶときに「まあ普通はArrayListでいいか」という判断をずっとしてきたが、その根拠が薄い気がして、改めて構造から確認することにした。
LinkedListはノードの連鎖でできている
ArrayList が内部的に配列を使っているのに対して、LinkedList は「ノード」と呼ばれるオブジェクトがつながった構造を持っている。
JavaのLinkedListクラスが内部で使っているNodeクラスは、こういう形になっている。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
各ノードは「値」と「前のノードへの参照」と「次のノードへの参照」の3つを持っている。これが双方向リストと呼ばれる理由で、前後どちらの方向にもたどることができる。
この構造がわかると、速い・遅いの理由がすっきりする。
挿入・削除が速い理由
リストの途中に要素を挿入するとき、ArrayList は後続のすべての要素を1つずつずらす処理が発生する。要素数が多いほどこのコストが大きくなる。
LinkedList の場合、挿入したい位置の前後のノードの参照を付け替えるだけでよい。
挿入前：A ⇄ B ⇄ C
挿入後：A ⇄ X ⇄ B ⇄ C
AのnextをXに、XのprevをAに、XのnextをBに、BのprevをXに。参照の更新だけで済む。削除も同様に、前後のノードを直接つなぎ直すだけなので一定時間で完了する。
ランダムアクセスが遅い理由
一方、特定インデックスの要素を取得したい場合は話が変わる。
配列であれば array[3] のように、インデックスから直接メモリアドレスを計算してアクセスできる。LinkedList にはそういった仕組みがない。インデックスを持たず、先頭（または末尾）のノードから順にたどっていくしかない。
import java.util.LinkedList;
class Main {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Hello");
linkedList.add("World");
// get(i) はノードを先頭から順番にたどって取得する
String element = linkedList.get(1); // "World"
System.out.println(element);
}
}
get(index) はインターフェースとして使えるが、内部でノードをたどる処理が走っている。要素数が増えるほど時間がかかる。インデックスを使って頻繁にアクセスするような使い方は LinkedList に向いていない。
余談だが、forループで linkedList.get(i) を毎回呼ぶコードを書くと、ループのたびにノードをたどる処理が走るため、要素数が多いと顕著に遅くなる。素朴に書いたコードが意図せずパフォーマンスのボトルネックになることがあるので、走査するだけなら後述の拡張for文かIteratorを使うほうが安全だ。
基本的な操作
初期化と要素の追加・削除はこのように使う。
import java.util.LinkedList;
import java.util.Arrays;
class Main {
public static void main(String[] args) {
// コレクションを渡して初期化
LinkedList<String> list = new LinkedList<>(Arrays.asList("Hello", "World"));
// 末尾に追加
list.add("d");
list.addAll(Arrays.asList("e", "f"));
System.out.println(list); // [Hello, World, d, e, f]
// インデックス指定で挿入（ノードをたどるので効率は下がる）
list.add(1, "x");
System.out.println(list); // [Hello, x, World, d, e, f]
// 削除
list.remove(); // 先頭を削除
list.remove(2); // インデックス指定
list.remove("x"); // オブジェクト指定
System.out.println(list); // [World, e, f]
}
}
remove() を引数なしで呼ぶと先頭の要素が削除される。Queue インタフェースの poll() に近い挙動で、最初はやや意外に感じた。
走査の方法
LinkedList を反復処理する方法はいくつかあるが、インデックスを使ったforループは先述の通り効率が下がるので避けたほうがよい。
拡張for文は LinkedList のルートインタフェースに Iterable があるため使える。内部でIteratorを使った順次アクセスになるのでノードを無駄にたどらない。
import java.util.LinkedList;
class Main {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("Hello");
list.add("World");
for (String element : list) {
System.out.println(element);
}
}
}
ListIterator を使えば前後どちらの方向にも進めるので、双方向にたどりたい場面では有効だ。
import java.util.LinkedList;
import java.util.ListIterator;
class Main {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("Hello");
list.add("World");
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
LinkedListがListとDequeを両方実装している点
LinkedList は List インタフェースだけでなく、Deque も実装している。そのため addFirst、addLast、removeFirst、removeLast といったメソッドが使えて、スタックやキューとして動かすこともできる。
ただ、前回の記事でも書いたが、スタック・キューの用途であれば ArrayDeque のほうがパフォーマンス面で優れているとされている。LinkedList はノードごとにオブジェクトを生成するためメモリのオーバーヘッドがあり、参照のたどりが伴う操作では ArrayDeque に劣ることが多い。
LinkedList が輝くのは「先頭・末尾への挿入削除が頻繁で、かつランダムアクセスをほとんどしない」という限定的な場面だと整理できた。
振り返って
今回ようやく腹落ちしたのは、「なぜ遅いのか」を内部のノード構造から説明できるようになった点だった。
「ランダムアクセスが遅い」という事実は知っていても、なぜかを説明できない状態は、選択の根拠があいまいなまま使い続けることにつながる。構造を追ってみたことで、使い分けの判断に少し自信が持てた気がしている。
ArrayList との具体的なパフォーマンス比較については要素数や操作の種類によって結果が変わるため、実際に計測したことがない。機会があれば数字で確認しておきたい。
この記事を書いた人について
株式会社Flexibilityでエンジニアをしています。
DX推進・システム開発を軸に、エンジニアが自律的に動ける環境を大事にしている会社です。
技術的に面白いことをやっていきたい方や、働き方に柔軟さを求めている方は、
よかったら一度のぞいてみてください。
- 会社サイト: https://www.flexi-inc.com/
- Qiita Organization: https://qiita.com/organizations/flexi-inc