LinkedListの使い方

LinkedList クラスは List インターフェースおよび Deque インターフェースを実装したクラスの一つで、要素の数が可変のコレクションとなっています。それぞれの要素は前の要素と次の要素の情報を持っていて、先頭の要素から順番に辿っていくことで各要素へアクセスすることができます。要素の追加や削除を行ったときに影響を受けるのはその前後の要素だけのため、 ArrayList と比較して高速に行える場合がありますが、インデックスを指定して各要素へアクセスする場合に時間がかかる場合があります。ここでは Java における LinkedList クラスの使い方について解説します。

※ LinkedList クラスは java.util パッケージに含まれています。利用する場合は java.util.LinkedList をインポートしてください。

(Last modified: )

LinkedListクラスのインスタンスを作成する

最初に LinkedList クラスのインスタンスを作成する方法です。 new 演算子を使って次のように作成します。

LinkedList<データ型> 変数名 = new LinkedList<>();

データ型の部分には LinkedList の要素に格納する値のデータ型を指定します。例えば文字列を格納する場合は次のように記述します。

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

なお LinkedList は List インターフェースを実装したクラスなので、次のように List オブジェクトとして作成することもできます。 List オブジェクトとして作成した場合は、 LinkedList クラスでのみ定義されているメソッドは利用できなくなりますが、同じ List インターフェースを実装したクラスへ変換する場合などに便利です。

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

主に使用するメソッドは List インターフェースで定義されているので、通常は List オブジェクトとして作成することが多いようです。(なお List オブジェクトとして作成する場合は java.util.List をインポートしてください)。

データ型には基本データ型である int や double などは指定することができません。これらの数値を格納したい場合には、それぞれの基本データ型に対応したラッパークラスを使用してください。(ラッパークラスについての詳細は「ラッパークラスの利用」を参照されてください)。

基本データ型ラッパークラス
booleanBoolean
charCharacter
byteByte
shortShort
intInteger
longLong
floatFloat
doubleDouble

int 型の値を格納する LinkedList クラスのインスタンスを作成するには次のように記述します。

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

要素を追加する(add)

リストの最後に要素を追加するには LinkedList クラスで用意されている add メソッドを使います。書式は次のとおりです。

public boolean add(E e)

パラメータ:
e - このリストに追加される要素

戻り値:
true (Collection.add(E)で指定されているとおり)

定義:
インタフェース: Deque<E>
インタフェース: List<E>

引数に指定したオブジェクトを参照する要素をリストの最後に追加します。

実際には次のように記述します。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

リストには追加した順に要素が追加されていきます。各要素には追加したオブジェクトへの参照が格納されています。

要素を追加する(add)(1)

LinkedList では各要素は連続している必要はありません。要素には次の要素の位置を示す情報が格納されており、順番に辿っていくことですべての要素へアクセスすることができます。

なお Integer クラスなど基本データ型のラッパークラスのオブジェクトを格納するリストの場合、厳密には要素を追加するときに add メソッドの引数に Integer クラスのインスタンスを指定します。

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

list.add(Integer.valueOf(16));
list.add(Integer.valueOf(8));
list.add(Integer.valueOf(24));

ただラッパークラスにはオートボクシングという機能が利用できます。これは本来ラッパークラスのインスタンスを記述すべきところにラッパークラスに対応した基本データ型の値を記述すると、自動で変換してくれるというものです。よって、 Integer クラスのインスタンスを作成して追加しなくても、次のように int 型の値をそのまま記述することができます。

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

list.add(16);
list.add(8);
list.add(24);

指定した位置に要素を挿入する(add)

リストの指定した位置に要素を挿入するには先ほどとは引数が異なる LinkedList クラスで用意されている add メソッドを使います。書式は次のとおりです。

public void add(int index, E element)

パラメータ:
index - 指定の要素が挿入される位置のインデックス
element - 挿入される要素

例外:
IndexOutOfBoundsException - インデックスが範囲外の場合(index < 0||index> size())

定義:
インタフェース: List<E>

1 番目の引数に要素を挿入するインデックスを指定し、 2 番目の引数に挿入するオブジェクトを指定します。

指定できるインデックスは 0 から現在リストに追加されている要素の数までです。例えば現在 3 個の要素が追加されているのであれば 0 から 3 までの値が指定でき、 0 を指定した場合は先頭の位置、 3 を指定した場合はリストの最後に要素が挿入されます。

LinkedList クラスの場合は要素は連続しておらず、前の要素に次の要素の位置に関する情報が格納されているため、新しい要素を追加したときに追加した要素の前後の要素で位置に関する情報だけが変更されます。その為、要素そのものを並べ替える ArrayList と比べて比較的高速に要素を追加できます。

