ArrayList is faster than LInkedList in inserting and removing the elements at the middle according to this program

Question

According the below program the insertion and deletion in ArrayList is faster than LinkedList. Please provide me the proof of the fact that Insertion and deletion should be faster in LinkedList than ArrayList.

public static void main(String args[]) {
    ArrayList al = new ArrayList();
    LinkedList ll = new LinkedList();
    int max_value = 10000000;

    // --------------------------------ArrayList-----------------------------------

    for (int i = 0; i <= max_value; i++) {
        ll.add(Integer.valueOf(i));
        al.add(Integer.valueOf(i));
    }

    int middle = max_value / 2;

    long d1 = System.currentTimeMillis();
    al.add(middle,Integer.valueOf(5));
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));

    long d2 = System.currentTimeMillis();
    System.out.println("Time Taken in ArrayList:  " + (d2 - d1));

    // --------------------------------LinkedList-----------------------------------

    long d3 = System.currentTimeMillis();
    ll.add(middle,Integer.valueOf(5));
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));

    long d4 = System.currentTimeMillis();
    System.out.println("Time Taken in LinkedList:  " + (d4 - d3));

}

Output:

Time Taken in ArrayList: 38 Time Taken in LinkedList: 537

Please provide me the proof of the fact that Insertion and deletion should be faster in LinkedList than ArrayList. Why do you think that insertion in linkedlist is faster? — Karthik
– Karthik, Commented Aug 15, 2015 at 11:27
docs.oracle.com/javase/tutorial/collections/implementations/… — Atul_15
– Atul_15, Commented Aug 15, 2015 at 11:30
can you quote which part of that documentation says that insertion in linkedlist in the middle is faster than Arraylist? — Karthik
– Karthik, Commented Aug 15, 2015 at 11:37

Sami Kuhmonen · Accepted Answer · 2015-08-15 12:06:18Z

6

What you have here is a single case. In this case you're adding and removing at an index. The linked list implementation doesn't know which item is at that position, so it has to count there every time. This operation will be slower.

If instead you had an iterator to an item in the linked list then insertion and deletion at that point become very fast, since there is no copying of arrays or enlargement of the container array. This is the general case why linked lists are faster.

One example of this kind of behavior is when you are iterating the list and need to remove items based on some condition. Then each time an item needs to be deleted a single linked list would just set the previous item to point to the element after the removed element and destroy the removed element. This is constant time operation. With an array(list) this would require copying the rest of the array one item backwards, which is a lot slower operation and depends on the location and the size of the array(list).

So it is not true that linked lists would be universally faster or better, that's why we still use regular arrays and lists. They are slow in random access, but faster when used properly.

edited Aug 15, 2015 at 12:06

answered Aug 15, 2015 at 11:28

Sami Kuhmonen

31.4k9 gold badges67 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Sami Kuhmonen Over a year ago

@davmac Yes, that's the word. Thanks

Atul_15 Over a year ago

@SamiKuhmonen Thanks.

Atul_15 Over a year ago

@SamiKuhmonen can you provide the program of adding the element in LinkedList using pointer and the statistics also that shows it is faster than ArrayList .

Collectives™ on Stack Overflow

ArrayList is faster than LInkedList in inserting and removing the elements at the middle according to this program

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related