LinkedList subclass takes you to learn advanced features of Java language

本セクションの目標

LinkedList サブクラスの操作方法を学習し、ArrayList と LinkedList の違いを理解します。

LinkedList サブクラス

List インターフェイスには、もう 1 つよく使われるサブクラスがあります。それが LinkedList です。クラス名から推測できる通り、連結リストに基づく実装です。まず LinkedList の定義を確認しましょう。

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
image.pngLinkedList クラスの継承関係

使用例：LinkedList を使ったコレクション操作

import java.util.LinkedList;
import java.util.List;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
List all = new LinkedList();
all.add("Hello");
all.add("Hello");
all.add("Wolrd");
all.add("MLDN");
all.forEach(System.out::println); //Hello Hello World MLDN
}
}
プログラムの出力だけを見ると、ArrayList とまったく同じ結果になります。しかし内部の実装メカニズムは完全に異なります。まず、LinkedList のコンストラクタには ArrayList のような初期サイズを指定する方法がなく、パラメーターなしのコンストラクタ「public LinkedList()」のみが提供されている点に注目してください。次に add() メソッドの具体的な実装を確認します。

public boolean add(E e) {
linkLast(e);
return true;
}
以前カスタム連結リストを作成した際は、渡されたデータが null かどうかを判定し、null の場合は保存しないようにしていました。しかし LinkedList ではそのような処理を行わず、すべてのデータを保存できます。このメソッドは linkLast() メソッド（末尾ノードの後に追加）を呼び出しています。

void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
LinkedList クラスに保存されるデータは、Node ノードによってカプセル化されています。同時に、プログラムの実行パフォーマンスを向上させるため、毎回最後に追加されたノード（末尾ノード）を保持することで、データ追加時の再帰的処理を回避しています。データ追加時には、保存データ数を加算する必要があります。

上記の分析から、LinkedList がカプセル化しているのは連結リストの実装であることがわかります。
面接質問：
ArrayList と LinkedList の違いは何ですか？

ArrayList は配列に基づくコレクション操作であり、LinkedList は連結リストに基づくコレクション操作です。

List コレクションで get() メソッドを使ってインデックスに基づいてデータを取得する場合、ArrayList の時間計算量は「O(1)」ですが、LinkedList の時間計算量は「O(n)」です（n はコレクションの長さ）。

ArrayList を使用する場合、デフォルトの初期化オブジェクト配列サイズは 10 です。容量が不足すると 2 倍に拡張されます。大量のデータを保存する場合、ガベージの発生やパフォーマンスの低下を引き起こす可能性がありますが、そのような場合は LinkedList クラスを使用して保存できます。