LinkedList-とはどう違いArrayListますか? ?を使用するのが望ましいのはLinkedListいつですか?
すべての Java 開発者は、面接で少なくとも 1 回はこの質問を聞いたことがあると思います。
- リストの途中にアイテムを挿入できるようにしたい場合は、リンクされたリストが適しています。
この質問に対する一般的な答えです。誰もがそれを知っています。List 実装の違いについて質問するたびに、次のような回答が得られます。
LinkedList はいつ使用する必要がありますか? エレメント間または開始時に効率的な除去が必要になるのはいつですか?
挿入コストについて言及するのを忘れていました。LinkedList では、正しい位置を取得すると、挿入コストが発生しますが
O(1)、ArrayList ではO(n)、挿入ポイントを超えるすべての要素を移動する必要があります。
リストの途中 (優先度キューなど) に項目を挿入できるようにする場合は、配列よりも連結リストの方が適しています。
ArrayList は、空きになったスロットを削除するために配列の一部をコピーする必要があるため、遅くなります。LinkedList は、いくつかの参照を操作するだけです。
もっと...
しかし、自分でそれを再現しようとしたことがありますか? 昨日試してみたところ、次の結果が得られました。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String... args) {
final int MAX_VAL = 10000;
List<Integer> linkedList = new LinkedList<Integer>();
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(i);
arrayList.add(i);
}
long time = System.nanoTime();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(MAX_VAL/2, i);
}
System.out.println("LL time: " + (System.nanoTime() - time));
time = System.nanoTime();
for(int i = 0; i < MAX_VAL; i++) {
arrayList.add(MAX_VAL/2, i);
}
System.out.println("AL time: " + (System.nanoTime() - time));
}
}
出力：
LLタイム：114098106
アル時間: 24121889
それで、それは何ですか？なぜ LinkedList はそれほどひどいのでしょうか? 追加する代わりに削除操作を試す必要がありますか? では、試してみましょう:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String... args) {
final int MAX_VAL = 10000;
List<Integer> linkedList = new LinkedList<Integer>();
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(i);
arrayList.add(i);
}
long time = System.nanoTime();
for(int i = 0; i < MAX_VAL/2; i++) {
linkedList.remove(MAX_VAL/2);
}
System.out.println("LL time: " + (System.nanoTime() - time));
time = System.nanoTime();
for(int i = 0; i < MAX_VAL/2; i++) {
arrayList.remove(MAX_VAL/2);
}
System.out.println("AL time: " + (System.nanoTime() - time));
}
}
出力：
LLタイム：27581163
アル時間: 3103051
おお、ArrayList は LinkedList よりもまだ高速です。理由は何ですか？この神話は破られましたか？それとも私が間違っているのでしょうか？
