What to use: ArrayList vs LinkedList

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>();
    //List<Integer> list = new LinkedList<Integer>();

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

    long start = System.currentTimeMillis();

    for (int i = 0; i < 10000; i++){
        //list.add(0, i); To the front
        //list.add(i); To the end
        //list.add(list.size()/2, i); Into the middle

        //list.remove(0); From the head
        //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:

1. Add to the front:
   • LinkedList – Time of execution is: 5ms.
   • ArrayList – Time of execution is: 4358ms.
2. Add to the end:
   • LinkedList – Time of execution is: 2ms.
   • ArrayList – Time of execution is: 1ms.
3. Add into the middle:
   • LinkedList – Time of execution is: 26329ms.
   • ArrayList – Time of execution is: 1703ms.
4. Remove from the head:
   • 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.

Thanks for reading my article.

Cheers.