1.はじめに
LinkedList
は、
https://docs.oracle.com/javase/の二重リンクリストの実装です。
8/docs/api/java/util/List.html[リスト]
および
Deque
インタフェース。これはすべてのオプションのリスト操作を実装し、すべての要素（
null
を含む）を許可します。
2.特徴
以下に
LinkedList
の最も重要なプロパティを見つけることができます。
-
リストにインデックスを付ける操作は、リストからリストをトラバースします。
指定されたインデックスに近い方の先頭または末尾
**
同期
ではありません
-
その
イテレータ
そして
ListIterator
イテレータは
fail-fast
（つまり、イテレータの作成後、リストが
修正、
ConcurrentModificationException
スローされます）
** すべての要素はノードであり、次への参照を保持します。
前のもの
** 掲載順を維持する
LinkedList
は同期されていませんが、
https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.Listを呼び出すことによって、その同期バージョンを取得できます。
– [Collections.synchronizedList]
メソッド。
List list = Collections.synchronizedList(new LinkedList(...));
3.
ArrayList
との比較
どちらも
List
インターフェースを実装していますが、それらのセマンティクスは異なります。どちらを使用するかの決定に間違いなく影響します。
3.1. 構造
ArrayList
は、
Array
を基にしたインデックスベースのデータ構造です。 O（1）と同等のパフォーマンスで、要素へのランダムアクセスを提供します。
一方、
LinkedList
はそのデータを要素のリストとして格納し、すべての要素はその前後の要素にリンクされます。この場合、アイテムの検索操作の実行時間はO（n）になります。
3.2. オペレーション
要素がコレクション内の任意の位置に追加されたときに配列のサイズを変更したりインデックスを更新したりする必要はなく、周囲の要素内の参照のみが変更されるため、アイテムの挿入、追加、削除操作は
LinkedList
で高速です。
3.3. メモリ使用量
LinkedList
の各ノードには前の要素と次の要素の2つの参照が格納されているのに対し、
LinkedList
は
ArrayList
よりも多くのメモリを消費します。
4.使い方
以下は
LinkedList
の使用方法を示すコードサンプルです。
4.1. 作成
LinkedList<Object> linkedList = new LinkedList<>();
4.2. 要素を追加する
LinkedList
は
List
と
Deque
インタフェースを実装しています。標準の
add（）
と
addAll（）
メソッドの他に、それぞれ
addFirst（）
と
addLast（）
を見つけることができます。
4.3. 要素を削除する
要素の追加と同様に、このリスト実装は
removeFirst（）
と
removeLast（）を提供します。 +
また、ブール値を返す便利なメソッド
removeFirstOccurence（）
および
removeLastOccurence（）
があります（コレクションに指定の要素が含まれる場合はtrue）。
4.4. キュー操作
Deque
インターフェースはキューのような振る舞いを提供します（実際には
Deque
は
Queue
インターフェースを拡張します）:
linkedList.poll();
linkedList.pop();これらのメソッドは最初の要素を取得してそれをリストから削除します。
poll（）
と
pop（）
の違いは、
pop
が空のリストに
NoSuchElementException（）
をスローするのに対して、
poll
はnullを返すことです。
API
pollFirst（）
と
pollLast（）
も利用できます。
たとえば、
push
APIの仕組みは次のとおりです。
linkedList.push(Object o);これは、要素をコレクションの先頭として挿入します。
LinkedList
には他にもたくさんのメソッドがありますが、そのほとんどは既に
Lists
を使っているユーザーにはおなじみのはずです。
Deque
によって提供される他のものは「標準的な」メソッドに代わる便利な方法かもしれません。
完全なドキュメントはhttps://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html[ここ]にあります。
5.まとめ
ArrayList
は通常、デフォルトの
List
実装です。
しかし、一定のアクセス時間および効果的なメモリ使用量よりも一定の挿入／削除時間（例えば、頻繁な挿入／削除／更新）に対する好みなど、
LinkedList
を使用することがより適している特定の使用例がある。
コードサンプルはhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[over on GitHub]にあります。
