Java: ArrayList vs LinkedList

As a Java developer, it's important to understand the different data structures available in the Java programming language and how to choose the right one for your specific problem.

ArrayList and LinkedList

Both ArrayList and LinkedList are data structures used for storing lists of items, but they have different characteristics and performance metrics.

The Test

Let's create a simple program (GitHub link) that compares the performance of ArrayList and LinkedList when inserting, accessing and deleting elements.

private static void compareArrayListLinkedList() {

    List<Integer> arrayList = new ArrayList<>();
    List<Integer> linkedList = new LinkedList<>();

    System.out.println("Operation\\t| ArrayList\\t| LinkedList");
    System.out.println("--------------------------------------------");

    System.out.print("Add At End\\t| ");
    int size = 50000000;
    long start = System.currentTimeMillis();
    for(int i = 0; i < size; i++) {
        arrayList.add(i);
    }
    long end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t| ");

    start = System.currentTimeMillis();
    for(int i = 0; i < size; i++) {
        linkedList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");

    System.out.print("Add At Index\\t| ");
    size = 250;
    start = System.currentTimeMillis();
    for(int i = 0; i < size; i++) {
        arrayList.add(i, i);
    }
    end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t| ");

    start = System.currentTimeMillis();
    for(int i = 0; i < size; i++) {
        linkedList.add(i, i);
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");


    System.out.print("Get By Index\\t| ");
    size = 50000;
    start = System.currentTimeMillis();
    for(int i = 0; i < size; i++) {
        arrayList.get(i);
    }
    end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t\\t| ");

    start = System.currentTimeMillis();
    for(int i = 0; i < size; i++) {
        linkedList.get(i);
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");


    System.out.print("Get By Iterator\\t| ");
    start = System.currentTimeMillis();
    for (Iterator<Integer> i = arrayList.iterator(); i.hasNext();) {
        i.next();
    }
    end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t\\t| ");

    start = System.currentTimeMillis();
    for (Iterator<Integer> i = linkedList.iterator(); i.hasNext();) {
        i.next();
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");


    System.out.print("Remove By Value\\t| ");
    size = 250;
    start = System.currentTimeMillis();
    for(int i = size; i >= 0 ; i--) {
        arrayList.remove(Integer.valueOf(i));
    }
    end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t| ");

    start = System.currentTimeMillis();
    for(int i = size; i >= 0 ; i--) {
        linkedList.remove(Integer.valueOf(i));
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");


    System.out.print("Remove By Index\\t| ");
    size = 250;
    start = System.currentTimeMillis();
    for(int i = size; i >= 0 ; i--) {
        arrayList.remove(i);
    }
    end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t| ");

    start = System.currentTimeMillis();
    for(int i = size; i >= 0 ; i--) {
        linkedList.remove(i);
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");


    System.out.print("Remove From End\\t| ");
    start = System.currentTimeMillis();
    for(int i = arrayList.size()-1; i >= 0 ; i--) {
        arrayList.remove(i);
    }
    end = System.currentTimeMillis();
    System.out.print(end - start + " ms\\t| ");

    start = System.currentTimeMillis();
    for(int i = linkedList.size()-1; i >= 0 ; i--) {
        linkedList.remove(i);
    }
    end = System.currentTimeMillis();
    System.out.println(end - start + " ms");

}

Results

Operation        | ArrayList    | LinkedList
--------------------------------------------
Add At End        | 5018 ms    | 9585 ms
Add At Index    | 45566 ms    | 1 ms
Get By Index    | 25 ms        | 3085 ms
Get By Iterator    | 51 ms        | 2187 ms
Remove By Value    | 28678 ms    | 1 ms
Remove By Index    | 26895 ms    | 2 ms
Remove From End    | 186 ms    | 2622 ms

Conclusion

LinkedList performs better when you add or remove elements from the middle. This is because LinkedList just needs to update the previous and next references after an element is added or removed. However, ArrayList needs to shift all the subsequent elements.

For all other use cases, ArrayList is a better choice in terms of performance.