comparison of Linkedlist over arraylist

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);

        }

    }

score 4 · Answer 1 · answered Nov 04 '14 at 14:03

4

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.

answered Nov 04 '14 at 14:03

Eran

387,369
54
702
768

it is not true that inserting in the array is trivial: if you have 1 million items and insert at position 500k you will have make 500k copies to insert an item... – heorhi Nov 04 '14 at 14:15
@heorhi I was referring to an insert of a new entry to the end of the ArrayList. As for insertion in the middle, that may be slower for very large lists, but keep in mind it is done via System.arraycopy. The references are not copied one by one. – Eran Nov 04 '14 at 14:19
1

@heorhi Also keep in mind that insertion in the middle of a large LinkedList will also be slower than insertion at the end, since it requires the linked list to be iterated (from the start or from the end) until the Entry that the new entry should come after is reached. – Eran Nov 04 '14 at 14:22
you are right. I agree that the difference is not so significant, both algos are essentially linear (LinkedList must search linearly for the item). – heorhi Nov 04 '14 at 14:25

score 2 · Accepted Answer · answered Nov 04 '14 at 14:11

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);

        }
}

comparison of Linkedlist over arraylist

2 Answers2

Linked

Related