Which is Faster - LinkedList or ArrayList? or When to use LinkedList over ArrayList?

This article compares LinkedList and ArrayList and describes which is faster and when to use one over another with examples.

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

Let us see the performance of ArrayList and LinkedList in different scenarios.

1) Retrieve an element from the list


     a)Retrieve elements at the beginning

import java.util.*;

public class Main {

public static void main(String args[]) {

ArrayList<Integer> arrayList = new ArrayList<Integer>();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}

long start = new Date().getTime();
for (int i = 0; i < 10000; i++)
arrayList.get(0);
long end = new Date().getTime();
System.out.println("ArrayList: Retrieving element at the beginning:"+ (end - start)+" ms");

LinkedList<Integer> linkedList = new LinkedList<Integer>();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
long start_linked = new Date().getTime();
for (int i = 0; i < 10000; i++)
linkedList.get(0);
long end_linked = new Date().getTime();
System.out.println("LinkedList: Retrieving element at the beginning:"+ (end_linked - start_linked)+" ms");
}

}

The output is

ArrayList: Retrieving element at the beginning:0 ms

LinkedList: Retrieving element at the beginning:2 ms

     b)Retrieve elements in the middle

import java.util.*;

public class Main {

public static void main(String args[]) {

ArrayList<Integer> arrayList = new ArrayList<Integer>();

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

arrayList.add(i);

}

long start = new Date().getTime();

for (int i = 0; i < 10000; i++)

arrayList.get(50000);

long end = new Date().getTime();

System.out.println("ArrayList: Retrieving elements in the middle:"+ (end - start)+" ms");

LinkedList<Integer> linkedList = new LinkedList<Integer>();

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

linkedList.add(i);

}

long start_linked = new Date().getTime();

for (int i = 0; i < 10000; i++)

linkedList.get(50000);

long end_linked = new Date().getTime();

System.out.println("LinkedList: Retrieving elements in the middle:"+ (end_linked - start_linked)+" ms");

}

}

The output is

ArrayList: Retrieving elements in the middle:0 ms

LinkedList: Retrieving elements in the middle:6956 ms

    c)Retrieve elements at the end

import java.util.*;

public class Main {

public static void main(String args[]) {

ArrayList<Integer> arrayList = new ArrayList<Integer>();

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

arrayList.add(i);

}

long start = new Date().getTime();

for (int i = 0; i < 10000; i++)

arrayList.get(99999);

long end = new Date().getTime();

System.out.println("ArrayList: Retrieving element at the end:"+ (end - start)+" ms");

LinkedList<Integer> linkedList = new LinkedList<Integer>();

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

linkedList.add(i);

}

long start_linked = new Date().getTime();

for (int i = 0; i < 10000; i++)

linkedList.get(99999);

long end_linked = new Date().getTime();

System.out.println("LinkedList: Retrieving element at the end:"+ (end_linked - start_linked)+" ms");

}

}

The output is

ArrayList: Retrieving element at the end:0 ms

LinkedList: Retrieving element at the end:2 ms

2) Insert an element into the list

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.The default capacity of the list is 10 .You can specify the capacity externally while list creation using the constructor, public ArrayList(int initialCapacity).If you create the arraylist with suitable capacity,this may reduce the amount of incremental reallocation,but unwanted capacity costs memory.
The LinkedList is implemented using doubly-linked list.Each LinkedList node has three parts,data part and addresses pointing to left and right nodes.So that LinkedList is consuming more memory compared to ArrayList.

    a)Insert elements at the beginning.

import java.util.*;

public class Main {

public static void main(String args[]) {

ArrayList<Integer> arrayList = new ArrayList<Integer>();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long start = new Date().getTime();
for (int i = 0; i < 10000; i++)
arrayList.add(0, -1);
long end = new Date().getTime();
System.out.println("ArrayList: For 10000 insertions at beginning:"+ (end - start)+" ms");

LinkedList<Integer> linkedList = new LinkedList<Integer>();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
long start_linked = new Date().getTime();
for (int i = 0; i < 10000; i++)
linkedList.add(0, -1);
long end_linked = new Date().getTime();
System.out.println("LinkedList: For 10000 insertions at beginning:"+ (end_linked - start_linked)+" ms");
}
}

The output is:

ArrayList: For 10000 insertions at beginning:1305 ms

LinkedList: For 10000 insertions at beginning:2 ms

You can see that for inserting an element at the first position, ArrayList is taking more time compared to LinkedList.Since the ArrayList is implemented using array, need to shift all the elements right when an element is inserted at the first position.But LinkedList can insert an element at first position just by creating a link to the neighboring element.

    b)Insert elements in the middle



import java.util.*;

public class Main {

public static void main(String args[]) {

ArrayList<Integer> arrayList = new ArrayList<Integer>();
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
}
long start = new Date().getTime();
for (int i = 0; i < 10000; i++)
arrayList.add(50000, -1);
long end = new Date().getTime();
System.out.println("ArrayList: For 10000 insertions in  middle :"+ (end - start)+" ms");

LinkedList<Integer> linkedList = new LinkedList<Integer>();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
long start_linked = new Date().getTime();
for (int i = 0; i < 10000; i++)
linkedList.add(50000, -1);
long end_linked = new Date().getTime();
System.out.println("LinkedList: For 10000 insertions in middle:"+ (end_linked - start_linked)+" ms");
}

}

The output is

ArrayList: For 10000 insertions in middle:578 ms

LinkedList: For 10000 insertions in middle:7827 ms

You can see that, LinkedList is taking more time compared to the ArrayList.Since there is no random access in LinkedList, it has to sequentially navigate to the middle element and then inserts element.This sequential element access is expensive.

     c)Insert elements at the end

import java.util.*;

public class Main {

public static void main(String args[]) {

ArrayList<Integer> arrayList = new ArrayList<Integer>();

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

arrayList.add(i);

}

long start = new Date().getTime();

for (int i = 0; i < 10000; i++)

arrayList.add(100000, -1);

long end = new Date().getTime();

System.out.println("ArrayList: For 10000 insertions at end:"+ (end - start)+" ms");

LinkedList<Integer> linkedList = new LinkedList<Integer>();

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

linkedList.add(i);

}

long start_linked = new Date().getTime();

for (int i = 0; i < 10000; i++)

linkedList.add(100000, -1);

long end_linked = new Date().getTime();

System.out.println("LinkedList: For 10000 insertions at end:"+ (end_linked - start_linked)+" ms");

}

}

The output is

ArrayList: For 10000 insertions at end:50 ms

LinkedList: For 10000 insertions at end:189 ms

LinkedList is taking more time compared to ArrayList.

3) Delete an element from the list

This scenario is same as inserting an element.Please refer the above.

Conclusion

I have executed these codes using ubuntu machine and java 1.6.According to my experiment you can efficiently use LinkedList in only one scenario -you need to add/remove elements at the beginning of a list and you are ready to compromise the random access to elements facility.In all other scenarios use ArrayList.Another disadvantage of linked lists is the extra storage needed for references.