Java の ArrayList と LinkedList の違い

ArrayListとLinkedListはどちらもListインターフェイスを実装していますが、違いは何ですか?ArrayList と LinkedList の主な違いは、拡張可能な配列を使用して実装される ArrayList にあります。ArrayList に追加される項目が増えると、そのサイズは動的に増加します。ArrayList は基本的に配列であるため、その要素には get() メソッドと set() メソッドを使用して直接アクセスできます.

LinkedList はリンクリストとして実装されており、これらの追加と削除のパフォーマンスは ArrayList のパフォーマンスよりも優れていますが、get() メソッドと set() メソッドには適していません.

この記事では、LinkedList と ArrayList の違いをいくつか見て、ArrayList の代わりに LinkedList を使用するタイミングと場所を理解しようとします。

ArrayList と LinkedList

LinkedList と ArrayList のすべての違いには、配列と LinkedList (リンクリスト) の違いであるソースがあります>><<。ArrayListでの検索は要素のインデックスに基づいているため、非常に高速です。get(インデックス) は O(1) の複雑さを持ちますが、すべての要素をオフセットする必要があるため、除去にはコストがかかります。LinkedListの場合、項目に直接アクセスできず、項目を取得するためにリスト全体を調べる必要があり、その複雑さはO(n)に等しくなります.

2) LinkedListでは、項目のサイズを変更してLinkedListに追加するときにリスクがなく、その複雑さがO(1)に等しいため、ArrayListと比較して挿入が簡単です。一方、ArrayList は、最悪の場合、複雑さ O(n) のすべての要素をシフトします.

3) 削除は挿入に似ており、ArrayList よりも LikedList の方が優れています.

4) LinkedList は ArrayList よりも多くのメモリを持っています。しかし、LinkedListの場合、各ノードは次と前のノードの要素とアドレスにリンクされています.

JavaでLinkedListとArraListを使用する場合

明らかに、LinkedListはArrayListのように人気はありませんが、それでもいくつかのケースでは良い選択です:

1) アプリケーションにランダムアクセスは必要ありません。この操作はリスト全体を調べることで構成されるため、この場合

2) アプリケーションでは、回復よりも挿入と削除が多くなります。これらの操作はどちらも、非同期アクセスが必要な状況で LikedList.

Use ArrayList in Java の方が高速です。ArrayListは高速で使いやすいです.

ArrayListの例

ArrayList<文字列>al = new ArrayListです<文字列>();
al.add("a");
al.add("c");
al.add("e");
al.add("z");
al.add("t");
al.add("m");

for(文字列 s: e){
 System.out.println(e);
}

LinkedListの例

LinkedList<整数>llist = new LinkedList<整数>();
llist.add(8);
llist.add(9);
llist.add(5);
llist.add(2);
llist.add(6);
 
イテレータ<整数>it = llist.iterator();
while(it.hasNext()){
 System.out.println(it.next());
}

ArrayListとLinkedListのパフォーマンス

両方のリストの時間計算量:

O(1)

Operation	ArrayList	LinkedList
get()	O(n)
add()	O(1)	O(1)
remove()	O(n)	O(1)

- ArrayList は、add() 操作と remove() 操作の両方で O(n) の時間互換性がありますが、リストの末尾の操作や get() メソッドで項目を取得する操作に対しては O(1) です。

- LinkedListは、get() 操作では O(n) ですが、削除操作では O(n) の複雑さを持ちます remove().

このコードは、いくつかの操作の実行にかかる時間に基づいてパフォーマンスをテストします:

import java.util.ArrayList;
import java.util.LinkedList;

public class ArrayListVsLinkedList {

 public static void main(String[] args) {
 ArrayList<整数>alist = new ArrayList<整数>();
 LinkedList<整数>llist = new LinkedList<整数>();
 
 /******************************/
 /* add() メソッド */
 /******************************/
 
 // ArrayList
 long tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 999999; i++) {
 alist.add(i);
 }
 long tpsfin = System.currentTimeMillis();
 long duration = tpsfin - tpsdebut;
 System.out.println("ArrayList追加:" + duration);
 
 // LinkedList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 999999; i++) {
 llist.add(i);
 }
 tpsfin = System.currentTimeMillis();
 duration = tpsfin - tpsdebut;
 System.out.println("LinkedList追加:" + duration);
 
 /******************************/
 /* get() メソッド */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 99999; i++) {
 alist.get(i);
 }
 tpsfin = System.currentTimeMillis();
 duration = tpsfin - tpsdebut;
 System.out.println("ArrayList get: " + duration);
 
 // LinkedList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 99999; i++) {
 llist.get(i);
 }
 tpsfin = System.currentTimeMillis();
 duration = tpsfin - tpsdebut;
 System.out.println("LinkedList get: " + duration);
 
 /******************************/
 /* remove() メソッド */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 9999; i >=0; i--) {
 alist.remove(i);
 }
 tpsfin = System.currentTimeMillis();
 duration = tpsfin - tpsdebut;
 System.out.println("ArrayList remove: " + duration);
 
 // LinkedList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 9999; i >=0; i--) {
 llist.remove(i);
 }
 tpsfin = System.currentTimeMillis();
 duration = tpsfin - tpsdebut;
 System.out.println("LinkedList remove: " + duration);
 }
}

結果:

ArrayList 追加: 398
LinkedList 追加: 987
ArrayList 取得: 180
LinkedList 取得: 43276
ArrayList 削除: 8721
LinkedList 削除: 233