6

ArrayList よりも LinkedList を使用する場合で指摘されているものArrayListとの違いを読んでいますか? . 主な利点をテストするための小さなサンプルアプリケーションを開発しましたが、得られた結果は確認できません。これは、操作のパフォーマンスを上回ります。LinkedListLinkedListLinkedListArrayList

ListIterator.add(E element)

これが私のコードです：

public static void main(String[] args) {

        int number = 100000;

        long startTime1 = System.currentTimeMillis();
        fillLinkedList(number);
        long stopTime1 = System.currentTimeMillis();

        long startTime2 = System.currentTimeMillis();
        fillArrayList(number);
        long stopTime2 = System.currentTimeMillis();

        System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
        System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));

    }


    public static void fillLinkedList(int number){

        LinkedList<Integer> list = new LinkedList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        int i = 0;
        while(i++<number){
            it.add(i);
        }
    //  System.out.println("LinkedList size: "+list.size());

    }


    public static void fillArrayList(int number){
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        int i = 0;
        while(i++<number){
            it.add(i);
        }
    //  System.out.println("ArrayList size: "+list.size());
    }

測定結果は次のとおりです。

number            10,000     100,000     500,000      1,000,000     5,000,000

ArrayList            7         17         60             77           170

LinkedList           7         21         89             838          4127

要素の増加は のパフォーマンスを大幅に低下させますが、かなり優れた動作LinkedListを示します。ArrayList私は何か間違っていることを理解しましたか？

4

3 に答える 3

6

ArrayListコンテナの最後または非常に近くに要素を追加すると、多くの要素をシフトする必要がないため、高速になります。途中や最初に追加すると遅いです。ループを次のように変更しました。

    while(i++<number){
        it.add(i);
        if(i%2 == 0)
            it.previous();
    }

これで、itは常に の真ん中を指しlistます。このベンチマークでLinkedListは、はるかに高速です。200000 の結果:

LinkedList needed: 47
ArrayList needed: 4702
于 2013-10-05T15:17:33.743 に答える
-1

私が理解しているように、LinkedList の利点は、特定のインデックス (たとえば、中央または開始) に値を挿入することです。ArrayList は、要素をシフトする必要がないため、順次挿入を失うことはありません。

上記のようにリストを作成したら、さまざまな場所へのインポジション挿入で何が得られるかを確認してください。あなたの例を修正して、LinkedListが大幅に勝利する例を示しました（少なくとも私のセットアップでは）：

public static void main(String[] args) {

    int number = 5000000;

    LinkedList<Integer> llist = new LinkedList<Integer>();
    ArrayList<Integer> alist = new ArrayList<Integer>();

    long startTime1 = System.nanoTime();
    fillLinkedList(number, llist);
    long stopTime1 = System.nanoTime();

    long startTime2 = System.nanoTime();
    fillArrayList(number, alist);
    long stopTime2 = System.nanoTime();

    System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
    System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));

    startTime1 = System.nanoTime();
    llist.add(1, 4);
    stopTime1 = System.nanoTime();

    startTime2 = System.nanoTime();
    alist.add(1, 4);
    stopTime2 = System.nanoTime();

    System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
    System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));

}

public static void fillLinkedList(int number, LinkedList<Integer> list){


    ListIterator<Integer> it = list.listIterator();
    int i = 0;
    while(i++<number){
        it.add(i);
    }
    //  System.out.println("LinkedList size: "+list.size());

}


public static void fillArrayList(int number, ArrayList<Integer> list){
    ListIterator<Integer> it = list.listIterator();
    int i = 0;
    while(i++<number){
        it.add(i);
    }
    //  System.out.println("ArrayList size: "+list.size());
}
于 2013-10-05T15:10:53.307 に答える