Java

Javaを振り返って-ArrayList対LinkedList対Vector



Looking Back Java Arraylist Vs



リストの概要

リストは、その名前が示すように、順序付けられた要素のセットです。リストについて議論するとき、それをセットと比較するのは簡単です。セットは、ユニークで無秩序な要素のグループです。

次の図は、コレクションクラスの階層図です。
画像



ArrayList vs. LinkedList vs. Vector

上の図からわかるように、これらはすべてListインターフェイスを実装しています。それらの使用法は似ていますが、主な違いは、操作ごとに操作速度が異なることです。

ArrayListは、サイズを変更できる配列です。要素がArrayListに追加されると、そのサイズは動的に増加します。要素には、get（）メソッドとset（）メソッドを介して直接アクセスできます。 ArrayListは実際には配列（順序の線形リスト）です 、。 LinkedListは二重にリンクされたリストです 。そのadd（）メソッドとremove（）メソッドはArrayListよりも高速ですが、get（）メソッドとset（）メソッドはArrayListよりも低速です。 VectorはArrayListに似ていますが、Vectorは同期しています。スレッドセーフな環境にいる場合は、ArrayListを使用することをお勧めします。要素を追加するときに、初期容量を超えると、VectorとArrayListはより多くのスペースを必要とします。Vectorは配列のサイズを2倍にする必要があり、ArrayListは50％増加する必要があります。



LinkedListは、キューインターフェイスも実装します 、したがって、ArrayListやVector、およびoffer（）、peek（）、poll（）などのいくつかのメソッドよりも多くのキュー機能があります。

ArrayListの例

public static void main(String[] args) { ArrayList list = new ArrayList() list.add(1) list.add(2) list.add(2) list.add(3) list.add(4) Iterator iter = list.iterator() while(iter.hasNext()) { System.out.println(iter.next()) } }

LinkedListの例

public static void main(String[] args) { LinkedList list = new LinkedList() list.add(3) list.add(2) list.add(4) list.add(6) list.add(2) list.addFirst(1) list.addLast(7) Iterator iter = list.iterator() while(iter.hasNext()) { System.out.println(iter.next()) } }

上記から、それらの使用法は同じであり、主な違いはそれらの内部実装と操作の複雑さにあることがわかります。

ベクター

VectorはArrayListとほぼ同じですが、主な違いはVectorが同期されていることです。このため、VectorはArrayListよりも高価です。通常、ほとんどのプログラマーはArrayListを使用し、同期する独自のコードを作成できます。



ArrayListとLinkedListのパフォーマンスの比較

時間計算量は次のとおりです。
画像

表のadd（）はadd（E e）を参照し（つまり、リストの最後に要素を追加します）、remove（）メソッドはremove（int index）を参照します。

インデックスに対するArrayListの挿入/削除操作の時間計算量はO（n）ですが、リストの最後の操作時間はO（1）です。これは、最後に操作するときに前の要素が配列で使用されないためです。場所を移動します。

LinkedListの任意のインデックスに対する挿入/削除操作の時間計算量はO（n）ですが、リストの先頭または末尾の操作時間はO（1）です。これは、先頭または末尾の操作でヘッドポインターとを変更するだけでよいためです。途中の要素のポインタ操作がなくても、テールポインタで十分です。

配列

  • 挿入/削除位置を見つける時間の複雑さはO（1）です。
  • 挿入/削除操作の時間計算量はO（n）です。

リンクリスト：

  • 挿入/削除位置を見つける時間の複雑さはO（n）です。
  • 挿入/削除操作の時間計算量はO（1）です。

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

public static void main(String[] args) { 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: 7064206 LinkedList add: 14325298 ArrayList get: 144756 LinkedList get: 120728232 ArrayList remove: 502540684 LinkedList remove: 119826646

画像

それらのパフォーマンスの違いは重要です。 LinkedListは、ArrayListよりもadd（）とremove（）の方が高速ですが、get（）は低速です。複雑さとテスト結果に応じて、ArrayListをいつ使用するかとLinkedListをいつ使用するかを簡単に知ることができます。 つまり、LinkedListは次の状況で使用する必要があります。

  • 多くのランダムアクセスなし

  • 追加/削除操作が多い場合

安全な使用

これらのサブクラスはスレッドセーフではないため、複数のスレッドで安全に使用する場合は、それら自体でアクセス同期を実装する必要があります。 1つの解決策は、リストの作成時に同期リストを作成することです。

List list = Collections.synchronizedList(new LinkedList())

参考記事