JavaにおけるArrayListとLinkListの違いの分析

1.ArrayList は動的配列に基づいたデータ構造を実装し、LinkedList はリンク リストに基づいたデータ構造を実装します。
2. 取得および設定のランダム アクセスの場合、ArrayList はランダムに配置できるため、LinkedList よりも優れていますが、LinkedList はポインタをノードに段階的に移動する必要があります。 (配列やリンクリストを参考に考えてください)
3. 追加および削除の新規操作と削除操作の場合、LinedList はポインターを変更するだけで済みますが、ArrayList は削除されたオブジェクトのスペースを埋めるためにデータを移動する必要があります。

ArrayList と LinkedList は、一連のオブジェクト参照を格納するために使用される 2 つのコレクション クラスです。たとえば、ArrayList を使用して一連の文字列または整数を保存できます。では、ArrayList と LinkedList のパフォーマンスの違いは何でしょうか? ArrayList をいつ使用する必要があるか、また LinkedList を使用する必要があるのはどのような場合ですか?

1つ。時間の複雑さ

最初の重要な点は、ArrayList の内部実装が基本的なオブジェクト配列に基づいているため、get メソッドを使用してリスト内の任意の要素にアクセスする場合 (ランダム アクセス)、LinkedList よりも高速であるということです。 LinkedList の get メソッドは、リストの一方の端からもう一方の端まで順番にチェックします。 LinkedList の場合、リスト内の特定の要素にこれより速くアクセスする方法はありません。

大きなリストがあり、そのリスト内の要素が ArrayList タイプまたは LinkedList タイプであるとします。次に、このリストに対して二分検索を実行します。ArrayList と LinkedList のクエリ速度については、次のようになります。次のプログラムを参照してください。

LinkedList の消費時間: 2596

この結果は修正されていませんが、基本的に ArrayList の時間は LinkedList の時間よりも大幅に短くなります。したがって、この場合は LinkedList を使用しないでください。二分探索法はランダム アクセス (randomaccess) 戦略を使用しており、LinkedList は高速ランダム アクセスをサポートしていません。 LinkedList へのランダム アクセスにかかる時間は、リストのサイズに比例します。これに応じて、ArrayList のランダム アクセスにかかる時間は固定されます。

これは、ArrayList のパフォーマンスが常に LinkedList よりも優れていることを意味しますか?これは必ずしも正しいとは限りません。場合によっては、LinkedList の方が ArrayList よりもパフォーマンスが良く、一部のアルゴリズムは LinkedList に実装された方が効率的です。たとえば、Collections.reverse メソッドを使用してリストを反転すると、パフォーマンスが向上します。

このような例を見てください。リストがあり、それに対して多数の挿入および削除操作を実行したい場合、この場合は LinkedList の方が良い選択肢になります。次の極端な例を考えてみましょう。ここでは、リストの先頭に要素を繰り返し挿入します。

現時点での出力は次のとおりです: ArrayList Takes: 2463

LinkedList の所要数: 15

これは、前の例の結果とはまったく逆です。要素が ArrayList の先頭に追加されると、既存の要素はすべて後方に移動されます。これは、データの移動とコピーのオーバーヘッドを意味します。対照的に、LinkedList の先頭に要素を追加すると、要素にレコードが割り当てられ、2 つのリンクが調整されます。 LinkedList の先頭に要素を追加するコストは固定ですが、ArrayList の先頭に要素を追加するコストは ArrayList のサイズに比例します。

二。空間の複雑さ

LinkedList にはプライベート内部クラスがあり、次のように定義されています。

プライベート静的クラス エントリ {
オブジェクト要素。
次にエントリーします。
前のエントリ;
}

各 Entry オブジェクトは、リスト内の要素だけでなく、LinkedList 内の前の要素と次の要素も参照します。 1000 個の要素を持つ LinkedList オブジェクトには 1000 個の Entry オブジェクトがリンクされており、各オブジェクトはリスト内の要素に対応します。この場合、LinkedList 構造にはこれら 1000 個の Entity オブジェクトの関連情報を格納する必要があるため、大量のスペースのオーバーヘッドが発生します。

ArrayList は、組み込み配列を使用して要素を格納します。この配列の開始容量は 10 です。配列を拡張する必要がある場合、新しい容量は次の式に従って取得されます: 新しい容量 = (古い容量 * 3)/2+ 1、つまり容量は毎回約50％増加します。つまり、多数の要素を含む ArrayList オブジェクトがある場合、この無駄なスペースは ArrayList の動作方法によって引き起こされます。新しい要素を格納するのに十分なスペースがない場合は、新しい要素を追加できるように配列を再割り当てする必要があります。アレイを再割り当てすると、パフォーマンスが大幅に低下します。 ArrayList に含まれる要素の数がわかっている場合は、コンストラクターを通じて容量を指定できます。 TrimToSize メソッドを使用して、ArrayList が割り当てられた後に無駄なスペースを削除することもできます。

三つ。要約する

ArrayList と LinkedList にはそれぞれ、パフォーマンスの点で独自の長所と短所があり、それぞれに独自の用途があります。一般に、次のように説明できます。

パフォーマンスの概要:

1. ArrayList と LinkedList の両方で、リストの末尾に要素を追加するコストは固定されています。 ArrayList の場合、主に追加された要素を指す内部配列に項目を追加します。これにより、配列が再割り当てされる場合があります。LinkedList の場合、このオーバーヘッドは均一であり、内部 Entry オブジェクトが割り当てられます。

2. ArrayList の途中で要素を挿入または削除すると、リスト内の残りの要素が移動されますが、LinkedList の途中で要素を挿入または削除すると、コストが固定されます。

3． LinkedList は、効率的なランダム要素へのアクセスをサポートしていません。

