java - ArrayListとLinkedListのパフォーマンスの違い

Question

はい、これは古いトピックですが、まだ混乱があります。

ジャワでは、人々はこう言います：

1. ArrayListは、その要素にランダムにアクセスする場合、LinkedListよりも高速です。ランダムアクセスとは「n番目の要素を教えて」という意味だと思います。ArrayListの方が速いのはなぜですか？

2. LinkedListは、削除に関してArrayListよりも高速です。私はこれを理解しています。内部バックアップ配列を再割り当てする必要があるため、ArrayListの速度は遅くなります。コードの説明：

   List<String> list = new ArrayList<String>();
   list.add("a");
   list.add("b");
   list.add("c");
   list.remove("b");
   System.out.println(list.get(1)); //output "c"
   

3. LinkedListは、挿入に関してArrayListよりも高速です。ここで挿入とはどういう意味ですか？一部の要素を元に戻してから要素を中央の空の場所に配置することを意味する場合、ArrayListはLinkedListよりも低速である必要があります。挿入がadd（Object）操作のみを意味する場合、これはどのように遅くなる可能性がありますか？

Answer 1

ArrayListは、その要素にランダムにアクセスする場合、LinkedListよりも高速です。ランダムアクセスとは「n番目の要素を教えて」という意味だと思います。ArrayListの方が速いのはなぜですか？

ArrayListリスト内のすべての要素への直接参照があるため、一定時間でn番目の要素を取得できます。LinkedListn番目の要素に到達するには、リストを最初からトラバースする必要があります。

LinkedListは、削除に関してArrayListよりも高速です。私はこれを理解しています。内部バックアップ配列を再割り当てする必要があるため、ArrayListの速度は遅くなります。

ArrayList空きになったスロットを削除するためにアレイの一部をコピーする必要があるため、速度は遅くなります。ListIterator.remove()APIを使用して削除を行う場合はLinkedList、いくつかの参照を操作するだけです。削除が値またはインデックスによって行われる場合、削除LinkedListする要素を見つけるために、最初にリスト全体をスキャンする必要がある可能性があります。

一部の要素を元に戻し、要素を中央の空の場所に配置することを意味する場合、ArrayListの速度は遅くなります。

はい、これが意味します。アレイの中央にあるスロットを解放する必要があるため、ArrayList実際には低速です。LinkedListこれには、いくつかの参照を移動し、最悪の場合は配列全体を再割り当てすることが含まれます。LinkedListいくつかの参照を操作する必要があります。

Answer 2

今のところこの答えは無視してください。他の答え、特にaixの答えは、ほとんど正しいです。長期的には、彼らは賭ける方法です。また、十分なデータがある場合（1台のマシンの1つのベンチマークでは、約100万エントリのようです）、ArrayListとLinkedListは現在広告として機能します。ただし、21世紀初頭に当てはまるいくつかの細かい点があります。

私のテストによると、現代のコンピューターテクノロジーは、アレイに大きな優位性を与えているようです。配列の要素は、非常に速い速度でシフトおよびコピーできます。その結果、配列とArrayListは、ほとんどの実際的な状況で、挿入と削除でLinkedListよりもパフォーマンスが高くなります。言い換えれば、ArrayListは独自のゲームでLinkedListを打ち負かします。

ArrayListの欠点は、削除後にメモリスペースにハングアップする傾向があることです。ここで、LinkedListは、エントリを放棄するときにスペースを放棄します。

配列とArrayListの大きな欠点は、空きメモリを断片化し、ガベージコレクターを過剰に処理することです。ArrayListが展開されると、新しい、より大きな配列が作成され、古い配列が新しい配列にコピーされ、古い配列が解放されます。メモリは、次の割り当てに十分な大きさではない、空きメモリの大きな連続したチャンクでいっぱいになります。最終的には、その割り当てに適したスペースがなくなります。メモリの90％は空いていますが、その仕事をするのに十分な大きさの個々のピースはありません。GCは必死になって物事を動かしますが、スペースの再配置に時間がかかりすぎると、OutOfMemoryExceptionがスローされます。それが諦めない場合でも、プログラムの速度が低下する可能性があります。

最悪の場合、この問題は予測が難しい場合があります。プログラムは1回正常に実行されます。次に、使用可能なメモリが少し少なくなり、警告なしで、速度が低下または停止します。

LinkedListは小さくて可憐なメモリを使用し、GCはそれを気に入っています。使用可能なメモリの99％を使用している場合でも、正常に動作します。

