[java] Performance differences between ArrayList and LinkedList

Yes, this is an old topic, but I still have some confusions.

In Java, people say:

1. ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?

2. LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated. A code explanation:

   List<String> list = new ArrayList<String>();
   list.add("a");
   list.add("b");
   list.add("c");
   list.remove("b");
   System.out.println(list.get(1)); //output "c"
   

3. LinkedList is faster than ArrayList for insertion. What does insertion mean here? If it means to move some elements back and then put the element in the middle empty spot, ArrayList should be slower than LinkedList. If insertion only means an add(Object) operation, how could this be slow?

Ignore this answer for now. The other answers, particularly that of aix, are mostly correct. Over the long term they're the way to bet. And if you have enough data (on one benchmark on one machine, it seemed to be about one million entries) ArrayList and LinkedList do currently work as advertized. However, there are some fine points that apply in the early 21st century.

Modern computer technology seems, by my testing, to give an enormous edge to arrays. Elements of an array can be shifted and copied at insane speeds. As a result arrays and ArrayList will, in most practical situations, outperform LinkedList on inserts and deletes, often dramatically. In other words, ArrayList will beat LinkedList at its own game.

The downside of ArrayList is it tends to hang onto memory space after deletions, where LinkedList gives up space as it gives up entries.

The bigger downside of arrays and ArrayList is they fragment free memory and overwork the garbage collector. As an ArrayList expands, it creates new, bigger arrays, copies the old array to the new one, and frees the old one. Memory fills with big contiguous chunks of free memory that are not big enough for the next allocation. Eventually there's no suitable space for that allocation. Even though 90% of memory is free, no individual piece is big enough to do the job. The GC will work frantically to move things around, but if it takes too long to rearrange the space, it will throw an OutOfMemoryException. If it doesn't give up, it can still slow your program way down.

The worst of it is this problem can be hard to predict. Your program will run fine one time. Then, with a bit less memory available, with no warning, it slows or stops.

LinkedList uses small, dainty bits of memory and GC's love it. It still runs fine when you're using 99% of your available memory.

So in general, use ArrayList for smaller sets of data that are not likely to have most of their contents deleted, or when you have tight control over creation and growth. (For instance, creating one ArrayList that uses 90% of memory and using it without filling it for the duration of the program is fine. Continually creating and freeing ArrayList instances that use 10% of memory will kill you.) Otherwise, go with LinkedList (or a Map of some sort if you need random access). If you have very large collections (say over 100,000 elements), no concerns about the GC, and plan lots of inserts and deletes and no random access, run a few benchmarks to see what's fastest.

I want to add an additional piece of information her about the difference in performance.

We already know that due to the fact that ArrayList implementation is backed by an Object[] it's supports random access and dynamic resizing and LinkedList implementation uses references to head and tail to navigate it. It has no random access capabilities, but it supports dynamic resizing as well.

The first thing is that with an ArrayList, you can immediately access the index, whereas with a LinkedList, you have iterate down the object chain.

Secondly, inserting into ArrayList is generally slower because it has to grow once you hit its boundaries. It will have to create a new bigger array, and copy data from the original one.

But the interesting thing is that when you create an ArrayList that is already huge enough to fit all your inserts it will obviously not involve any array copying operations. Adding to it will be even faster than with LinkedList because LinkedList will have to deal with its pointers, while huge ArrayList just sets value at given index.

Check out for more ArrayList and LinkedList differences.

ArrayList

• ArrayList is best choice if our frequent operation is retrieval operation.
• ArrayList is worst choice if our operation is insertion and deletion in the middle because internally several shift operations are performed.
• In ArrayList elements will be stored in consecutive memory locations hence retrieval operation will become easy.

LinkedList:-

• LinkedList is best choice if our frequent operation is insertion and deletion in the middle.
• LinkedList is worst choice is our frequent operation is retrieval operation.
• In LinkedList the elements won't be stored in consecutive memory location and hence retrieval operation will be complex.

Now coming to your questions:-

1) ArrayList saves data according to indexes and it implements RandomAccess interface which is a marker interface that provides the capability of a Random retrieval to ArrayList but LinkedList doesn't implements RandomAccess Interface that's why ArrayList is faster than LinkedList.

2) The underlying data structure for LinkedList is doubly linked list so insertion and deletion in the middle is very easy in LinkedList as it doesn't have to shift each and every element for each and every deletion and insertion operations just like ArrayList(which is not recommended if our operation is insertion and deletion in the middle because internally several shift operations are performed).
Source

