Deque

Java – LinkedListの使い方をわかりやすく解説

JavaのLinkedListは、リスト構造を実現するクラスで、java.utilパッケージに含まれています。

要素の挿入や削除が効率的で、特に中間操作に適しています。

LinkedListはListとDequeの両方を実装しており、リストとしてもキューやスタックとしても利用可能です。

主なメソッドには、要素を追加するadd()、削除するremove()、取得するget()、先頭や末尾を操作するaddFirst()やaddLast()などがあります。

例えば、LinkedList<String> list = new LinkedList<>();でリストを作成し、list.add("A");で要素を追加できます。

目次から探す

LinkedListとは何か

LinkedListは、Javaのコレクションフレームワークの一部であり、要素をリスト形式で管理するためのデータ構造です。

配列と異なり、要素の追加や削除が効率的に行えるため、特に頻繁に要素の変更が行われる場合に適しています。

LinkedListは、各要素がノードと呼ばれるオブジェクトで構成されており、各ノードは次のノードへの参照を持っています。

これにより、要素の順序を維持しながら、動的にサイズを変更することが可能です。

LinkedListの特徴

動的サイズ: 要素の追加や削除に応じてサイズが変わる。
双方向リスト: 各ノードが前後のノードを参照できる。
効率的な操作: 特に先頭や末尾での要素の追加・削除が高速。

LinkedListの構造

LinkedListは以下のような構造を持っています。

ノード	説明
データ	ノードが保持する値
次のノードへの参照	次のノードを指すポインタ
前のノードへの参照	前のノードを指すポインタ

このように、LinkedListは要素の追加や削除が容易であり、特にリストの先頭や末尾での操作が効率的です。

次のセクションでは、LinkedListの基本操作について詳しく見ていきます。

LinkedListの基本操作

LinkedListでは、要素の追加、削除、検索などの基本操作が簡単に行えます。

以下に、主な基本操作を紹介します。

要素の追加

LinkedListに要素を追加するには、addメソッドを使用します。

要素はリストの末尾に追加されます。

特定の位置に追加することも可能です。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>(); // LinkedListのインスタンスを作成
        // 要素を末尾に追加
        list.add("りんご"); // 1つ目の要素
        list.add("ばなな"); // 2つ目の要素
        // 特定の位置に要素を追加
        list.add(1, "オレンジ"); // 1番目の位置に追加
        // 結果を表示
        System.out.println(list); // [りんご, オレンジ, ばなな]
    }
}

[りんご, オレンジ, ばなな]

要素の削除

要素を削除するには、removeメソッドを使用します。

特定のインデックスやオブジェクトを指定して削除できます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("オレンジ");
        list.add("ばなな");
        // 特定のインデックスの要素を削除
        list.remove(1); // 1番目の要素を削除
        // 結果を表示
        System.out.println(list); // [りんご, ばなな]
    }
}

[りんご, ばなな]

要素の検索

要素を検索するには、containsメソッドを使用します。

指定した要素がリストに存在するかどうかを確認できます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("オレンジ");
        list.add("ばなな");
        // 要素が存在するか確認
        boolean hasBanana = list.contains("ばなな"); // ばななが存在するか
        // 結果を表示
        System.out.println("ばななはリストに存在しますか？: " + hasBanana); // true
    }
}

ばななはリストに存在しますか？: true

要素の取得

要素を取得するには、getメソッドを使用します。

指定したインデックスの要素を取得できます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("オレンジ");
        list.add("ばなな");
        // 特定のインデックスの要素を取得
        String fruit = list.get(1); // 1番目の要素を取得
        // 結果を表示
        System.out.println("1番目の要素: " + fruit); // オレンジ
    }
}

1番目の要素: オレンジ

これらの基本操作を理解することで、LinkedListを効果的に活用できるようになります。

次のセクションでは、LinkedListの応用操作について詳しく見ていきます。

LinkedListの応用操作

LinkedListは基本操作に加えて、さまざまな応用操作が可能です。

ここでは、要素の挿入、逆順、部分リストの取得、リストのクリアなどの応用操作について説明します。

要素の挿入

特定の位置に要素を挿入するには、addメソッドを使用します。