実際には次のように記述します。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

list.add(1, "千葉県");

インデックス 1 の位置に新しい要素を挿入しました。この場合、リストには次のように要素が追加されています。

指定した位置に要素を挿入する(add)(1)

要素の数を取得する(size)

リストに現在追加されている要素の数を取得するには LinkedList クラスで用意されている size メソッドを使います。書式は次のとおりです。

public int size()

戻り値:
このリスト内の要素数

定義:
インタフェース: Deque<E>
インタフェース: List<E>

メソッドを呼び出すと、現在リストに追加されている要素の数を戻り値として返します。

次のサンプルをみてください。

List<String> list = new LinkedList<>();
System.out.println(list.size());  // 0

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

System.out.println(list.size());  // 3

リストを作成した直後は要素の数が 0 です。 add メソッドを使って要素を 3 つ追加したあとで再度確認してみると要素の数は 3 となっています。

要素に格納されているオブジェクトを取得する(get)

リストに追加されている要素の中で指定したインデックスの要素に格納されているオブジェクトを取得するには LinkedList クラスで用意されている get メソッドを使います。書式は次のとおりです。

public E get(int index)

パラメータ:
index - 返される要素のインデックス

戻り値:
このリスト内の指定された位置にある要素

例外:
IndexOutOfBoundsException - インデックスが範囲外の場合(index < 0||index>= size())

定義:
インタフェース: List<E>

引数に指定したインデックスが示す要素に格納されているオブジェクト(実際はオブジェクトの参照が格納されています)を戻り値として返します。

次のサンプルをみてください。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

System.out.println(list.get(0));  // "東京都"
System.out.println(list.get(2));  // "神奈川県"

指定したインデックスの要素に格納されているオブジェクトを取得しました。

リストに追加されているすべての要素に格納されているオブジェクトを取得するには、 size メソッドと使って次のように記述することができます。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

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

または拡張 for 文を使用して次のように記述することができます。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

for(String s: list){
  System.out.println(s);
}

このように LinkedList の場合もインデックスを指定して要素に格納されているオブジェクトを取得することができますが、先頭の要素(または最後)から順番に辿っていく構造のため、全体の中央付近にある要素になるほど時間がかかる点は覚えておいてください。

要素を置き換える(set)

リストに追加されている要素の中で指定したインデックスの要素を別の要素に置き換えるには LinkedList クラスで用意されている set メソッドを使います。書式は次のとおりです。

public E set(int index, E element)

パラメータ:
index - 置換される要素のインデックス
element - 指定された位置に格納される要素

戻り値:
指定された位置に以前あった要素

例外:
IndexOutOfBoundsException - インデックスが範囲外の場合(index < 0||index>= size())

定義:
インタフェース: List<E>

1 番目の引数に指定したインデックスが示す要素を 2 番目の引数に指定した要素で置き換えます。

次のサンプルをみてください。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

list.set(1, "北海道");

インデックス 1 の位置の要素を新しい要素で置き換えました。この場合、リストには次のように要素が追加されています。

要素を置き換える(set)(1)

要素を削除する(remove)

リストに追加されている要素の中で指定したインデックスの要素を削除には LinkedList クラスで用意されている remove メソッドを使います。書式は次のとおりです。

public E remove(int index)

パラメータ:
index - 削除される要素のインデックス

戻り値:
指定された位置に以前あった要素

例外:
IndexOutOfBoundsException - インデックスが範囲外の場合(index < 0||index>= size())

定義:
インタフェース: List<E>

1 番目の引数に指定したインデックスが示す要素を削除します。削除された要素よりもあとに要素が存在していた場合は一つずつ前へずれていきます。

次のサンプルをみてください。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

list.remove(1);

インデックス 1 の位置の要素を削除ました。この場合、リストには次のように要素が追加されています。

要素を削除する(remove)(1)

リストに追加されている要素の中で指定したオブジェクトが含まれる要素を削除するには、先ほどとは引数が異なる LinkedList クラスで用意されている remove メソッドを使います。書式は次のとおりです。

public boolean remove(Object o)

パラメータ:
o - このリストから削除される要素(その要素が存在する場合)

戻り値:
指定された要素がこのリストに含まれていた場合はtrue

定義:
インタフェース: Deque<E>
インタフェース: List<E>

1 番目の引数に指定したオブジェクトが含まれる要素があった場合、その要素をを削除します。複数の要素で見つかった場合は、最初の要素を削除します。見つからなかった場合は何もしません。

次のサンプルをみてください。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

list.remove("大阪府");

