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]にあります。