Select Page

I think that this article should be interesting for all who have a question “what data structure to use?”. In this article we will compare  ArrayList and LinkedList. Data type is Integer. List size is 1 000 000 items. We will perform a 10 000 operations with the lists, such as: adding to the front, adding to end, adding to the middle, remove from the head, remove from the end, remove from the middle.
How we will do it:

```public void listTimeTest(){
List<Integer> list = new ArrayList<Integer>();

for(int i = 0; i < 1000000; i++){
}

long start = System.currentTimeMillis();

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

//list.remove(list.size()-1); From the end
//list.remove(list.size()/2); From the middle
}

long end = System.currentTimeMillis();

System.out.print("Time of execution is: " + (end - start) + "ms.");
}```

Time results are very interesting:

• LinkedList – Time of execution is: 5ms.
• ArrayList – Time of execution is: 4358ms.
• LinkedList – Time of execution is: 2ms.
• ArrayList – Time of execution is: 1ms.
• LinkedList – Time of execution is: 26329ms.
• ArrayList – Time of execution is: 1703ms.
• LinkedList – Time of execution is: 4ms.
• ArrayList – Time of execution is: 4220ms.
5. Remove from the end:
• LinkedList – Time of execution is: 3ms.
• ArrayList – Time of execution is: 1ms.
6. Remove from the middle:
• LinkedList – Time of execution is: 27737ms.
• ArrayList – Time of execution is: 1793ms.

So, as You see, ArrayList won everything except operations in the head of the list.

Resolution:

• If You want to perform operations in the front  of the list – use LinkedList
• If You want to perform operations in the end  of the list – doesn’t matter what to use because time of execution is almost the same (approx. 1-3ms)
• If You want to perform operations in the middle of the list –  use only ArrayList. Difference in the time is almost 15x times faster then LinkedList.