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

Answer 2

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

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