LinkedListの詳細解析

LinkedList も Java コレクションフレームワークでよく使われる List 実装ですが、ArrayList とは発想がまったく異なります。ArrayList の中核は「動的配列」、LinkedList の中核は「連結リスト」です。ArrayList を連番付きの箱が並んだ構造だと考えるなら、LinkedList はノードの連なりで、各ノードが自分の値と前後のノードを覚えているイメージです。

クラス全体の構造

ソースコード設計の観点では、LinkedList はだいたい次のようになっています。

Java

        public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable

ここで重要なのは次の 2 点です。

List だけではない
Deque も実装しているため、両端キュー操作を自然にサポートします。
AbstractSequentialList を継承している
名前の通り、ランダムアクセスより順次アクセス向けの設計です。

この点は ArrayList と大きく違います。ArrayList はランダムアクセス寄り、LinkedList は順次構造操作寄りです。

内部の中核フィールド

LinkedList で特に重要なのは通常この 3 つです。

Java

        transient int size = 0;
transient Node<E> first;
transient Node<E> last;

意味は次の通りです。

size
現在リストにある要素数
first
先頭ノードへの参照
last
末尾ノードへの参照

連結リストを null <- A <-> B <-> C -> null とすると、

first は A を指す
last は C を指す
size は 3

この 3 つが LinkedList の挙動をほぼ決めます。

Node とは何か

LinkedList の実際の格納単位は要素そのものではなく Node です。

ソースの考え方は次のような形です。

Java

        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 つを持ちます。

item
ノード自身の値
next
次ノードへの参照
prev
前ノードへの参照

これが「双方向連結リスト」の本質です。例えば A <-> B <-> C なら、

B.prev = A
B.item は B の値
B.next = C

つまり LinkedList のデータは連続配置ではなく、参照でつながっています。

なぜ双方向連結リストなのか

各ノードが前後の両方を知っているからです。

直接的な利点は次の 2 つです。

先頭から後ろへたどれる
末尾から前へもたどれる

そのため、LinkedList のソースで index を探すときは常に先頭からではなく、位置に応じて first と last を使い分けます。

空リストの状態

空のときは次のようになります。

size = 0
first = null
last = null

これは重要です。多くの挿入・削除ロジックは以下 2 パターンに分岐するためです。

元が空
元が空でない

ソース中の多くの判定はこの状態を基準にしています。

先頭挿入 linkFirst

先頭挿入は LinkedList の典型的なロジックです。

Java

        private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
                last = newNode;
        else
                f.prev = newNode;
        size++;
        modCount++;
}

分解すると次の通りです。

旧先頭 f を退避
新ノード newNode を作成
新ノードの prev は先頭になるので null
新ノードの next は旧先頭 f
first を新ノードに更新
元が空なら
旧先頭 f は null なので last も新ノードにする
元が空でなければ
旧先頭の prev を新ノードに向ける
size を増やす
modCount を増やす

ポイントは、先頭挿入では要素の移動は不要で、参照更新だけで済むことです。

末尾挿入 linkLast

末尾挿入も対称的です。

Java

        void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
                first = newNode;
        else
                l.next = newNode;
        size++;
        modCount++;
}

流れは次の通りです。

旧末尾 l を退避
新ノードの prev は旧末尾
新ノードの next は末尾なので null
last を更新
元が空なら first も新ノード
そうでなければ旧末尾の next を新ノードへ
size と modCount を更新

そのため LinkedList は末尾追加にも自然に向いています。

中間挿入 linkBefore

先頭でも末尾でもなく、あるノードの前へ挿入する場合は次のようなイメージです。

Java

        void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
                first = newNode;
        else
                pred.next = newNode;
        size++;
        modCount++;
}

鍵は succ で、「誰の前に入れるか」を表す後続ノードです。

元が A <-> B <-> C で、B の前に X を入れるなら：

succ は B
pred は A
X の prev = A
X の next = B
A.next を X に変更
B.prev を X に変更

結果は A <-> X <-> B <-> C です。

変わるのは参照数本だけです。

ノード削除 unlink

削除も連結リストの重要ポイントです。既知ノード x を削除する考え方は次の通りです。

Java

        E unlink(Node<E> x) {
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
                first = next;
        } else {
                prev.next = next;
                x.prev = null;
        }

        if (next == null) {
                last = prev;
        } else {
                next.prev = prev;
                x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
}

このメソッドは非常に重要です。

A <-> B <-> C の中間 B を削除すると、A <-> C にする必要があります。

ソース上で行うのは：

B の prev（A）を取得
B の next（C）を取得
A.next = C
C.prev = A

これで B は連鎖から外れます。

さらに次の処理も重要です。

x.prev = null
x.next = null
x.item = null

主目的は GC 回収を助け、不要参照を残さないことです。

既知ノード削除が速い理由

ArrayList のように要素シフトが不要だからです。

配列削除では後続要素を前詰めします。連結リスト削除は前後ノードをつなぎ直すだけです。

