Why get different results regarding time when pasting to LinkedList and ArrayList

Question

I worked with LinkedList and ArrayList, and I know the concept of adding elements to ArrayList and LinkedList, but when I run the insert time check code, I get another insert time again and again for both LinkedList and ArrayList.

Sometimes, the LinkedList insertion time comes better, and vice versa, how exactly this happens, can someone tell me.

import java.util.ArrayList; public class Time { public static void main(String args[]) { int n=100000; long milis = System.currentTimeMillis(); ArrayList obj=new ArrayList(); for(int k=0;k<=n;k++) { obj.add(k); } System.out.println("insert arraylist takes " +(System.currentTimeMillis()-milis)+" ms"); } } 

The output of this program

1) arraylist insert takes 13 ms 2) arraylist insert takes 9 ms

Second code

  import java.util.LinkedList; public class Time1 { public static void main(String args[]) { int n=100000; long milis = System.currentTimeMillis(); LinkedList obj=new LinkedList(); for(int k=0;k<=n;k++) { obj.add(k); } System.out.println("insert linklist takes " +(System.currentTimeMillis()-milis)+" ms"); } } 

Result of this

1) insert linklist takes 8 ms

2) insert linklist takes 17 ms

Answer 1

In general, a linked list will be more effective at adding and removing items anywhere except at the end of the list, but will be much slower when searching for an arbitrary index in the list. To add or remove an element anywhere, LinkedList just needs to change a couple of links, but in ArrayList everything that needs to be changed after that. From the point of view of searching for an arbitrary index, ArrayList just goes to this place in memory, LinkedList should go through each element to this point.

This is a trivial example. There are two main reasons why you do not see it above:

• Firstly, microbenchmarks suck in better times, but especially in a language such as Java, where you have a JIT that will “warm up” and change performance in the process. Either compare it in a real-world scenario, or you can pretty much say goodbye to any real performance metric.

• Secondly, ArrayList has shown great optimization over the years, to the point that I even noticed that it works faster on certain occasions when you classically expect LinkedList win.

Personally, I stick with ArrayList in a real-world application that I use, and not in a micro-controller, and measure performance. If the performance was unacceptable, I would switch the implementation to LinkedList (this should be a one-line change) and then run the test again to check. Without these checks, it is almost impossible to say what would work best in your scenario.

Answer 2

You will need to use obj in some way to avoid a "hot spot" optimizing your entire loop.

Answer 3

Every time you start Java benchmarking, you should be very skeptical about your results. In most cases, your results will show different results that you might expect. There are too many factors that can affect the performance of your program. To do the right test, you need a deep understanding of the JVM. The simplest points that I can tell you:

• JIT warm up (your first benchmark results will usually be much worse than later).
• DCE aka Dead Elemination. It is not your business, but it is useful to know about it.

To make a good result with results that could be correctly interpreted, I recommend looking at Java Harness and thoroughly checking and running all the examples .