Java

Java-ArrayList vs. LinkedList vs. Vector



Java Arraylist Vs Linkedlist Vs



1.リストの概要

リストは、その名前が示すように、要素の順序付けられたシーケンスです。 Listについて話すときは、一意で順序付けられていない要素のセットであるSetと比較することをお勧めします。以下は、コレクションのクラス階層図です。階層図から、Javaコレクションの一般的な考え方を理解できます。



2.ArrayListとLinkedListとVector



階層図から、それらはすべてリストインターフェイスを実装しています。それらは使用法と非常によく似ています。それらの主な違いは、さまざまな操作でさまざまなパフォーマンスを引き起こす実装です。

ArrayListは、サイズ変更可能な配列として実装されます。 ArrayListに要素が追加されると、そのサイズは動的に増加します。 ArrayListは本質的に配列であるため、その要素にはgetメソッドとsetメソッドを使用して直接アクセスできます。

LinkedListは、二重リンクリストとして実装されます。追加と削除でのパフォーマンスはArraylistよりも優れていますが、getメソッドとsetメソッドでは劣ります。



VectorはArrayListと似ていますが、同期されています。

プログラムがスレッドセーフである場合は、ArrayListの方が適しています。 VectorとArrayListは、要素が追加されるにつれて、より多くのスペースを必要とします。 Vectorは毎回配列サイズを2倍にしますが、ArrayListは毎回サイズの50％増加します。ただし、LinkedListは、offer（）、peek（）、poll（）など、ArrayListやVectorよりも多くのメソッドを追加するQueueインターフェイスも実装しています。

注：ArrayListのデフォルトの初期容量はかなり小さいです。より高い初期容量でArrayListを作成することは良い習慣です。これにより、サイズ変更のコストを回避できます。

3.ArrayListの例

ArrayList al = new ArrayList() al.add(3) al.add(2) al.add(1) al.add(4) al.add(5) al.add(6) al.add(6) Iterator iter1 = al.iterator() while(iter1.hasNext()){ System.out.println(iter1.next()) }

4.LinkedListの例

LinkedList ll = new LinkedList() ll.add(3) ll.add(2) ll.add(1) ll.add(4) ll.add(5) ll.add(6) ll.add(6) Iterator iter2 = ll.iterator() while(iter2.hasNext()){ System.out.println(iter2.next()) }

上記の例に示されているように、それらは使用法に似ています。本当の違いは、基礎となる実装と操作の複雑さです。

5.ベクトル

VectorはArrayListとほぼ同じですが、違いはVectorが同期されていることです。このため、ArrayListよりもオーバーヘッドがあります。通常、ほとんどのJavaプログラマーは、自分で明示的に同期できるため、VectorではなくArrayListを使用します。

6.ArrayListとLinkedListのパフォーマンス

時間計算量の比較は次のとおりです。
arraylist-vs-linkedlist-complexity

*表のadd（）はadd（E e）を参照し、remove（）はremove（int index）を参照します

  • ArrayListには、追加/削除の任意のインデックスに対してO（n）の時間計算量がありますが、リストの最後の操作に対してはO（1）です。
  • LinkedListは、追加/削除の任意のインデックスに対してO（n）の時間計算量を持ちますが、リストの終了/開始時の操作に対してはO（1）です。

次のコードを使用して、パフォーマンスをテストします。

ArrayList arrayList = new ArrayList() LinkedList linkedList = new LinkedList() // ArrayList add long startTime = System.nanoTime() for (int i = 0 i <100000 i++) { arrayList.add(i) } long endTime = System.nanoTime() long duration = endTime - startTime System.out.println('ArrayList add: ' + duration) // LinkedList add startTime = System.nanoTime() for (int i = 0 i < 100000 i++) { linkedList.add(i) } endTime = System.nanoTime() duration = endTime - startTime System.out.println('LinkedList add: ' + duration) // ArrayList get startTime = System.nanoTime() for (int i = 0 i < 10000 i++) { arrayList.get(i) } endTime = System.nanoTime() duration = endTime - startTime System.out.println('ArrayList get: ' + duration) // LinkedList get startTime = System.nanoTime() for (int i = 0 i <10000 i++) { linkedList.get(i) } endTime = System.nanoTime() duration = endTime - startTime System.out.println('LinkedList get: ' + duration) // ArrayList remove startTime = System.nanoTime() for (int i = 9999 i>=0 i--) { arrayList.remove(i) } endTime = System.nanoTime() duration = endTime - startTime System.out.println('ArrayList remove: ' + duration) // LinkedList remove startTime = System.nanoTime() for (int i = 9999 i >=0 i--) { linkedList.remove(i) } endTime = System.nanoTime() duration = endTime - startTime System.out.println('LinkedList remove: ' + duration)

そして、出力は次のとおりです。

ArrayList add: 13265642 LinkedList add: 9550057 ArrayList get: 1543352 LinkedList get: 85085551 ArrayList remove: 199961301 LinkedList remove: 85768810

arraylist-vs-linkedlist

それらのパフォーマンスの違いは明らかです。 LinkedListは、追加と削除では高速ですが、取得では低速です。複雑さの表とテスト結果に基づいて、ArrayListまたはLinkedListをいつ使用するかを判断できます。簡単に言うと、次の場合はLinkedListを優先する必要があります。

  • 要素へのランダムアクセスは多数ありません
  • 多数の追加/削除操作があります