先生と生徒の会話形式で理解しよう

生徒

「JavaのListを使おうと思ったら、ArrayListとLinkedListの2種類が出てきました。これって何が違うんですか？」

先生

「どちらも要素を順番に管理するリスト構造ですが、内部の仕組みが全く異なります。特にデータの追加や削除のスピードに大きな差があるんですよ。」

生徒

「初心者はどっちを使えばいいんでしょうか？具体的な使い分けの基準が知りたいです！」

先生

「基本的にはArrayListがよく使われますが、LinkedListが圧倒的に有利な場面もあります。それぞれのメリットとデメリットを詳しく見ていきましょう！」

1. LinkedListとは？双方向連結リストの仕組みを学ぶ

JavaのLinkedListは、java.utilパッケージに含まれるコレクションクラスで、ListインターフェースとDequeインターフェースの両方を実装しています。最大の特徴は、データを配列のように一列に並べて管理するのではなく、「ノード」と呼ばれる小さな箱を鎖のようにつなげて管理している点です。

それぞれのノードは、「自分が持っているデータ」と「前のノードへの参照」「次のノードへの参照」を持っています。このように前後どちらにもたどれる構造を双方向連結リストと呼びます。ArrayListのようにメモリ上で連続して並んでいなくても、リンク情報をたどることで順番を維持できるため、途中への追加や削除が得意です。

イメージとしては、紙に書かれたメモ同士をホチキスでつなげているような状態です。間に新しいメモを差し込みたい場合でも、前後のホチキスを付け替えるだけで済むため、全体を動かす必要がありません。

プログラミング未経験者向けに、LinkedListの基本的な考え方がわかる簡単なサンプルを見てみましょう。


import java.util.LinkedList;

public class SimpleLinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> fruits = new LinkedList<>();

        // 要素を順番に追加
        fruits.add("りんご");
        fruits.add("みかん");
        fruits.add("バナナ");

        // 中身を表示
        System.out.println(fruits);
    }
}

このプログラムでは、「りんご」「みかん」「バナナ」というデータが、それぞれ別々のノードとして管理され、前後の関係を保ちながらLinkedListの中に保存されています。見た目は普通のリストですが、内部ではノード同士がリンクでつながっている点が、LinkedListならではの仕組みです。

2. LinkedListの基本的な使い方とソースコード解説

まずは、LinkedListをどのように記述するのか、基本的なコードを確認してみましょう。使い方はArrayListとほぼ同じですが、インスタンス化する際にLinkedListを指定します。初心者が最初につまずきやすいのはインポート宣言ですが、java.util.LinkedListを忘れずに記述しましょう。


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

public class BasicLinkedList {
    public static void main(String[] args) {
        // LinkedListの宣言と生成
        List<String> animals = new LinkedList<>();

        // 要素の追加
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Rabbit");

        // 要素の表示
        for (String animal : animals) {
            System.out.println(animal);
        }
    }
}


Dog
Cat
Rabbit

このように、通常のリスト操作であればArrayListと全く同じ感覚で利用できることがわかります。しかし、内部では要素が追加されるたびに新しいノードが作成され、参照が書き換えられています。

3. ArrayListとLinkedListの決定的な違い

Javaエンジニアとして最も理解しておくべきなのが、ArrayListとLinkedListの性能差です。これらは「データのアクセス速度」と「データの更新速度」において対照的な特性を持っています。

ArrayListは内部で「配列」を使用しているため、インデックス番号（添え字）を指定して特定の要素を取り出すのが非常に高速です。これを「ランダムアクセス」と呼びます。しかし、リストの途中にデータを挿入したり、削除したりする場合、それ以降のデータをすべて一つずつずらす必要があるため、データ量が多いと処理が重くなります。

対するLinkedListは、特定の要素にアクセスする場合、先頭（または末尾）から順番にリンクを辿っていく必要があるため、指定した番号のデータを取り出すのは遅いです。しかし、要素の挿入や削除は、隣り合うノードの参照を書き換えるだけで済むため、要素の移動が発生せず、非常に高速に処理を終えることができます。

4. リストの先頭や途中への挿入・削除を実践する

LinkedListが最も得意とする「データの挿入と削除」について、具体的なコードで見ていきましょう。特に、大量のデータを扱う際に、先頭にデータを追加する処理を繰り返すようなケースでは、LinkedListの独壇場となります。


import java.util.LinkedList;

public class ModifyListExample {
    public static void main(String[] args) {
        LinkedList<String> tasks = new LinkedList<>();
        
        tasks.add("掃除");
        tasks.add("洗濯");
        
        // 先頭に要素を追加
        tasks.addFirst("料理");
        
        // 1番目のインデックスに挿入（料理と掃除の間）
        tasks.add(1, "買い物");
        
        // 削除
        tasks.remove("洗濯");
        
        System.out.println("現在のタスクリスト: " + tasks);
    }
}


