Measuring time does not confirm LinkedList advantage

Question

I am reading the differrences between ArrayList and LinkedList pointed out in When to use LinkedList over ArrayList?. I developed a small example applcation to test a major advantage of LinkedList but the results I obtain do not confirm, that LinkedList outweighs ArrayList in the performance of the operation:

ListIterator.add(E element)

Here is my code:

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());
    }

The measurement gives:

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

I notice that the increase of elements impairs significantly the performance of LinkedList while ArrayList presents a considerably better behaviour. Have I understood something false?

Answer 1

ArrayList is faster when adding element at the end of container or very close, since it doesn't need to shift many elements then. It is slow, when adding in the middle or at the beginning. I changed your loop into the following:

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

Now, it will always point to the middle of list. With this benchmark, LinkedList is much faster. Results for 200000:

LinkedList needed: 47
ArrayList needed: 4702