Difference between ArrayList and LinkedList in Java - the whys for performance

Question

I thought I understood the difference between ArrayList and LinkedList theoretically pretty well. However, its the first time, I put it to a little test, and the tests came out, well different to my expectations.

Expectations :

1. Arraylist will be slower than LinkedList when inserting at the beginning, since it has to "shift" the elements, for linkedlist, its just updating 2 references.

   Reality : came out to be same on most iterations. For a select few iterations, it was slower.

2. Arraylist will be slower than LinkedList when deleting at the beginning, since it has to "shift" the elements, for Linkedlist, its just nullifying one element.

   Reality : Performance was same when deleting from beg.

Test Case : 1,000,000 elements

public static void main(String[] args) { int n = 1000000; List arrayList = new ArrayList(n+10); long milis = System.currentTimeMillis(); for(int i= 0 ;i<n;i++){ arrayList.add(i); } System.out.println("insert arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); List linkedList = new LinkedList(); milis = System.currentTimeMillis(); for(int i= 0 ;i<n;i++){ linkedList.add(i); } System.out.println("insert linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); //System.out.println("Adding at end"); milis = System.currentTimeMillis(); arrayList.add(n-5,n+1); System.out.println("APPEND arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.add(n-5,n+1); System.out.println("APPEND linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); //add at front milis = System.currentTimeMillis(); arrayList.add(0,0); System.out.println("INSERT BEG arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.add(0,0); System.out.println("INSERT BEG linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); //add at middle milis = System.currentTimeMillis(); arrayList.add(n/2,n/2); System.out.println("INSERT MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.add(n/2,n/2); System.out.println("INSERT MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); //get from front, mid, end milis = System.currentTimeMillis(); arrayList.get(0); System.out.println("get front arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.get(0); System.out.println("get front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); arrayList.get(n/2); System.out.println("get MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.get(n/2); System.out.println("get MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); arrayList.get(n-4); System.out.println("get last arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.get(n-4); System.out.println("get last linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); //delete from front, mid, end. milis = System.currentTimeMillis(); arrayList.remove(0); System.out.println("del front arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.remove(0); System.out.println("del front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); arrayList.remove(n/2); System.out.println("del mid arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.remove(n/2); System.out.println("del mid linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); arrayList.remove(n-4); System.out.println("del end arraylist takes "+(System.currentTimeMillis()-milis)+" ms"); milis = System.currentTimeMillis(); linkedList.remove(n-4); System.out.println("del end linkedlist takes "+(System.currentTimeMillis()-milis)+" ms"); } 

Output Log

insert arraylist takes 141 ms insert linkedlist takes 312 ms APPEND arraylist takes 0 ms APPEND linkedlist takes 0 ms INSERT BEG arraylist takes 0 ms INSERT BEG linkedlist takes 0 ms INSERT MIDDLE arraylist takes 0 ms INSERT MIDDLE linkedlist takes 0 ms get front arraylist takes 0 ms get front linkedlist takes 0 ms get MIDDLE arraylist takes 0 ms get MIDDLE linkedlist takes 16 ms get last arraylist takes 0 ms get last linkedlist takes 0 ms del front arraylist takes 0 ms del front linkedlist takes 0 ms del mid arraylist takes 0 ms del mid linkedlist takes 15 ms del end arraylist takes 0 ms del end linkedlist takes 0 ms 

So what's the reason? JDK 1.6 used.

EDIT : After using System.nanotime(), it did give me answers as I expected. Agreed, its only a single trial, and should be averaged.

insert arraylist takes 137076082 ns insert linkdlist takes 318985917 ns APPEND arraylist takes 69751 ns APPEND linkdlist takes 98126 ns **INSERT BEG arraylist takes 2027764 ns INSERT BEG linkdlist takes 53522 ns** INSERT MIDDLE arraylist takes 1008253 ns INSERT MIDDLE linkdlist takes 10395846 ns get front arraylist takes 42364 ns get front linkdlist takes 77473 ns get MIDDLE arraylist takes 39499 ns get MIDDLE linkdlist takes 9645996 ns get last arraylist takes 46165 ns get last linkdlist takes 43446 ns **del front arraylist takes 1720329 ns del front linkdlist takes 108063 ns** del mid arraylist takes 1157398 ns del mid linkdlist takes 11845077 ns del end arraylist takes 54149 ns del end linkdlist takes 49744 ns 

Answer 1

The explanation for your first two (weird) test numbers is:

Inserting into ArrayList is generally slower because it has to grow once you hit its boundaries. It will have to create a new bigger array, and copy data from the original one.

But when you create an ArrayList that is already huge enough to fit all your inserts (which is your case since you're doing new ArrayList(n+10)) - it will obviously not involve any array copying operations. Adding to it will be even faster than with LinkedList because LinkedList will have to deal with its "links" (pointers), while huge ArrayList just sets value at given (last) index.

Also your tests are not good because each iteration involves autoboxing (conversion from int to Integer) - it will both take additional time to do that and will also screw up the results because of the Integers cache that will get filled on the first pass.

Answer 2

int n = 1000000; is too small. You get 0 ms doesn't really mean that it takes no time to complete the insertion or deletion. It means that the time elapsed is less than 1ms . Try rising the number of int n = 1000000; . You can see the difference then.

EDIT: I have misread your code. I thought that you are inserting n elements in the front of the array list. You should definitely insert multiple items instead of inserting one only.

ANOTHER EDIT: If you insert n elements, you would not need to raise the value of n. Conversely, you would probably want to decrease it because inserting in the front of ArrayList is a slow operation.

Answer 3

With an ArrayList, the insert at the middle operation is going to be two steps in terms of theoretical Big Oh:

• O(1) to find the position and insert the new value
• O(n) to shift the remaining values forward.

With a LinkedList, if the relevant Node is not known yet (looping from the head node), it is also two steps:

• O(n) to find the Node at the position
• O(1) to insert the new value

However, besides the expected algorithmic complexity, there are other points that can have an impact on the actual runtime:

• Specific language implementations might make parts of a specific process faster. In this case, Java's arraycopy(), which ArrayList uses, seams faster than a for-loop copying each value. This might not be true for all arrays (sizes, types) - again, it will be implementation specific.

• Big Oh ignores constants that might have an impact on certain datasets. For example, Bubble Sort is O(n*n) but can detect a pre-sorted array in O(n) and is very fast with almost-sorted arrays.

• LinkedList requires more memory to be requested to the virtual machine (creation of the Node object). Processes that require more memory to be requested can sometimes be causes for bottlenecks.

To summarize: beware of theoretical assumptions and always measure, preferably with real world data and operations :).