現在のタスクリスト: [料理, 買い物, 掃除]

このコードで注目すべきは、addFirstメソッドです。これはLinkedList特有（正確にはDequeインターフェース由来）のメソッドで、リストの先頭に一瞬でデータを追加できます。ArrayListで同じことを行うと、全ての要素を後ろにずらすコストが発生しますが、LinkedListなら参照を2、3箇所書き換えるだけで完了します。

5. キュー（Queue）やデック（Deque）としての活用法

LinkedListは、Listインターフェースだけでなく、QueueやDequeといったインターフェースも実装しています。これにより、「最初に入れたものを最初に取り出す（FIFO）」や「最後に入れたものを最初に取り出す（LIFO）」といった、特殊なデータ管理が容易に行えます。

例えば、コールセンターの着信待ち行列や、スタック構造でのデータ処理、ブラウザの「戻る」ボタンの履歴管理などがこれに当たります。単なるデータの羅列ではなく、特定のルールに基づいた出し入れが必要な場合に、LinkedListは非常に柔軟に対応できます。


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

public class DequeExample {
    public static void main(String[] args) {
        // DequeとしてLinkedListを使用
        Deque<Integer> stack = new LinkedList<>();
        
        // スタックにデータを積む（プッシュ）
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        // データを一つずつ取り出す（ポップ）
        System.out.println("取り出した値: " + stack.pop());
        System.out.println("残りのリスト: " + stack);
    }
}


取り出した値: 30
残りのリスト: [20, 10]

この例では、最後に追加した「30」が最初に取り出されています。このように、用途に応じて役割を変えられるのがLinkedListの隠れたメリットです。

6. LinkedListを使うべきではない「使いどころ」の注意点

ここまでメリットを中心に解説してきましたが、実際の開発現場ではArrayListの方が圧倒的に多く使われています。その理由は、現代のコンピュータのアーキテクチャにあります。

ArrayListはデータがメモリ上に連続して並んでいるため、CPUの「キャッシュ」という仕組みが効きやすく、繰り返し処理（ループ）が非常に高速です。一方でLinkedListはデータが分散しているため、キャッシュ効率が悪く、たとえ理論上は速いはずの処理でも、トータルのパフォーマンスでArrayListに負けることが多々あります。

また、一つ一つのノードがデータ本体だけでなく「前後の参照情報」を持っているため、メモリの消費量もArrayListより多くなります。数万件、数十万件といった膨大なデータを扱う場合、このメモリ消費の差が無視できなくなることもあるため注意が必要です。

7. 実際の開発での判断基準！どちらを選ぶべきか？

初心者が迷った時のための、実用的な判断基準をまとめます。ほとんどのケースでは、以下のフローチャートのような考え方で問題ありません。

まず、基本的にはArrayListを選択してください。データの検索や、特定の場所からの値の取得、リストの最後への追加がメインであれば、これ一択です。パフォーマンス面でもメモリ面でも安定しています。

では、どのような時にLinkedListを選ぶべきか？それは「リストの先頭や途中の要素を、頻繁に追加・削除する」という確信がある場合です。また、要素数がそれほど多くなく、スタックやキューとしての機能を直感的に使いたい場合も有効です。迷ったらまずはArrayListを使い、処理速度がボトルネックになった段階でLinkedListへの変更を検討するのがプロの進め方です。

8. Iteratorを使用した効率的な要素削除

LinkedListで要素をループさせながら削除する場合、通常のfor文で行うと非常に効率が悪くなることがあります。なぜなら、各要素の削除ごとにインデックスを再計算しようとしてしまうからです。このような場合は「Iterator（反復子）」を使うのが正解です。


import java.util.LinkedList;
import java.util.Iterator;

public class IteratorExample {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
        for(int i = 1; i <= 5; i++) numbers.add(i);
        
        Iterator<Integer> it = numbers.iterator();
        while(it.hasNext()) {
            Integer n = it.next();
            if(n % 2 == 0) {
                it.remove(); // 偶数だけを効率よく削除
            }
        }
        System.out.println("削除後のリスト: " + numbers);
    }
}


削除後のリスト: [1, 3, 5]

Iteratorを使うことで、現在地を保持したまま安全かつ高速にノードの切り離しが行えます。LinkedListの真価を発揮させるためには、こうした周辺のクラスの使い方もセットで覚えておくと、Java初心者から中級者へとステップアップできるでしょう。データの持ち方を知ることは、アルゴリズムとデータ構造を理解する第一歩です。