comparison of Linkedlist over arraylist [duplicate]

Question

I understood that LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods.

Does that mean I should choose LinkedList over Arraylist for inserting?

I wrote a small test and found ArrayList is faster in inserting. Then how does linked list faster than ArrayList?

Please refer the below example which I have done.

    import java.util.Date;
    import java.util.LinkedList;
    import java.util.List;

    public class TestLinkedList {

        public static void main(String[] args) {

            long lStartTime = new Date().getTime();
            System.out.println("lStartTime:: " + lStartTime);
            List<Integer> integerList = new LinkedList<Integer>();
            for (int i = 0; i < 10000000; i++) {
                integerList.add(i);
            }

            long lEndTime = new Date().getTime();
            System.out.println("lEndTime:: " + lEndTime);

            long difference = lEndTime - lStartTime;

            System.out.println("Elapsed milliseconds: " + difference);

        }

    }

Answer 1

LinkedList is not faster than ArrayList in insertion. ArrayList is backed by an array, so inserting an element is trivial. Insertion to a LinkedList involves creation of a new Entry instance, which is slower.

The only time insert to an ArrayList may be slower is when the insert causes the ArrayList capacity to be increased, which requires a new array to be created and the old array copied to it.

Answer 2

Linkedlist is indeed faster on insertion, the problem is with your example. In your code you insert by appending to the end all the time. For ArrayList it is as easy as for LinkedList. What you should do is to build a list of say 5000 items and then start inserting in the middle. Here array becomes slow - you have to shift all the time the rest of the array after the insertion position. This is what will show the difference. Analyzing how the things work, it is not difficult to understand why. Here is the modified code:

import java.util.Date;
    import java.util.LinkedList;
    import java.util.ArrayList;
    import java.util.List;

    public class Prob {

        public static void main(String[] args) {

            long lStartTime = new Date().getTime();
            System.out.println("lStartTime:: " + lStartTime);
            List<Integer> integerList = new LinkedList<Integer>();
            for (int i = 0; i < 5000; i++) {
                integerList.add(0, i);
            }
            for (int i = 0; i < 100000; i++) {
                integerList.add(1000, i);
            }

            long lEndTime = new Date().getTime();
            System.out.println("lEndTime:: " + lEndTime);

            long difference = lEndTime - lStartTime;

            System.out.println("Elapsed milliseconds: " + difference);

        }
}