既存の要素を移動させることなく、新しい要素を挿入できます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("ばなな");
        // 1番目の位置に要素を挿入
        list.add(1, "オレンジ"); // 1番目の位置にオレンジを挿入
        // 結果を表示
        System.out.println(list); // [りんご, オレンジ, ばなな]
    }
}

[りんご, オレンジ, ばなな]

リストの逆順

LinkedListの要素を逆順にするには、Collections.reverseメソッドを使用します。

これにより、リストの順序を簡単に反転できます。

import java.util.LinkedList;
import java.util.Collections;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("ばなな");
        list.add("オレンジ");
        // リストを逆順にする
        Collections.reverse(list);
        // 結果を表示
        System.out.println(list); // [オレンジ, ばなな, りんご]
    }
}

[オレンジ, ばなな, りんご]

部分リストの取得

LinkedListから部分リストを取得するには、subListメソッドを使用します。

指定した範囲の要素を含む新しいリストを作成できます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("ばなな");
        list.add("オレンジ");
        list.add("ぶどう");
        // 部分リストを取得
        LinkedList<String> subList = new LinkedList<>(list.subList(1, 3)); // 1番目から2番目まで
        // 結果を表示
        System.out.println(subList); // [ばなな, オレンジ]
    }
}

[ばなな, オレンジ]

リストのクリア

LinkedListの全要素を削除するには、clearメソッドを使用します。

これにより、リストは空になります。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("りんご");
        list.add("ばなな");
        // リストをクリア
        list.clear(); // 全要素を削除
        // 結果を表示
        System.out.println("リストのサイズ: " + list.size()); // 0
    }
}

リストのサイズ: 0

これらの応用操作を活用することで、LinkedListをさらに効果的に利用できるようになります。

次のセクションでは、LinkedListのパフォーマンスと注意点について詳しく見ていきます。

LinkedListのパフォーマンスと注意点

LinkedListは、特定の操作において非常に効率的ですが、他のデータ構造と同様に、使用する際にはいくつかのパフォーマンス特性と注意点があります。

ここでは、LinkedListのパフォーマンスに関する情報と、使用時の注意点を説明します。

パフォーマンス特性

操作	時間計算量	説明
要素の追加	O(1)	リストの先頭または末尾に追加する場合。
要素の削除	O(1)	リストの先頭または末尾から削除する場合。
要素の検索	O(n)	特定の要素を検索する場合、リストを走査。
要素の取得	O(n)	特定のインデックスの要素を取得する場合。
部分リストの取得	O(n)	指定した範囲の要素を取得する場合。

注意点

メモリ使用量: LinkedListは、各ノードがデータと次のノードへの参照を持つため、配列に比べてメモリを多く消費します。

特に、大量のデータを扱う場合は、メモリの効率を考慮する必要があります。

ランダムアクセスの非効率性: LinkedListは、インデックスを指定して要素を取得する際に、リストの先頭から順に走査する必要があります。

そのため、ランダムアクセスが必要な場合は、ArrayListの方が適しています。

スレッドセーフではない: LinkedListは、複数のスレッドから同時にアクセスされる場合、スレッドセーフではありません。

スレッド間での安全な操作が必要な場合は、Collections.synchronizedListを使用するか、CopyOnWriteArrayListなどのスレッドセーフなコレクションを検討する必要があります。

ガーベジコレクション: LinkedListのノードは、要素が削除されるとガーベジコレクションの対象になりますが、参照が残っている場合はメモリリークの原因となることがあります。

適切にリストをクリアすることが重要です。

LinkedListは、特定の操作において非常に効率的であり、動的なデータ構造としての利点がありますが、メモリ使用量やランダムアクセスの非効率性などの注意点もあります。

これらを理解し、適切な場面で使用することで、LinkedListの利点を最大限に活かすことができます。

次のセクションでは、LinkedListを使った具体例について詳しく見ていきます。

LinkedListを使った具体例

LinkedListは、さまざまなシナリオで活用できます。

ここでは、実際のアプリケーションでの使用例をいくつか紹介します。

具体的には、タスク管理システム、履歴管理、キューの実装などの例を見ていきます。

1. タスク管理システム