したがって、一般に、ほとんどのコンテンツが削除される可能性が低い小さなデータセットの場合、または作成と拡張を厳密に制御できる場合は、ArrayListを使用します。（たとえば、メモリの90％を使用する1つのArrayListを作成し、プログラムの期間中はそれを埋めずに使用することは問題ありません。メモリの10％を使用するArrayListインスタンスを継続的に作成して解放すると、強制終了します。）それ以外の場合は、LinkedListを使用します。 （またはランダムアクセスが必要な場合は、ある種のマップ）。非常に大きなコレクション（たとえば100,000を超える要素）があり、GCの心配がなく、多くの挿入と削除を計画し、ランダムアクセスがない場合は、いくつかのベンチマークを実行して、何が最も速いかを確認します。

Answer 3

このArrayListクラスは、配列のラッパークラスです。内部配列が含まれています。

public ArrayList<T> {
    private Object[] array;
    private int size;
}

ALinkedListは、データを管理するための内部ノードを持つ、リンクリストのラッパークラスです。

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

現在のコードは、実際の実装ではなく、クラスがどのようになるかを示すために使用されていることに注意してください。実装がどのようになるかを知っているので、さらに分析を行うことができます。

ArrayListは、その要素にランダムにアクセスする場合、LinkedListよりも高速です。ランダムアクセスとは「n番目の要素を教えて」という意味だと思います。ArrayListの方が速いのはなぜですか？

ArrayListのアクセス時間：O（1）。LinkedListのアクセス時間：O（n）。

配列では、を使用して任意の要素にアクセスできますが、リンクリストでは、必要な要素を取得するまでarray[index]、すべてのリストをナビゲートする必要があります。first

LinkedListは、削除に関してArrayListよりも高速です。私はこれを理解しています。内部バックアップ配列を再割り当てする必要があるため、ArrayListの速度は遅くなります。

ArrayListの削除時間：アクセス時間+ O（n）。LinkedListの削除時間：アクセス時間+ O（1）。

ArrayListは、インデックスを削除するために、すべての要素をアイテムの先頭array[index]から先頭に移動する必要があります。array[index-1]LinkedListは、そのアイテムまでナビゲートしてから、リストからノードを切り離してそのノードを消去する必要があります。

LinkedListは、削除に関してArrayListよりも高速です。私はこれを理解しています。内部バックアップ配列を再割り当てする必要があるため、ArrayListの速度は遅くなります。

ArrayListの挿入時間：O（n）。LinkedListの挿入時間：O（1）。

ArrayListがO（n）を取ることができるのはなぜですか？新しい要素を挿入して配列がいっぱいになると、より多くのサイズの新しい配列を作成する必要があるためです（2*サイズまたは3*サイズ/2のような式で新しいサイズを計算できます）。LinkedListは、最後のノードの隣に新しいノードを追加するだけです。

この分析は、Javaだけでなく、C、C ++、C＃などの別のプログラミング言語でも行われます。

詳細はこちら：

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

Answer 4

remove（）とinsert（）はどちらも、ArrayListsとLinkedListsの両方で実行時効率がO（n）です。ただし、線形処理時間の背後にある理由は、2つの非常に異なる理由から来ています。

ArrayListでは、O（1）の要素にアクセスしますが、実際に何かを削除または挿入すると、次のすべての要素を変更する必要があるため、O（n）になります。

LinkedListでは、目的のインデックスに到達するまで最初から開始する必要があるため、実際に目的の要素に到達するにはO（n）が必要です。remove（）の1つの参照とinsert（）の2つの参照を変更するだけでよいため、そこに到達すると、削除または挿入は一定になります。

挿入と削除のどちらが速いかは、それがどこで発生するかによって異なります。最初に近づくと、比較的少数の要素を通過する必要があるため、LinkedListの速度が速くなります。終わりに近づくと、一定時間でそこに到達し、それに続くいくつかの残りの要素を変更するだけでよいため、ArrayListはより高速になります。

ボーナス：ArrayListに対してこれら2つのメソッドをO（1）にする方法はありませんが、実際にはLinkedListsでこれを行う方法があります。リスト全体を調べて、途中で要素を削除および挿入するとします。通常、LinkedListを使用して各要素の最初から開始します。また、イテレータを使用して作業中の現在の要素を「保存」することもできます。Iteratorの助けを借りて、LinkedListで作業するときにremove（）とinsert（）のO（1）効率を得ることができます。LinkedListがArrayListよりも常に優れていることを私が知っている唯一のパフォーマンス上の利点になります。

Answer 5

配列リスト

• 頻繁な操作が検索操作である場合は、ArrayListが最適です。
• 内部的にいくつかのシフト操作が実行されるため、操作が途中で挿入と削除である場合、ArrayListは最悪の選択です。
• ArrayListでは、要素は連続したメモリ位置に格納されるため、取得操作が簡単になります。

LinkedList：-

• LinkedListは、頻繁な操作が途中での挿入と削除である場合に最適です。
• LinkedListは最悪の選択であり、頻繁な操作は検索操作です。
• LinkedListでは、要素は連続したメモリ位置に格納されないため、取得操作は複雑になります。

