Java | Java 標準ライブラリ：LinkedList

Java Java
スポンサーリンク

LinkedList をざっくりイメージする

まず感覚からいきます。

ArrayList は「配列ベースで、連番の棚がズラッと並んでいるストレージ」です。
それに対して LinkedList は、「前後の箱が“鎖”のようにつながったストレージ」です。

1つ1つの要素が、「自分のデータ」＋「前の要素への参照」＋「次の要素への参照」を持っていて、
それらが順番につながっているイメージです（Java の LinkedList は「両方向」のリンクリスト）。

コード上では、基本的にこう書きます。

List<String> list = new LinkedList<>();
Java

ArrayList と同じ List インターフェースを実装しているので、
add, get, remove などの使い方はほぼ同じです。
違いは「内部構造」と、それに伴う「得意・不得意な操作」です。

ArrayList と LinkedList の違いを直感で押さえる

ArrayList は「インデックスアクセスが速い」が「途中の追加・削除に弱い」

ArrayList は内部的には配列です。
get(i) は配列アクセスなのでとても速いですが、
途中で add(index, value)、remove(index) をすると、その後ろの要素を全部ずらす必要があります。

例として、要素数が 10000 のリストの先頭に 1 個挿入したい場合、
ArrayList だと 10000 個をまるっと後ろにずらすことになります。

LinkedList は「前後のつながりだけ付け替えればよい」

LinkedList は「要素がチェーンのようにつながっている」構造です。

途中に 1 つ要素を挿入するときは、基本的に

「前の要素 → 新しい要素 → 次の要素」

というリンクをつなぎ直せばよく、
配列のように大量の要素をコピーしたりはしません。

このため、概念的には

先頭・末尾・途中への追加・削除 → LinkedList が得意
インデックスを指定したランダムアクセス（get(9999) など） → ArrayList が得意

という住み分けになります。

ただし、Java の LinkedList はかなり多機能でオーバーヘッドもあるので、
「なんとなく LinkedList にしたほうが速そう」と思って気軽に置き換えるのはあまりおすすめしません。
初心者のうちは、「通常は ArrayList。特別な理由があるときに LinkedList を検討」が基本で大丈夫です。

LinkedList の基本操作（ArrayList と「何が」同じで「何が」違うか）

基本的な add / get / remove は同じ

使い方そのものは ArrayList とほとんど変わりません。

import java.util.LinkedList;
import java.util.List;

public class LinkedListBasic {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();

        list.add("Alice");
        list.add("Bob");
        list.add("Carol");

        System.out.println(list);          // [Alice, Bob, Carol]

        String first = list.get(0);        // "Alice"
        list.remove(1);                    // index 1 の "Bob" を削除

        System.out.println(list);          // [Alice, Carol]
    }
}
Java

List<String> list = new LinkedList<>(); にしておけば、
ArrayList に差し替えることも簡単です。

List<String> list = new ArrayList<>();   // 後からこう変えても、他のコードはほぼそのまま
Java

API（メソッドの名前や意味）はほぼ共通なので、
「違うのは内部の構造と性能特性」と考えてください。

LinkedList 独自の「両端操作」メソッド（ここは少し深掘り）

LinkedList は、List であると同時に Deque（両端キュー）インターフェースも実装しています。
つまり、「先頭」と「末尾」を意識した操作が得意です。

代表的なメソッドは次のあたりです（名前のイメージをつかんでほしいのでまとめて例を出します）。

LinkedList<String> list = new LinkedList<>();

list.addFirst("A");  // 先頭に追加
list.addLast("B");   // 末尾に追加（add とほぼ同じ）

String first = list.getFirst();  // 先頭要素を見る
String last  = list.getLast();   // 末尾要素を見る

String removedFirst = list.removeFirst(); // 先頭を取り出して削除
String removedLast  = list.removeLast();  // 末尾を取り出して削除
Java

スタックやキューの実装にも、そのまま使えます。

スタックっぽく（後入れ先出し）使うなら addFirst ＋ removeFirst など。
キューっぽく（先入れ先出し）使うなら addLast ＋ removeFirst など。

ArrayList にはこういう「先頭・末尾に特化した名前のメソッド」はありません。
LinkedList を使うなら、ここを活かせる設計になっているか？が一つの判断基準になります。

LinkedList を使うときの「向き・不向き」をもう少しちゃんと理解する

「先頭にしょっちゅう追加・削除する」なら LinkedList が候補

例えば、常にデータの先頭に新しい要素を突っ込むようなケース。

LinkedList<Integer> list = new LinkedList<>();

list.addFirst(10);
list.addFirst(20);
list.addFirst(30);
System.out.println(list);  // [30, 20, 10]
Java

ArrayList でこれをやると、毎回全要素を後ろにずらすコストがかかります。
LinkedList なら、「リンク付け替え＋内部での参照更新」で済みます。

ただし、実際には Java の ArrayList もかなり最適化されていて、
要素数が少なかったり、処理回数が少ない場合は、体感的に差が出ないことも多いです。

だからこそ、初心者向けの指針としては、

特別な理由がなければ ArrayList
「先頭・末尾の追加・削除を大量にやる」「キュー・スタックっぽい用途がメイン」なら LinkedList も検討

くらいのバランス感で考えておくのが現実的です。

ランダムアクセス（インデックスアクセス）は苦手

list.get(100_000) のような「大きいインデックスへのアクセス」は、
ArrayList なら配列アクセス一発ですが、LinkedList は「先頭から 100000 回分リンクをたどる」イメージです。

要素数が大きくなるほど、get(index) のコスト差は広がっていきます。

なので、「大量の要素がいて、インデックスで頻繁にアクセスする」ような用途で
LinkedList を選ぶのはほぼおすすめできません。

LinkedList をキュー／スタックとして扱う小さな例

キュー（Queue）として使う例（先入れ先出し）

import java.util.LinkedList;
import java.util.Queue;

public class LinkedListAsQueue {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("task1");
        queue.offer("task2");
        queue.offer("task3");

        System.out.println(queue.poll()); // task1
        System.out.println(queue.poll()); // task2
        System.out.println(queue.poll()); // task3
    }
}
Java

ここでは、Queue インターフェース型で受けて、LinkedList を中身に使っています。
offer で末尾に追加し、poll で先頭から取り出します。

裏で何が行われているかというと、
offer → addLast、poll → removeFirst のような動きです。

スタック（Stack）として使う例（後入れ先出し）

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListAsStack {
    public static void main(String[] args) {
        Deque<String> stack = new LinkedList<>();

        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println(stack.pop()); // C
        System.out.println(stack.pop()); // B
        System.out.println(stack.pop()); // A
    }
}
Java

Deque インターフェース型で受けて、push（先頭に追加）と pop（先頭から取り出し）で
スタックとして扱っています。

Java には古い Stack クラスもありますが、
現代的な書き方では Deque + LinkedList を使うのが一般的です。

まとめ：LinkedList をどう頭の中に置いておくか

初心者向けに、LinkedList の位置づけを整理するとこうなります。

内部構造が「前後へのリンクでつながった鎖のようなリスト」。
List としての API は ArrayList とほぼ同じだが、前後に特化したメソッド（addFirst, addLast, removeFirst, removeLast など）も持つ。
先頭・末尾への追加／削除がしょっちゅう発生する、キューやスタックのような用途に向いている。
インデックス指定のランダムアクセスは ArrayList のほうが圧倒的に得意なので、そこを勘違いして選ばない。
通常は ArrayList をデフォルトにし、「これは LinkedList 向きだな」という明確な理由があるときだけ切り替える。

スポンサーリンク
タイトルとURLをコピーしました