java - 初めてオブジェクトを ArrayList または LinkedList に追加するのに時間がかかるのはなぜですか?

Question

初めてオブジェクトを ArrayList または LinkedList に追加するのに時間がかかるのはなぜですか?

ArrayList と LinkedList のパフォーマンスをテストしています。結果は私が期待したものです。通常、ArrayList はランダム アクセスに適しています。また、LinkedList へのすべての挿入には同様の時間が必要です。しかし、オブジェクトを ArrayList または LinkedList に初めて追加するときは、他よりもはるかに時間がかかることがわかりました。

Mac と Linux でコードをテストしましたが、状況は似ています。コードと完全な結果は、ここからダウンロードできます。

java PlayArrayList       
0 to 10, elapsedTime: 716362
10 to 20, elapsedTime: 19765
20 to 30, elapsedTime: 10895

$ java PlayLinkedList 
0 to 10, elapsedTime: 704209
10 to 20, elapsedTime: 5867
20 to 30, elapsedTime: 5378

PS: ナノ秒単位で測定されます。

/* Untilty Class for measuring elapsed time */
public class BenmarkTimer {
    private long startTime;
    private long endTime;

    /* Getter */
    public long getStartTime(){
        return startTime;
    }

    public long getEndTime(){
        return endTime;
    }

    /* Setter */
    private void setStartTime(long t){
        startTime = t;
    }

    private void setEndTime(long t){
        endTime = t;
    }

    /* Method */
    public void start(){
        setStartTime(System.nanoTime());
    } 

    public long end(){
        setEndTime(System.nanoTime());
        return getDuration();
    }

    public void cancel(){
        setStartTime(0);
        setEndTime(0);
    }

    public long getDuration(){
        return getEndTime() - getStartTime();
    }

    /* Unit testing */
    public static void main (String [] args){
        BenmarkTimer timer = new BenmarkTimer();
        timer.start();
        System.out.println("Hello, World for timer");
        timer.end();
        long t = timer.getDuration();
        System.out.println("Start time "+ timer.getStartTime());
        System.out.println("End time "+ timer.getEndTime());
        System.out.println("Elaped time "+ t);
    }
}


import java.util.*;

public class PlayArrayList{
    private int itemCount;
    private BenmarkTimer timer;
    private List<Integer> list; 

    public PlayArrayList(){
        itemCount = 0;
        timer = new BenmarkTimer();
        list = getList();
    }

    public long addTenIntegers(){
        timer.start();
        for (int i=itemCount; i<(itemCount + 10); i++ ) {
            list.add(i);
        }
        long elapsedTime = timer.end();
        itemCount += 10;

        return elapsedTime;
    }

    public long randomRemove(){
        Random r = new Random();
        int s = list.size();
        int i = r.nextInt(s);

        timer.start();
        list.remove(i);
        return timer.end();
    }

    public String toString(){
        return list.toString();
    }

    /* Factory method */
    protected List<Integer> getList(){
        return new ArrayList<Integer>();
    }

    public static void main (String [] args){
        PlayArrayList playAList = new PlayArrayList();

        /* Add 99 integers */
        long elapsedTime;
        for (int i=0; i<10; i++){
            elapsedTime = playAList.addTenIntegers();
            System.out.print(i*10 + " to " + (i*10+10));
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

        System.out.println("Array content");
        System.out.println(playAList.toString());


        /* Remove 99 integer */
        for (int i=0; i<99; i++){
            elapsedTime = playAList.randomRemove();
            System.out.print("Remove a integer");
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

    }
} 

import java.util.*;

public class PlayLinkedList extends PlayArrayList{
    /* Factory method */
    @Override
    protected List<Integer> getList(){
        return new LinkedList<Integer>();
    }

    public static void main (String [] args){
        PlayLinkedList playAList = new PlayLinkedList();

        /* Add 99 integers */
        long elapsedTime;
        for (int i=0; i<10; i++){
            elapsedTime = playAList.addTenIntegers();
            System.out.print(i*10 + " to " + (i*10+10));
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

        System.out.println("Array content");
        System.out.println(playAList.toString());


        /* Remove 99 integer */
        for (int i=0; i<99; i++){
            elapsedTime = playAList.randomRemove();
            System.out.print("Remove a integer");
            System.out.println(", elapsedTime: "+ elapsedTime);
        }

    }
}