Is LinkedList really faster than ArrayList in the case of insertion in the middle of list?

BUSTED

Not really. Here

for(int i = 0; i < MAX_VAL; i++) {
    linkedList.add(MAX_VAL/2, i);
}

you don't just insert the item; you pay the cost of iterating from the beginning to i every time. Naturally, that's O(i).

On the other hand, the list must be quite large before you'll actually witness the performance benefit of mid-list insertion. System.arraycopy is a blazing-fast operation and, on the other end, each insertion into a LinkedList requires the allocation of a node instance.

In summary, ArrayList is a better choice for 99% or more of real-world cases, and leveraging the narrow advantage of a LinkedList requires great care.

General notes on microbenchmarking the JVM

I should also warn you that your benchmarking code is badly deficient. There is quite a sizable checklist of things to watch out for when microbencharking on the JVM, for example:

  • always warm up the code to let the JIT compiler get to it;
  • be very careful about interpreting nanoTime results due to accuracy/precision issues. Make the reading grow at least into milliseconds (millions of nanoseconds) to ensure reliability;
  • control the spurious side-effects of the Garbage Collector;
  • etc.

Therefore the advice is to use a ready-made microbenchmarking framework such as OpenJDK's jmh.


To demonstrate the (in)effectivenes of the add() operation, it is better to use the ListIterator object instead of list object. If you use the add() method directly on the linked list, it starts with the list head and has to iterate to the position where you want to insert the item. This part takes O(n). If you use the ListIterator, it will hold the position where we are adding the elements and the algorithm does not have to iterate into the middle of the list each time. 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List<Integer> linkedList = new LinkedList<Integer>();
        List<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();


        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        System.out.println("LL time:\t" + (System.nanoTime() - time));

        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        System.out.println("AL time:\t" + (System.nanoTime() - time));


        //Reset the lists
        linkedList = new LinkedList<Integer>();
        arrayList = new ArrayList<Integer>();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }

        time = System.nanoTime();
        ListIterator<Integer> li = linkedList.listIterator(MAX_VAL/2);
        for(int i = 0; i < MAX_VAL; i++) {
            li.add(i);
        }
        System.out.println("LL iterator:\t" + (System.nanoTime() - time));

        time = System.nanoTime();
        ListIterator<Integer> ali = arrayList.listIterator(MAX_VAL/2);
        for(int i = 0; i < MAX_VAL; i++) {
            ali.add(i);
        }
        System.out.println("AL iterator:\t" + (System.nanoTime() - time));
    }
}

My results shows that using using ListIterator on LinkedList gives the best performance for inserting the elements in the "middle":

LL time:     237819474
AL time:      31410507
LL iterator:   5423172
AL iterator:  23975798

Your test has bias - it doesn't measure the usual performance difference.

General observations about LinkedList structure (compared to ArrayList, for a large list):

  1. adding/removing a node at the head or tail is very fast
  2. getting an element from the middle is very slow
  3. getting an element becomes faster (linearly) as you approach either end of the list
  4. getting an element from the head or tail approaches the speed of an ArrayList
  5. adding/removing an element somewhere in the middle is two operations: get plus node insertion
  6. if you use a ListIterator, you can add/remove a node somewhere in the middle and avoid the get - a very fast operation

Your test intends to test (5).

But it always carries out the worst case - adding/removing an element exactly in the middle.

Your micro-benchmark gives systematic error. You need to uniformly or randomly distribute the add/remove location. Or carry out macro-benchmarking with real-life complex & challenging apps.

An interesting read on the challenge of creating an accurate micro-benchmark: Java theory and practice: Anatomy of a flawed microbenchmark

Tags:

Java

Collections

Recent Posts