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?

Because benchmarking is hard. https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — awksp, May 15 '14 at 17:34
Sorry but your test is completely broken. See http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Alexis C., May 15 '14 at 17:34
Try reversing the call of `doCalculations` in your `main` method and you will get completely different results ;) — Luiggi Mendoza, May 15 '14 at 17:34
Call `doCalculations("LinkedList",LinkedList)` first, then `doCalculations("ArrayList",ArrayList);` and you'll see. — Luiggi Mendoza, May 15 '14 at 17:36
@LuiggiMendoza why is timings different now? these kind of things makes me sometimes hate programming :( — saurabh kumar, May 15 '14 at 17:38
@saurabhkumar Read the links ZouZou and I provided, and you might understand. Long story short, benchmarks are hard. — awksp, May 15 '14 at 17:39
@user3580294 they are hard if you try to reinvent the wheel. — Luiggi Mendoza, May 15 '14 at 17:40
Even with a proper benchmark, List.add(0,i) should be *significantly* slower on an ArrayList because it has to move all the existing elements to the right each time, whereas the LinkedList just appends a node to the front. — spudone, May 16 '14 at 00:21

score 4 · Accepted Answer · edited May 23 '17 at 12:13

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.

score 0 · Answer 2 · answered May 15 '14 at 23:02

0

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

answered May 15 '14 at 23:02

xceeder88

1

but then why its faster ? – saurabh kumar May 16 '14 at 17:07

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

2 Answers2

Linked