今あなたの質問に来ています：-

1）ArrayListはインデックスに従ってデータを保存し、ArrayListにランダム検索の機能を提供するマーカーインターフェイスであるRandomAccessインターフェイスを実装しますが、LinkedListはRandomAccessインターフェイスを実装しないため、ArrayListはLinkedListよりも高速です。

2）LinkedListの基礎となるデータ構造は二重リンクリストであるため、ArrayList（これは内部的にいくつかのシフト操作が実行されるため、操作が途中での挿入と削除である場合はお勧めしません）。
ソース

Answer 6

1への回答：ArrayListは内部で配列を使用します。ArrayListオブジェクトのメンバーへのアクセスは、インデックスがバッキング配列の境界内にあると仮定すると、提供されたインデックスで配列にアクセスするのと同じくらい簡単です。LinkedListは、n番目の要素に到達するために、そのメンバーを反復処理する必要があります。これは、LinkedListの場合はO（n）であるのに対し、ArrayListの場合はO（1）です。

Answer 7

LinkedListでは、要素にはその前後の要素への参照があります。ArrayListでは、データ構造は単なる配列です。

1. LinkedListは、N番目の要素を取得するためにN個の要素を反復処理する必要があります。ArrayListは、バッキング配列の要素Nのみを返す必要があります。

2. バッキング配列は、新しいサイズに再割り当てして配列をコピーするか、削除した要素を上に移動して空のスペースを埋める必要があります。LinkedListは、削除された後の要素の前の参照を削除される前の参照に設定し、削除された要素の前の要素の次の参照を削除された要素の後の要素に設定する必要があります。説明するのに時間がかかりますが、実行するのは速くなります。

3. ここでの削除と同じ理由。

Answer 8

彼女にパフォーマンスの違いについての情報を追加したいと思います。

ArrayList実装はObject[]ランダムアクセスと動的なサイズ変更をサポートしているため、LinkedList実装はヘッドとテールへの参照を使用してナビゲートすることをすでに知っています。ランダムアクセス機能はありませんが、動的なサイズ変更もサポートしています。

まず、ArrayListを使用すると、すぐにインデックスにアクセスできますが、LinkedListを使用すると、オブジェクトチェーンを反復処理できます。

第二に、ArrayListへの挿入は、境界に達すると大きくなる必要があるため、一般的に遅くなります。新しい大きな配列を作成し、元の配列からデータをコピーする必要があります。

しかし、興味深いのは、すべての挿入に適合するのに十分な大きさのArrayListを作成すると、明らかに配列のコピー操作が含まれないことです。LinkedListはそのポインターを処理する必要があるため、LinkedListを追加するよりもさらに高速になりますが、巨大なArrayListは指定されたインデックスに値を設定するだけです。

ArrayListとLinkedListのその他の違いを確認してください。

Answer 9

ArrayList：ArrayListは配列のような構造を持ち、すべての要素への直接参照を持っています。したがって、ArrayListではランダムアクセスが高速です。

LinkedList：n番目の要素を取得するためのLinkedListでは、リスト全体をトラバースする必要があり、ArrayListと比較して時間がかかります。すべての要素には前の要素とネスト要素へのリンクがあるため、削除は高速です。

Answer 10

ArrayList： ArrayListクラスはAbstractListを拡張し、ListインターフェイスとRandomAccess（マーカーインターフェイス）を実装します。ArrayListは、必要に応じて拡張できる動的配列をサポートします。これにより、要素に対する最初の反復が行われます。

LinkedList： LinkedListは、要素が相互に二重にリンクされていることを除いて、ArrayListのようにインデックス位置順に並べられています。このリンケージは、最初または最後から追加および削除するための新しいメソッド（リストインターフェイスから取得するものを超えて）を提供します。これにより、スタックまたはキューを実装するための簡単な選択が可能になります。LinkedListはArrayListよりも反復が遅い場合がありますが、迅速な挿入と削除が必要な場合に適しています。Java 5以降、LinkedListクラスは、java.util.Queueインターフェースを実装するように拡張されました。そのため、一般的なキューメソッドであるpeek（）、poll（）、offer（）をサポートするようになりました。

Answer 11

それらは同一であるように見えますが（同じ実装されたインターフェイスリスト-スレッドセーフではありません）、追加/削除、検索時間、およびメモリの消費（LinkedListはより多くを消費します）のパフォーマンスの点で異なる結果をもたらします。

LinkedListsは、パフォーマンスO（1）で高度な挿入/削除を使用する場合に使用できます。パフォーマンスO（1）で直接アクセス操作を使用する場合は、ArrayListsを使用できます。

このコードはこれらのコメントを明らかにする可能性があり、パフォーマンスの結果を理解することを試みることができます。（ボイラープレートコードでごめんなさい）

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}