そのため、削除対象ノードが既に分かっていれば、削除処理自体は O(1) です。

ただし非常に重要な前提があります。まずそのノードを見つける必要があります。

remove(index) の場合、削除前に index ノードの探索が必要で、これは通常 O(n) です。

よってソース観点で正確に言うと：

ノード切り離しは O(1)
ノード探索は通常 O(n)
インデックス削除全体は O(n)

なぜ index アクセスが遅いのか

LinkedList の要となる node(index) を見ると分かります。

Java

        Node<E> node(int index) {
        if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                        x = x.next;
                return x;
        } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                        x = x.prev;
                return x;
        }
}

意味は次の通りです。

index が前半なら
先頭から後ろへ探索
index が後半なら
末尾から前へ探索

例：size = 100 で index = 80 のとき、first から 80 歩ではなく、last から逆向きに約 19 歩です。

これは最適化ですが本質は変わりません。依然として線形探索であり、配列の O(1) 直接参照ではありません。

したがって get(index)、set(index)、add(index, e)、remove(index) はすべて node(index) の影響を受けます。

get / set / add / remove の本質

これらは次のように整理できます。

get(index)

Java

        public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

インデックス検証後、node(index) でノード取得し item を返します。ボトルネックは node(index) です。

set(index, element)

Java

        public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
}

代入自体は速いですが、ノード探索が遅いため全体は O(n) です。

add(index, element)

Java

        public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
        linkLast(element);
        else
        linkBefore(element, node(index));
}

末尾追加なら linkLast、それ以外は node(index) で位置を取り linkBefore します。

remove(index)

Java

        public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

先にノードを見つけ、次に切り離します。

つまり index ベース操作のボトルネックは「変更そのもの」ではなく「ノード探索」です。

なぜ LinkedList はランダムアクセスに向かないか

ソース上の理由はシンプルです。

配列のようなインデックス直接参照能力がない next / prev を辿るしかない get(index) ごとに先頭か末尾から再探索が起きうる

そのため次のようなコード：

Java

        for (int i = 0; i < list.size(); i++) {
        list.get(i);
}

ArrayList では問題になりにくいですが、LinkedList では各 get(i) が探索を行うため、全体が O(n^2) 近くになることがあります。

LinkedList の走査では次を推奨します。

for-each
Iterator
先頭から末尾へ順次走査

インデックスの反復参照は避けるのが無難です。

Deque が自然に合う理由

LinkedList は Deque を実装しており、構造特性と一致しています。

例えば：

addFirst
実質 linkFirst
addLast
実質 linkLast
removeFirst
実質 first の削除
removeLast
実質 last の削除
peekFirst
first.item を返す
peekLast
last.item を返す

常に先頭・末尾を保持しているため、両端キューとして非常に扱いやすいです。

これは LinkedList の代表的な設計価値の 1 つで、List であるだけでなく Deque としても適しています。

なぜ Iterator で順次走査できるか

LinkedList 内部には ListItr のような反復子実装があります。通常は次を保持します。

next
次に返すノード
lastReturned
直前に返したノード
nextIndex
現在の反復位置
expectedModCount
反復子生成時点の変更バージョン

next() の本質は次です。

同時変更チェック現在ノード値を返すポインタを次へ進める

連結リスト自体が順序接続されているため、next を辿るだけで順次走査できます。

modCount と fail-fast

これもソースで頻出するポイントです。

LinkedList の継承系には modCount があり、構造変更回数を表します。通常は次のような操作で増えます。

add
remove
clear
そのほかの構造変更

反復子作成時には expectedModCount を記録します。

以降の各反復で、

現在の modCountexpectedModCount と一致するか

を確認します。

一致しなければ、反復中に外部変更されたと判断し ConcurrentModificationException を投げます。

これが fail-fast 機構です。

目的はスレッド安全性の提供ではなく、誤った使い方を早期に顕在化することです。

例えば反復中に list.remove() を直接呼ぶと、この例外が起きる可能性があります。

最小構成の思考モデル

Java

        class MyLinkedList<E> {
        Node<E> first;
        Node<E> last;
        int size;

        static class Node<E> {
                E item;
                Node<E> prev;
                Node<E> next;
        }
}

用途

通常の List として：

add
get
set
remove
size

キューとして：

offer
poll
peek

両端キューとして：

offerFirst
offerLast
pollFirst
pollLast
peekFirst
peekLast

スタックとして：

push
pop
peek

結局のところ、LinkedList がやっていることは次に集約できます。

先頭挿入：first と旧先頭の prev を更新
末尾挿入：last と旧末尾の next を更新
中間挿入：前ノード・新ノード・後ノードをつなぎ直す
削除：対象ノードの前後を再接続する
index アクセス：先頭または末尾から辿って目的ノードを見つける
反復子：next に沿って順番に読む

Fonnpo

Spring フレームワーク完全ガイド

HashMapの詳細解析

ArrayListの詳細解析