arraylist vs linked list .why linked list is slower when we add in the end?

Question

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class CompareList {
public static void main(String[] args) {
 List<Integer> ArrayList = new ArrayList<Integer>();
 List<Integer> LinkedList = new LinkedList<Integer>();
 doCalculations("ArrayList",ArrayList);
 doCalculations("LinkedList",LinkedList); 
}
private static void doCalculations(String type,List<Integer> List){
 for(int i=0;i<1E5;i++){
 List.add(i); 
 }
 Long start = System.currentTimeMillis();
 /*
 To add elements in the end 
 for(int i=0;i<1E5;i++){
 List.add(i); 
 }
 */
 for(int i=0;i<1E5;i++){
 List.add(0,i);
 }
 Long end = System.currentTimeMillis();
 System.out.println("time taken" +" "+ (end-start) + "ms for" +" "+ type);
}
}

time taken 13ms for ArrayList time taken 64ms for LinkedList

i know this is duplicate question ,but please don't remove this ,whatever answers they gave to this question i was unable understand ,Can anyone explain this in simple words why this linked list is slower when we add element in the end?

• awksp: Because benchmarking is hard. stackoverflow.com/questions/504103/…
• Alexis C.: Sorry but your test is completely broken. See stackoverflow.com/questions/504103/…
• Luiggi Mendoza: Try reversing the call of doCalculations in your main method and you will get completely different results ;)
• saurabh kumar: @LuiggiMendoza what do you mean by reversing?
• Luiggi Mendoza: Call doCalculations("LinkedList",LinkedList) first, then doCalculations("ArrayList",ArrayList); and you'll see.

Answer 1

What you're currently doing here is a micro benchmark. This is not an easy task, because you have to take into account all these tips: How do I write a correct micro-benchmark in Java?.

Still, there's no need to reinvent the wheel. There are frameworks that ease this work like JUnitBenchmarks and Caliper that help you to perform real benchmarks for your pieces of code/algorithms by using JUnit tests.

Answer 2

linked list is slower cuz it is like a train.......it have to check each element and check it is value ..until it find the matched element..so think of it like chained train and you want to go from the first of the train to the end

• saurabh kumar: but then why its faster ?