リスト

ArrayListとLinkedListの違い、長所と短所、およびアプリケーションシナリオ



Difference Advantages



ArrayListとLinkedListはどちらも、Listインターフェイスを実装するコンテナクラスであり、一連のオブジェクト参照を格納するために使用されます。それらはすべて、要素の追加、削除、および変更を操作できます。それらの違い、長所と短所は何ですか？これをソースコードとデータ構造で説明します。

ArrayListとLinkedListのおおよその違いは次のとおりです。

  1. ArrayListは動的配列に基づくデータ構造を実装し、LinkedListはリンクリスト構造に基づいています。
  2. ランダムアクセスのgetメソッドとsetメソッドの場合、LinkedListはポインターを移動するため、ArrayListはLinkedListよりも優れています。
  3. 追加および削除操作、追加および削除の場合、ArrayListはデータを移動する必要があるため、LinkedListが支配的です。
具体的な手順
ArrayListソースコード：

画像
ソースコードでわかるように、ArrayListは動的配列に基づくデータ構造を実装し、配列は連続したメモリ空間です。メモリでは、次のパターンを簡単に表すことができます。
画像
データを格納するときに配列が順番に格納されるため、データを格納するためのメモリも連続しているため、彼の特徴は 読み取ったデータのアドレス指定が簡単で、挿入と削除が困難です 。データを読み取るときに、データを取得する場所（インデックス）を配列に指示するだけでよい理由を簡単に説明します。配列は、必要な場所のデータを直接取得します。これらの保存されたデータのメモリは連続しているため、挿入と削除はより困難です。挿入および削除するには、配列全体のデータの位置を変更する必要があります。例：数値0-> 1-> 2-> 3-> 4の配列は、配列のデータを5つのメモリアドレスに格納しますが、4にデータを挿入する必要があります。つまり、4の先頭にあります。 、バックメモリ内のすべてのデータを1つの位置に戻す必要があり、これには非常に時間がかかります。
そのため、ArrayListの場合、コレクションの最後で要素を削除または追加するのに同じ時間がかかりますが、リストの途中でパーツを追加または削除するのにかかる時間は大幅に増加します。ただし、インデックスに基づいて要素を検索する場合は高速です。



ArrayListソースコードの説明の他の部分を添付します
LinkedListソースコード：

画像
ソースコードでは、LinkedListが単一リンクリストに基づいていることがわかります。単一リンクリストのリンクリストオブジェクトは、ノードリストの最初のノードオブジェクトを指す最初の参照を維持し、各ノードオブジェクトは次の参照を維持し、次の参照は次のノードオブジェクトを指します（ここでの参照：参照ポイントはノードオブジェクトです：ノードオブジェクトには、保存されたデータと次の参照が含まれます）。
LinkedListはメモリ内で簡略化できます
画像
最初の位置に要素を挿入する必要がある場合、図は次のようになります。最初の参照はリンクリストに挿入する必要のあるノードオブジェクトを指し、新しいノードオブジェクトの次の参照は元の最初の参照を指します。ノードオブジェクト
画像
したがって、LinkedListの場合、コレクション内の任意の場所に要素を挿入および削除するのに同じ時間がかかりますが、インデックスに基づいて要素をクエリする場合は時間がかかります。

ArrayListとLinkedListの欠点は次のとおりです。

  1. ArrayListおよびLinkedListの場合、リストの最後に要素を追加するオーバーヘッドが修正されました。 ArrayListの場合、主に追加された要素を指すアイテムを内部配列に追加します。場合によっては、配列がLinkedListに再割り当てされ、このオーバーヘッドが均一になり、内部Entryオブジェクトが割り当てられます。
  2. ArrayListコレクションに要素が追加または削除されると、現在のリストのすべての要素が移動されます。 LinkedListコレクションの要素を追加または削除するオーバーヘッドが修正されました。
  3. LinkedListコレクションは、2次動作を生成できるため、効率的なランダムアクセス（RandomAccess）をサポートしていません。
  4. ArrayListのスペースの浪費は、主にリストリストの最後にある特定の容量スペースの予約に反映され、LinkedListのスペースコストは、その各要素がかなりのスペースを消費する必要があるという事実に反映されます。

ArrayListとLinkedListのアプリケーションシナリオは次のとおりです。

ArrayListはより多くの場合に使用されますが、挿入と削除は少なく、LinkedListは、クエリが少なく、挿入と削除が多い場合に使用されます。