[解決済み] JavaでArrayListではなくLinkedListを使用するのはいつですか？

質問

私はいつもシンプルに使う派です。

List<String> names = new ArrayList<>();

の型名としてインターフェイスを使用しています。 ポータビリティ というような質問をされたときに、自分のコードを作り直せるようにするためです。

どのような場合に LinkedList よりも ArrayList とか、その逆は？

解決方法は？

概要 ArrayList と ArrayDeque が望ましい。 多数 よりも多くのユースケースで LinkedList . よくわからない場合は、まず ArrayList .

TLDR、ArrayListでは要素へのアクセスに一定時間[O(1)]、要素の追加にO(n) 時間[最悪の場合]がかかります。LinkedListでは、要素の追加はO(n)時間、アクセスもO(n)時間かかりますが、ArrayListよりもLinkedListの方が多くのメモリを使用します。

LinkedList と ArrayList は、List インターフェースの 2 つの異なる実装です。 LinkedList は二重連結リストで実装しています。 ArrayList は、動的にサイズを変更する配列で実装されています。

標準的なリンクリストや配列の操作と同様に、様々なメソッドは異なるアルゴリズムのランタイムを持つことになります。

について LinkedList<E>

• get(int index) は O(n) と n/4 のステップを平均しています。 O(1) 時 index = 0 または index = list.size() - 1 (この場合 getFirst() と getLast() ). の主なメリットの1つは LinkedList<E>
• add(int index, E element) は O(n) と n/4 のステップを平均しています。 O(1) 時 index = 0 または index = list.size() - 1 (この場合 addFirst() と addLast() / add() ). の主なメリットの1つは LinkedList<E>
• remove(int index) は O(n) と n/4 のステップを平均しています。 O(1) 時 index = 0 または index = list.size() - 1 (この場合 removeFirst() と removeLast() ). の主なメリットの1つは LinkedList<E>
• Iterator.remove() は O(1) . の主なメリットの1つは LinkedList<E>
• ListIterator.add(E element) は O(1) . の主なメリットの1つは LinkedList<E>

^{注：多くの操作には n/4 のステップを平均しています。 一定 最良の場合（例：index = 0）のステップ数、および n/2 最悪の場合(リストの真ん中)の歩数}

について ArrayList<E>

• get(int index) は O(1) . の主なメリット ArrayList<E>
• add(E element) は O(1) 償却されるが O(n) 配列のサイズ変更とコピーが必要なため，最悪の場合
• add(int index, E element) は O(n) と n/2 ステップを平均して）
• remove(int index) は O(n) と n/2 ステップを平均して）
• Iterator.remove() は O(n) と n/2 ステップを平均して）
• ListIterator.add(E element) は O(n) と n/2 ステップを平均して）

^{注：多くの操作には n/2 のステップを平均しています。 定数 最良の場合のステップ数（リスト終了）。 n 最悪の場合（リストの先頭）のステップ数}

LinkedList<E> 定時挿入・定時削除を可能にする イテレータを使用した しかし、要素の順次アクセスのみです。言い換えれば、リストを前方または後方に歩くことができますが、リスト内の位置を見つけるにはリストのサイズに比例した時間がかかります。Javadocには次のように書かれています。 リストのインデックスを作成する操作は、リストの先頭または末尾のどちらか近いほうから行います。 ということで、それらのメソッドは O(n) ( n/4 ステップ)を平均していますが O(1) に対して index = 0 .

ArrayList<E> 一方、高速なランダムアクセスが可能で、任意の要素を定速で読み取ることができます。しかし、末尾以外の要素を追加したり削除したりするには、後者の要素をすべてずらして、隙間を作ったり埋めたりする必要があります。また，配列の容量を超えて要素を追加すると，新しい配列（1.5 倍のサイズ）が確保され，古い配列が新しい配列にコピーされます． ArrayList は O(n) は、最悪の場合、平均で一定となる。

ですから、やろうとする操作に応じて、実装を選択する必要があります。どちらの種類のListに対しても、反復処理は実質的に同等に安い。(リストに対する反復処理は ArrayList の方が技術的には速いのですが、よほどパフォーマンスにこだわることをしない限り、気にする必要はないでしょう -- どちらも定数ですから)。

を使用する主な利点は LinkedList は、既存のイテレータを再利用して要素の挿入や削除を行う場合に発生します。これらの操作は O(1) を局所的に変更するだけでよい。配列リストでは、配列の残りを 移動 (コピー)されます。一方、シークを LinkedList のリンクをたどることを意味します。 O(n) ( n/2 ステップ)であるのに対し、最悪の場合 ArrayList は数学的に計算され、アクセスすることができます。 O(1) .

を使用するもう一つの利点は LinkedList は、リストの先頭に追加したり削除したりするときに発生する操作です。 O(1) であるのに対して O(n) に対して ArrayList . ただし ArrayDeque の代替となる可能性があります。 LinkedList を頭から追加したり削除したりするためのものですが、これは List .

また、大きなリストがある場合、メモリの使用量も異なるので注意が必要です。の各要素は LinkedList は、次と前の要素へのポインタも保存されるため、より多くのオーバーヘッドが発生します。 ArrayLists はこのようなオーバーヘッドがありません。しかし ArrayLists は、実際に要素が追加されたかどうかに関係なく、容量として割り当てられているのと同じだけメモリを消費します。

デフォルトの初期容量は ArrayList はかなり小さいです (Java 1.4 - 1.8 では 10)。しかし、基礎となる実装が配列であるため、要素をたくさん追加すると配列のサイズを変更しなければなりません。要素を大量に追加することがわかっている場合にサイズ変更のコストが高くなるのを避けるために ArrayList を、より大きな初期容量で設定します。

データ構造の観点からこの2つの構造を理解すると、LinkedListは基本的に先頭のNodeを含むシーケンシャルなデータ構造である。Nodeは、T型（ジェネリックスによって受け入れられる）の値と、それにリンクされたNodeへの参照という、2つのコンポーネントのラッパーである。したがって、これは再帰的なデータ構造であると断言できる（あるNodeは別のNodeを含み、そのNodeは別のNodeを持つ、という具合に）。LinkedListでは、上記のように要素の追加に線形時間がかかる。

ArrayListは成長可能な配列です。通常の配列と同じです。そのため、要素が追加され、ArrayListがすでに満杯になると、以前のサイズよりも大きなサイズの別の配列が作成されます。そして、前の配列から新しい配列に要素がコピーされ、追加される要素も指定されたインデックスに配置されます。