Why is the ArrayList in my program inserting faster than the LinkedList?

Question

So, I was watching a tutorial which explained why Linked list is faster that Array list in insertion and when the person inserted the elements in both of the lists, the Linked list was faster as expected. But when I copied the same code, the Array List inserted faster in all of the attempts when i ran this code:

    long n = (long) 1E7;


    long milliseconds = System.currentTimeMillis();

    ArrayList al = new ArrayList();

    for(int i = 0; i < n; i ++) {

        al.add(i);

    }

    System.out.println("Insertion time for ArrayList takes: " + (System.currentTimeMillis() - 
    milliseconds) + " milliseconds");

    LinkedList ll = new LinkedList();

    milliseconds = System.currentTimeMillis();

    for(int i = 0; i < n; i++) {

        ll.add(i);

    }

    System.out.println("Insertion time for LinkedList takes: " + (System.currentTimeMillis() - 
    milliseconds) + " milliseconds");

In all of the attempts, the Array list was faster in inserting the elements.

You might want to read about [how to write a correct micro-benchmark in java](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). Also, `add()` is amortized O(1) for `ArrayList`, so it won't be all that much slower for large data sets. — azurefrog, Dec 17 '19 at 18:57
Did you try addign the object types or references as well, see if that can help. Like ```ArrayList al = new ArrayList<>(); LinkedList ll = new LinkedList<>(); ``` — pdrersin, Dec 17 '19 at 18:58
So I just tried your suggestion by casting the Integer reference and the ArrayList is still faster. — mr3oh5, Dec 17 '19 at 19:03
An `ArrayList` is a random access data structure. A `linkedList` is not. And even tagging something onto the end of a linked list is slightly more expensive that assigning to an array. — WJS, Dec 17 '19 at 19:07
It depends on what you are doing. If you have lots of deletions, no. It is more efficient to delete from a linkedList. Of course you have to find the object to delete and that is a linear exercise. But to delete from an `ArrayList` requires lots of recopying. Even adding to an ArrayList will eventually require copying because they are backed by arrays which can't grow dynamically. — WJS, Dec 17 '19 at 19:16
The guy in the tutorial video taught the difference in time for the insertion, deletion and searching for an element. In the cases for deletion and searching, it was as the guy explained where Linked list was faster for deletion and ArrayList was faster for searching. In the case for insertion, he explained that the ArrayList will be slower and it happened as he said in the video when he ran the code but when i did the exact thing the ArrayList was faster. — mr3oh5, Dec 17 '19 at 19:19
Trying to determine performance with System time units is not very precise. You should use a tool made for performance analysis. — WJS, Dec 17 '19 at 19:21

Why is the ArrayList in my program inserting faster than the LinkedList?

0 Answers0