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?

Perspex

Note that with LinkedList you need to create a Node object for every insertion. With ArrayList you have to grow the array. – Attestation

You understood everything right. Stack Overflow is full of s... – Idou

For future measurements, you should probably use System.nanoTime() instead of System.currentTimeMillis() as the precision is much much less for the latter and you're not actually measuring the current time here but a difference between 2 points. – Dukedom

If you populate ArrayList first and LinkedList later, then the results are very different. ArrayList still wins mostly, but it is a lot closer. – Selby

Oh, and please post complete executable samples, whenever possible, it makes investigation easier. – Jordanjordana

Why do you think LinkedList should be faster than ArrayList in this case? I can see nothing in the referenced question tht supports this assumption. LinkedList and ArrayList have the same asymptotic amortized behavior for appending. However, the constant factor is significant smaller for the latter. – Electromyography

#10656971 – Revisionism

Ok, the answer of the linked question writes ListIterator.add(E element) is O(n-index) in ArrayList. I do not understand what is index when looping over the list with an iterator. Based on its best case though, the performace should be at least equal, what can be proved by my example. – Perspex

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

Jordanjordana

Can you explain what do you mean by: "Now, it will always point to the middle of list"? I do not think your code does that. – Perspex

@Perspex - every second add I go back one element. In effect I do add n times, but move forward only n/2 times. – Jordanjordana

That is true but not the same with your claim "Now, it will always point to the middle of list". – Perspex

@arjacsoh, if you want me to be extremely precise: after each iteration of the loop it will point to element with index (list.size()+1)/2. – Jordanjordana

Answer 2

Insertion and deletion at the beginning or middle (of the array or list) is where a list beats out an array.

Lifework

Answer 3

As I understand it, the benefit of a LinkedList is on insertion of a value into a given index (say, the middle, or the start). ArrayList won't lose out on sequential insertion, as it doesn't have to shift elements over.

Once you have populated your lists as above, see what you get for in-position insertion to different places. I've modified your example to show an example of where LinkedList wins significantly (on my setup at least):

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

Compeer