タスクを管理するシステムでは、タスクの追加や削除が頻繁に行われます。

LinkedListを使用することで、これらの操作を効率的に行うことができます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> tasks = new LinkedList<>(); // タスクのリストを作成
        // タスクを追加
        tasks.add("メールの返信");
        tasks.add("会議の準備");
        tasks.add("レポートの作成");
        // タスクを表示
        System.out.println("現在のタスク: " + tasks);
        // タスクを完了したので削除
        tasks.remove("会議の準備");
        // 更新されたタスクを表示
        System.out.println("更新されたタスク: " + tasks);
    }
}

現在のタスク: [メールの返信, 会議の準備, レポートの作成]
更新されたタスク: [メールの返信, レポートの作成]

2. 履歴管理

ユーザーの操作履歴を管理する場合、LinkedListを使用することで、最新の操作を簡単に追加し、古い操作を削除することができます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> history = new LinkedList<>(); // 操作履歴のリストを作成
        // 操作を追加
        history.add("ファイルを開く");
        history.add("ファイルを編集");
        history.add("ファイルを保存");
        // 最新の操作を表示
        System.out.println("最新の操作: " + history.getLast()); // 最後の操作を取得
        // 古い操作を削除
        history.removeFirst(); // 最初の操作を削除
        // 更新された履歴を表示
        System.out.println("更新された履歴: " + history);
    }
}

最新の操作: ファイルを保存
更新された履歴: [ファイルを編集, ファイルを保存]

3. キューの実装

LinkedListは、キューの実装にも適しています。

FIFO(先入れ先出し)方式で要素を管理することができます。

import java.util.LinkedList;
public class App {
    public static void main(String[] args) {
        LinkedList<String> queue = new LinkedList<>(); // キューのリストを作成
        // 要素を追加(エンキュー)
        queue.add("タスク1");
        queue.add("タスク2");
        queue.add("タスク3");
        // キューの先頭の要素を取得(デキュー)
        String firstTask = queue.remove(); // 先頭の要素を削除し、取得
        // 結果を表示
        System.out.println("処理するタスク: " + firstTask); // タスク1
        System.out.println("残りのタスク: " + queue); // [タスク2, タスク3]
    }
}

処理するタスク: タスク1
残りのタスク: [タスク2, タスク3]

これらの具体例を通じて、LinkedListがどのように実際のアプリケーションで役立つかを理解できるでしょう。

次のセクションでは、LinkedListと他のコレクションの比較について詳しく見ていきます。

LinkedListと他のコレクションの比較

Javaのコレクションフレームワークには、さまざまなデータ構造が用意されています。

ここでは、LinkedListと他の主要なコレクション(ArrayList、HashSet、HashMap)との比較を行い、それぞれの特性や適切な使用シーンについて説明します。

1. LinkedList vs ArrayList

特徴	LinkedList	ArrayList
データ構造	双方向リスト	動的配列
要素の追加	O(1)(先頭・末尾)	O(1)(末尾)
要素の削除	O(1)(先頭・末尾)	O(n)(特定のインデックス)
ランダムアクセス	O(n)	O(1)
メモリ使用量	高い(ノードの参照が必要)	低い(配列のサイズに依存)

使用シーン: 頻繁に要素の追加や削除が行われる場合はLinkedListが適していますが、ランダムアクセスが必要な場合はArrayListが優れています。

2. LinkedList vs HashSet

特徴	LinkedList	HashSet
データ構造	双方向リスト	ハッシュテーブル
要素の追加	O(1)(末尾)	O(1)(平均)
要素の削除	O(n)	O(1)(平均)
重複要素	許可	許可しない
順序の保持	保持	保持しない

使用シーン: 順序を保持しながら重複を許可する場合はLinkedListが適していますが、重複を許可せず高速な検索が必要な場合はHashSetが適しています。

3. LinkedList vs HashMap

特徴	LinkedList	HashMap
データ構造	双方向リスト	ハッシュテーブル
要素の追加	O(1)(末尾)	O(1)(平均)
要素の削除	O(n)	O(1)(平均)
キーと値のペア	なし	あり
順序の保持	保持	保持しない(LinkedHashMapを除く)