4． ArrayList のスペースの浪費は、主にリストの最後に一定量のスペースを確保することに反映されますが、LinkedList のスペース消費は、その各要素がかなりの量のスペースを消費する必要があることに反映されます。

これは次のように言えます。操作がデータの列の前や中央ではなく後にデータを追加する場合、要素にランダムにアクセスする必要がある場合、操作がデータ列の前にあるときに ArrayList を使用するとパフォーマンスが向上します。データの列 途中でデータを追加または削除し、要素に順番にアクセスする場合は、LinkedList を使用する必要があります。

JavaのArrayListとListの違い

リストコレクション
List は Collection インターフェイスを継承します。 List は順序付けされたコレクションです。List 内の要素は、インデックス (シーケンス番号: コレクション内の要素の位置情報) に基づいて取得/削除/挿入できます。

Set コレクションとは異なり、List では要素の重複が許可されます。 e1.equals(e2) の条件を満たす e1 および e2 オブジェクト要素は、List コレクションに同時に存在できます。もちろん、要素の重複を許可しない List 実装クラスもあります。
同時に、List は ListIterator インターフェイス オブジェクトを返す listIterator() メソッドも提供します。 Iterator インターフェイスと比較すると、ListIterator には要素を追加、削除、設定するためのメソッドが追加されており、前方または後方への移動も可能です。

リストとコレクションの関係:
java.util.コレクション[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]

List インターフェースの実装クラスには主に ArrayList、LinkedList、Vector、Stack などが含まれます。

父と子の関係。
List はインターフェイスであり、ArrayList はこのインターフェイスを継承して実装します。
これを使用するときは、通常は ArrayList を使用しますが、List は次のように使用できます。

コレクションインターフェース
コレクションは最も基本的なコレクション インターフェイスです。コレクションはオブジェクトのセット、つまりコレクションの要素を表します。コレクションによっては、同一の要素を許可するものと許可しないものがあります。ある種のものとそうでないものがあります。 Java SDK は Collection を直接継承するクラスを提供しません。Java SDK が提供するクラスはすべて、List や Set など、Collection を継承する「サブインターフェイス」です。
Collection インターフェイスを実装するすべてのクラスは、空の Collection を作成するためのパラメーターなしのコンストラクターと、新しい Collection を作成するための Collection パラメーターのコンストラクターという 2 つの標準コンストラクターを提供する必要があります。入力 Collection には同じ要素があります。後者のコンストラクターを使用すると、ユーザーはコレクションをコピーできます。

コレクション内の各要素を反復処理するにはどうすればよいですか? Collection の実際のタイプに関係なく、コレクション内の各要素に 1 つずつアクセスするために使用できるイテレータを返す iterator() メソッドがサポートされています。一般的な使用方法は次のとおりです。
Iterator it = collection.iterator() // イテレータを取得します。
while(it.hasNext()) {
Object obj = it.next() // 次の要素を取得します。
}
Collection インターフェイスから派生した 2 つのインターフェイスは、List と Set です。

リストインターフェイス:
リストは順序付けされたコレクションです。このインターフェイスを使用すると、各要素の挿入位置を正確に制御できます。ユーザーは、Java 配列に似たインデックス (配列の添え字に似たリスト内の要素の位置) を使用して、リスト内の要素にアクセスできます。
以下で説明する Set とは異なり、List では同じ要素が許可されます。
Collection インターフェイスに必要な iterator() メソッドに加えて、List には ListIterator インターフェイスを返す listIterator() メソッドも用意されています。標準の Iterator インターフェイスと比較して、ListIterator には追加できる add() メソッドやその他のメソッドがいくつかあります。要素を削除、設定し、前方または後方に移動します。
List インターフェイスを実装する一般的なクラスは、LinkedList、ArrayList、Vector、Stack です。

LinkedList クラス
LinkedList は List インターフェイスを実装し、null 要素を許可します。さらに、LinkedList は、LinkedList の先頭または末尾に追加の get、remove、および insert メソッドを提供します。これらの操作により、LinkedList をスタック、キュー、または両端キューとして使用できるようになります。
LinkedList には同期メソッドがないことに注意してください。複数のスレッドが同時にリストにアクセスする場合、スレッド自体がアクセス同期を実装する必要があります。回避策の 1 つは、リストの作成時に同期されたリストを構築することです。
リスト list = Collections.synchronizedList(new LinkedList(...));

ArrayList クラス
ArrayList は可変サイズの配列を実装します。 null を含むすべての要素が許可されます。 ArrayList は同期されていません。
size、isEmpty、get、set メソッドの実行時間は一定です。ただし、add メソッドのコストは償却定数であり、n 個の要素を追加するには O(n) 時間がかかります。他の方法では実行時間が直線的になります。
各 ArrayList インスタンスには容量 (Capacity) があり、これは要素を格納するために使用される配列のサイズです。この容量は、新しい要素が追加されると自動的に増加しますが、増加アルゴリズムは定義されていません。多数の要素を挿入する必要がある場合は、挿入前に ensureCapacity メソッドを呼び出して ArrayList の容量を増やし、挿入効率を向上させることができます。
LinkedList と同様に、ArrayList も非同期です。

概要: スタックやキューなどの操作が関係する場合は、List の使用を検討する必要があります。要素を迅速に挿入および削除する必要がある場合は、LinkedList を使用する必要があります。要素への高速なランダム アクセスが必要な場合は、ArrayList を使用する必要があります。
将来 ArrayList を LinkedList に置き換える必要がある場合に、クライアント コードを変更する必要がないように、ArrayList の代わりに List を返すなど、実際の型ではなくインターフェイスを返すようにしてください。これは抽象化のためのプログラミングです。