"大阪府" を参照しているインデックス 1 の位置の要素を削除ました。

またリストに追加されているすべての要素を削除には LinkedList クラスで用意されている clear メソッドを使います。書式は次のとおりです。

public void clear()

-- --

定義:
インタフェース: List<E>

メソッドを呼び出すとリストに含まれているすべての要素を削除します。

次のサンプルをみてください。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");

list.clear();

すべての要素が削除されてリストが初期化されました。

要素を検索する(indexOf,lastIndexOf)

リストに追加されている要素の中で指定したオブジェクトが含まれる最初の要素を検索するには LinkedList クラスで用意されている indexOf メソッドを使います。書式は次のとおりです。

public int indexOf(Object o)

パラメータ:
o - 検索する要素

戻り値:
指定された要素がこのリスト内で最初に検出された位置のインデックス。その要素がこのリストにない場合は -1

定義:
インタフェース: List<E>

1 番目の引数に指定したオブジェクトを参照している要素のインデックスを戻り値として返します。リストの中に一致する要素が複数存在する場合は最初のインデックスを返します。

またリストに追加されている要素の中で指定したオブジェクトが含まれる最後の要素を検索するには LinkedList クラスで用意されている lastIndexOf メソッドを使います。書式は次のとおりです。

public int lastIndexOf(Object o)

パラメータ:
o - 検索する要素

戻り値:
指定された要素がこのリスト内で最後に検出された位置のインデックス。その要素がこのリストにない場合は -1

定義:
インタフェース: List<E>

1 番目の引数に指定したオブジェクトを参照している要素のインデックスを戻り値として返します。リストの中に一致する要素が複数存在する場合は最後のインデックスを返します。

次のサンプルをみてください。

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

list.add("東京都");
list.add("大阪府");
list.add("神奈川県");
list.add("大阪府");

System.out.println(list.indexOf("大阪府"));  // 1
System.out.println(list.lastIndexOf("大阪府"));  // 3

indexOf メソッドは最初に一致した要素のインデックスを返し、 lastIndexOf メソッドは最後に一致した要素のインデックスを返します。

サンプルコード

それでは簡単なサンプルプログラムを作って試してみます。テキストエディタで次のように記述したあと、 JSample2-1.java という名前で保存します。

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

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

    list.add("東京都");
    list.add("大阪府");

    for(String s: list){
      System.out.println(s);
    }

    System.out.println("-- --");

    list.add(1, "神奈川県");

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

    System.out.println("-- --");

    list.remove(0);

    for(String s: list){
      System.out.println(s);
    }

  }
}

コンパイルを行います。

javac -encoding UTF-8 JSample2_1.java

その後で、次のように実行してください。

java JSample2_1

LinkedListの使い方(1)

LinkedList クラスから List オブジェクトを作成し、要素の追加と挿入、そして要素の削除を行いました。

Dequeインターフェースで定義されているメソッド

LinkedList クラスは List インターフェースおよび Deque インターフェースを実装したクラスです。ここまで解説してきたメソッドは主に List インターフェースから継承したもので、 LinkedList クラスでは他に Deque インターフェースから継承したメソッドも利用できます。

add メソッドや size メソッドはどちらのインターフェースでも定義されているメソッドですが、 add メソッドでも引数にインデックスを指定するものは List インターフェースでのみ定義されています。 List オブジェクトを作成した場合は List インターフェースで定義されたメソッドのみ使用できます。 Deque インターフェースでのみ定義されたメソッドを使用する場合や両方のインターフェースで定義されたメソッドを使用する場合は LinkedList オブジェクトを作成してください。

Deque インターフェースから継承したメソッドには次のようなものがあります。(一部です)。

public void addFirst(E e)
・リストの先頭に要素を追加します

public void addLast(E e)
・リストの最後に要素を追加します

public E getFirst()
・リストの先頭の要素を取得します

public E getLast()
・リストの最後の要素を取得します

public E removeFirst()
・リストの先頭の要素を削除します

public E removeLast()
・リストの最後の要素を削除します

またキューとして利用するためのメソッドとして次のようなメソッドも用意されています。

public boolean offer(E e)
・リストの末尾に要素を挿入します

public E peek()
・リストの先頭の要素を取得します

public E poll()
・リストの先頭の要素を取得し、その要素を削除します

public void push(E e)
・リストの先頭に要素を挿入します

public E pop()
・リストの先頭の要素を取得し、その要素を削除します

-- --

Java における LinkedList クラスの使い方について解説しました。

( Written by Tatsuo Ikura )

Profile
profile_img

著者 / TATSUO IKURA

プログラミングや開発環境構築の解説サイトを運営しています。