The ArrayList class is a wrapper class for an array. It contains an inner array.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList is a wrapper class for a linked list, with an inner node for managing the data.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

Note, the present code is used to show how the class may be, not the actual implementation. Knowing how the implementation may be, we can do the further analysis:

ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?

Access time for ArrayList: O(1). Access time for LinkedList: O(n).

In an array, you can access to any element by using array[index], while in a linked list you must navigate through all the list starting from first until you get the element you need.

LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.

Deletion time for ArrayList: Access time + O(n). Deletion time for LinkedList: Access time + O(1).

The ArrayList must move all the elements from array[index] to array[index-1] starting by the item to delete index. The LinkedList should navigate until that item and then erase that node by decoupling it from the list.

LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.

Insertion time for ArrayList: O(n). Insertion time for LinkedList: O(1).

Why the ArrayList can take O(n)? Because when you insert a new element and the array is full, you need to create a new array with more size (you can calculate the new size with a formula like 2 * size or 3 * size / 2). The LinkedList just add a new node next to the last.

This analysis is not just in Java but in another programming languages like C, C++ and C#.

More info here:

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

Answer to 1: ArrayList uses an array under the hood. Accessing a member of an ArrayList object is as simple as accessing the array at the provided index, assuming the index is within the bounds of the backing array. A LinkedList has to iterate through its members to get to the nth element. That's O(n) for a LinkedList, versus O(1) for ArrayList.

Both remove() and insert() have a runtime efficiency of O(n) for both ArrayLists and LinkedLists. However the reason behind the linear processing time comes from two very different reasons:

In an ArrayList you get to the element in O(1), but actually removing or inserting something makes it O(n) because all the following elements need to be changed.

In a LinkedList it takes O(n) to actually get to the desired element, because we have to start at the very beginning until we reach the desired index. Removing or inserting is constant once we get there, because we only have to change 1 reference for remove() and 2 references for insert().

Which of the two is faster for inserting and removing depends on where it happens. If we are closer to the beginning the LinkedList will be faster, because we have to go through relatively few elements. If we are closer to the end an ArrayList will be faster, because we get there in constant time and only have to change the few remaining elements that follow it.

Bonus: While there is no way of making these two methods O(1) for an ArrayList, there actually is a way to do this in LinkedLists. Lets say we want to go through the entire List removing and inserting elements on our way. Usually you would start from the very beginning for each elements using the LinkedList, we could also "save" the current element we're working on with an Iterator. With the help of the Iterator we get a O(1) efficiency for remove() and insert() when working in a LinkedList. Making it the only performance benefit I'm aware of where a LinkedList is always better than an ArrayList.

ArrayList: The ArrayList class extends AbstractList and implements the List interface and RandomAccess (marker interface). ArrayList supports dynamic arrays that can grow as needed. It gives us first iteration over elements.

LinkedList: A LinkedList is ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. This linkage gives you new methods (beyond what you get from the List interface) for adding and removing from the beginning or end, which makes it an easy choice for implementing a stack or queue. Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion. As of Java 5, the LinkedList class has been enhanced to implement the java.util.Queue interface. As such, it now supports the common queue methods: peek (), poll (), and offer ().

ArrayList: ArrayList has a structure like an array, it has a direct reference to every element. So rendom access is fast in ArrayList.

LinkedList: In LinkedList for getting nth elemnt you have to traverse whole list, takes time as compared to ArrayList. Every element has a link to its previous & nest element, so deletion is fast.

In a LinkedList the elements have a reference to the element before and after it. In an ArrayList the data structure is just an array.

1. A LinkedList needs to iterate over N elements to get the Nth element. An ArrayList only needs to return element N of the backing array.

2. The backing array needs to either be reallocated for the new size and the array copied over or every element after the deleted element needs to be moved up to fill the empty space. A LinkedList just needs to set the previous reference on the element after the removed to the one before the removed and the next reference on the element before the removed element to the element after the removed element. Longer to explain, but faster to do.

3. Same reason as deletion here.

Even they seem to identical(same implemented inteface List - non thread-safe),they give different results in terms of performance in add/delete and searching time and consuming memory (LinkedList consumes more).

LinkedLists can be used if you use highly insertion/deletion with performance O(1). ArrayLists can be used if you use direct access operations with performance O(1)

This code may make clear of these comments and you can try to understand performance results. (Sorry for boiler plate code)

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}