Java LinkedListクラス
JavaのLinkedListクラスは、双方向リストとして実装されたコレクションです。AbstractSequentialListクラスを継承し、List, Deque, Queueの各インターフェースを実装しています。
LinkedListを使用する主な利点の1つは、挿入または削除時に後続のすべての要素をシフトする必要がある配列ベースのリストとは対照的に、リストへの要素の挿入または削除を一定時間可能にすることです。しかし、LinkedListでは、配列ベースのリストと比較して、要素へのランダムアクセスが遅くなります。
Java 連結リストの仕組み
LinkedListオブジェクトは一連のノードを含み、各ノードにはリスト内の次と前のノードへの参照が含まれています。以下は、LinkedListクラスが内部で持つNodeクラスのコードです。
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;
}
}双方向リストは、ノードを追加したり削除したりする際に、周囲のノードのnextとprevの参照を簡単に更新できるため、要素の挿入や削除が速くなります。しかし、各ノードが1つの参照だけでなく、2つの参照を格納する必要があるため、より多くのメモリを必要とします。
JavaではLinkedListクラスをimportするだけで簡単に実装することができます。これはjava.utilパッケージの一部で、Listインタフェースを実装しているので、要素の追加、削除、アクセスなど、標準的なJavaリストのすべてのメソッドと機能を備えています。
連結リストについては、CS基礎/上級/データ構造入門で詳しく学習できます。
Java LinkedListクラスの初期化
JavaでLinkedListクラスを初期化するには、まずjava.utilパッケージからLinkedListクラスをインポートする必要があります。次に、LinkedListコンストラクタを使用して新しいLinkedListオブジェクトを作成することができます。
たとえば、以下のようになります。
import java.util.LinkedList;
class Main{
public static void main(String[] args){
// 新しいLinkedListオブジェクトの初期化
LinkedList<String> linkedList = new LinkedList<String>();
}
}このコードでは、LinkedListクラスの新しいオブジェクトを作成し、型パラメータにStringを指定しています。これは、連結リストがStringデータ型の要素のみを保持できることを意味します。LinkedListクラスのデフォルトのコンストラクタを呼び出すために()が使用されており、新しい空の連結リストが作成されます。
また、LinkedListのコンストラクタに引数としてコレクションを渡すことで、特定の要素のコレクションでLinkedListを初期化することもできます。
import java.util.LinkedList;
import java.util.Arrays;
class Main{
public static void main(String[] args){
// 要素のコレクションを持つ新しいLinkedListオブジェクトを初期化
LinkedList<String> linkedList = new LinkedList<String>(Arrays.asList("Hello", "World"));
System.out.println(linkedList); // [Hello, World]
}
}Arrays.asListメソッドは、オブジェクトの配列から新しいListオブジェクトを作成するユーティリティメソッドです。この例では、HelloとWorldという2つの文字列を含むListオブジェクトを作成します。
最後に、LinkedListクラスのコンストラクタを使って新しいLinkedListオブジェクトを作成します。コンストラクタはArrays.asListが返すListオブジェクトを引数として受け取り、Listからの要素で新しいLinkedListオブジェクトを初期化します。
Java LinkedListクラスへ要素を追加
リストへの要素の追加は、addメソッドとaddAllメソッドを使用します。addメソッドはリストの末尾に要素を追加し、addAllメソッドは指定されたコレクション内のすべての要素をリストに追加します。
import java.util.LinkedList;
import java.util.Arrays;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>(Arrays.asList("Hello", "World"));
// 要素を追加
linkedList.add("d");
linkedList.addAll(Arrays.asList("e", "f"));
System.out.println(linkedList); // [Hello, World, d, e, f]
}
}また、リストの特定のインデックスに要素を挿入することもできます。しかしLinkeListはインデックスを保持していません。挿入位置を特定するためにノードを先頭または末尾からたどる必要があり、効率が悪くなる場合があります。
import java.util.LinkedList;
import java.util.Arrays;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>(Arrays.asList("Hello", "World"));
linkedList.add("d");
linkedList.addAll(Arrays.asList("e", "f"));
// インデックスを指定
linkedList.add(1, "x");
System.out.println(linkedList); // [Hello, x, World, d, e, f]
}
}Java LinkedListクラスの要素を削除
リストから要素を削除するには、removeメソッドを使います。removeメソッドは、引数なしでリストの最初の要素を削除したり、引数としてインデックスやオブジェクトを指定してリストから特定の要素を削除することができます。
import java.util.LinkedList;
import java.util.Arrays;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>(Arrays.asList("Hello", "World"));
linkedList.add("d");
linkedList.addAll(Arrays.asList("e", "f"));
linkedList.add(1, "x"); // [Hello, x, World, d, e, f]
// 要素の削除
linkedList.remove(); // [x, World, d, e, f]
linkedList.remove(2); // [x, World, e, f]
linkedList.remove("x"); // [World, e, f]
}
}Java LinkedListクラスのその他のメソッド
LinkedListクラスには、containsやindexOfといったリスト内の要素を検索するためのメソッドも用意されています。getメソッドで指定したインデックスの要素を取得し、setメソッドで指定したインデックスの要素を新しい要素に置き換えることができます。
import java.util.LinkedList;
import java.util.Arrays;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>(Arrays.asList("Hello", "World"));
linkedList.add("d");
linkedList.addAll(Arrays.asList("e", "f"));
linkedList.add(1, "x"); // [Hello, x, World, d, e, f]
// 連結リストに要素が含まれているかブール値で返す
boolean containsX = linkedList.contains("x"); // true
// 連結リスト内の要素のインデックス
int indexOfF = linkedList.indexOf("f"); // 5
// 連結リスト内の指定されたインデックスの値
String elementAtIndex2 = linkedList.get(2); // World
// 指定されたインデックスの値を設定
linkedList.set(2, "y"); // [Hello, x, y, d, e, f]
}
}LinkedListクラスには、Listインターフェースから継承したメソッドに加えて、addFirst, addLast, removeFirst, removeLastといったリストの先頭と末尾を操作するメソッドも含まれています。これらのメソッドを使うことで、LinkedListを使ったスタックやキューを実装することができます。
Java LinkedListクラスでの走査
Javaでは、LinkedListを繰り返し処理して、リスト内の要素にアクセスしたり変更したりすることがあります。LinkedListを反復処理する方法には、forループ、whileループ、for-eachループなど、いくつかの方法があります。
まずは、forループを使った例を見てみましょう。
import java.util.LinkedList;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>();
linkedList.add("Hello");
linkedList.add("World");
for (int i = 0; i < linkedList.size(); i++) {
String element = linkedList.get(i);
System.out.println(element);
}
// Hello
// World
}
}以下では、whileループを使ってLinkedListを反復処理する例を示します。
import java.util.LinkedList;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>();
linkedList.add("Hello");
linkedList.add("World");
int i = 0;
while (i < linkedList.size()) {
String element = linkedList.get(i);
System.out.println(element);
i++;
}
// Hello
// World
}
}iteratorを使う場合も見ておきましょう。
import java.util.LinkedList;
import java.util.ListIterator;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>();
linkedList.add("Hello");
linkedList.add("World");
ListIterator<String> iterator = linkedList.listIterator();
// hasNext() メソッドを使用して、リストを繰り返し処理します。
while (iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
}
// Hello
// World
}
}for-eachループを使ってLinkedListを反復処理することもできます。
LinkedListのルートインタフェースにIterableがあるので拡張for文（for-eachループ)を使うことができます。
import java.util.LinkedList;
class Main{
public static void main(String[] args){
LinkedList<String> linkedList = new LinkedList<String>();
linkedList.add("Hello");
linkedList.add("World");
for (String element : linkedList) {
System.out.println(element);
}
// Hello
// World
}
}この記事を書いた人
Jeffry Alvarado
Ex-Facebook Engineer 大学ではコンピュータサイエンスを専攻し、在学中に複数のインターンシップを経験。コンピュータサイエンスが学習できるプラットフォームRecursionを創業し、CTOとしてカリキュラム作成、ソフトウェア開発を担当。
