Last Updated on June 14, 2019 by Simanta

Lists are common data structures in Java. Elements in a List have a specific order and can include duplicate elements.

List have different implementations based on different use cases. The two key ones are ArrayList and LinkedList.

Novice programmers often tend to use both the implementations interchangeably. However, both ArrayList and LinkedList have significant differences on what that are designed for and how they are internally implemented.

In this post, I will differentiate ArrayList from LinkedList, measure their performances across different operations, and list out specific use cases for them.

ArrayList and LinkedList: Introduction

Java ArrayList internally uses a dynamic array for storing elements. An ArrayList is not synchronized and therefore allows fast random read access. When more and more elements are added into an ArrayList, the capacity of the underlying array grows 50% of its size each time. Internally, a new array which is 1.5 times the size the original array is allocated, and the old array is copied to the new one.

Java LinkedList uses doubly linked list to store elements. LinkedList allows for constant-time insertions or removals using iterators. However, it allows only sequential access of elements. You can walk the list forwards or backwards. Also, LinkedList, similar to ArrayList is not synchronized.

Comparing ArrayList and LinkedList

Both ArrayList and LinkedList are similar to use. The main difference is their implementation that gives different performances in different operations. The major differences between the two are:

• Random access of elements: ArrayList allows fast and random access of elements as it is essentially an array that works on index basis. Its elements can be directly accessed using the get and set methods. Whereas in LinkedList, finding an element’s position in the list takes time proportional to the size of the list. Any indexed operation requires a traversal.
• Random insertion and deletion: As LinkedList uses doubly linked list, it takes constant time for insertions or removals as it does not require bit shifting in memory. On the other hand, adding or removing anywhere from an ArrayList except at the end requires shifting all the latter elements over, either to make an opening or fill to the gap.
• Insertion and deletion from head: Inserting or deleting elements from the head is cheaper in LinkedList than ArrayList.
• Queue functionality: ArrayList can act only as list but LinkedList can act both as list and queue as it implements the List and Deque interfaces.
• Memory overhead: Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of next and previous nodes. Whereas an ArrayList doesn’t have this overhead as in an ArrayList each index only holds the actual object (data).
• Size: An ArrayList take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added or not. The default initial capacity of an ArrayList is pretty small. But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing, when you know you’re going to add a lot of elements, construct the ArrayList with a higher initial capacity.
• Reverse iterator: LinkedList can be iterated in reverse direction using descendingIterator() while there is no descendingIterator() in ArrayList. For reverse iteration, you need to write your own implementation code.

This table shows the time complexity comparisons between various ArrayList and LinkedList operations using Big O notation.

Performance Benchmarking

Let us create a Spring Boot application to measure performance for the common operations on ArrayList and LinkedList. The main class is this.

ArraylistvslinkedlistApplication.java

package springframework.guru.arraylistvslinkedlist;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class ArraylistvslinkedlistApplication {

  public static void main(String[] args) {
    
     SpringApplication.run(ArraylistvslinkedlistApplication.class, args);
  }
}

We will next create a Java class that will define the maximum elements in the list. For the first test run, the maximum elements value is set to 500.

InitializeContants.java

package springframework.guru.arraylistvslinkedlist;

public class InitializeContants {
   static final int MAX_ELEMENTS = 500;
   String[] strings = maxArray();

   private String[] maxArray() {
       String[] strings = new String[MAX_ELEMENTS];
       Boolean result = Boolean.TRUE;
       for (int i = 0; i < MAX_ELEMENTS; i++) {
           strings[i] = getString(result, i);
           result = !result;
       }
       return strings;
   }

   protected String getString(Boolean result, int i) {
       return String.valueOf(result) + i + String.valueOf(!result);
   }
}

The maxArray() method of this code returns a String array with dummy values. The number of elements in the array is set by the MAX_ELEMENTS field.

Next, let us create a class which computes the total time taken by an operation to complete.
PerformanceAnalysis is an abstract class with methods getName(), setUp(), and run () methods. This class is written to warm up the JIT compilation and take an average over many runs.

The PerformanceAnalysis class is this.

PerformanceAnalysis.java

package springframework.guru.arraylistvslinkedlist;

public abstract class PerformanceAnalysis {

   private static final int WARMUP_RUNS = 10000;
   private static final int AVERAGE_RUNS = 100000;

   abstract String getName();
   abstract void setup();
   abstract void runMethod();

   /*Warm up runs*/ 
   public void doPerformanceTest() {
       int warmupRuns = WARMUP_RUNS;
       int averageRuns = AVERAGE_RUNS;
       for(int i=0; i<warmupRuns; i++){
           setup();
           runMethod();
       }

      /*Run operation in loop and calculate time in nanosecond for each loop*/
       long totalTime = 0;
       for(int i=0; i<averageRuns; i++) {
           setup();
           long startTime = System.nanoTime();
           runMethod();
           long endTime = System.nanoTime();
           totalTime += (endTime-startTime);
           }
       /*Print average time of operation per run*/
       System.out.println(getName()+" took "+totalTime/averageRuns+" ns/run");
   }
}

Add Operation

I have written a JUnit test class to check performance of add operations on both ArrayList and LinkedList. If you are new to JUnit, I suggest going through my series of JUnit posts.

The PerformanceAnalysisTest JUnit test class is this.

PerformanceAnalysisTest.java

package springframework.guru.arraylistvslinkedlist;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import java.util.*;

public class PerformanceAnalysisTest {

    private List<String> testList;
    private InitializeConstants initializeConstants;
    private List<String> stringList;
    String find1;
    String find2;
    int max;

    @Before
    public void set() {
        initializeConstants = new InitializeConstants();
        String[] strings = initializeConstants.strings;
        stringList = Arrays.asList(strings);
        max = initializeConstants.MAX_ELEMENTS;
        find1 = initializeConstants.getString(true, max/2 + 10);
        find2 = initializeConstants.getString(true, max/2 +20);
    }

    @After
    public void tearDown() {
        initializeConstants = null;
        stringList = null;
        find1 = null;
        find2 = null;
    }



    @Test
    public void arrayListAdd() {
        PerformanceAnalysis arrayListAdd = new PerformanceAnalysis() {
            @Override
            String getName() {
                return "ArrayList add";
            }

            @Override
            void setup() {
                testList = new ArrayList<>();
            }

            @Override
            void runMethod() {
                for (String string : stringList) {
                    testList.add(string);
                }
            }
        };
        arrayListAdd.doPerformanceTest();
    }
    @Test
    public void linkedListAdd() {
        PerformanceAnalysis linkedListAdd = new PerformanceAnalysis() {
            @Override
            String getName() { return "LinkedList add"; }

            @Override
            void setup() { testList = new LinkedList<>(); }

            @Override
            void runMethod() {
                for(String string : stringList) {
                    testList.add(string);
                }
            }
        };
        linkedListAdd.doPerformanceTest();
    }

}

The output on running the test on IntelliJ is this.

As you can see from the output, adding an element is faster in LinkedList as compared to ArrayList. This is because, in a LinkedList, once you have the correct position, insertion costs O(1). On the other hand, in an ArrayList it goes up to O(n) – all elements past the insertion point must be shifted.

Remove Operation

Next, let us compare the performance of removing an element from both the List implementations.

Here are the test cases.

@Test
public void arrayListRemove() {
    PerformanceAnalysis findInArrayList = new PerformanceAnalysis() {
        @Override
        String getName() {
            return "ArrayList remove";
        }

        @Override
        void setup() {
            testList = new ArrayList<>(max);
            testList.addAll(stringList);
        }

        @Override
        void runMethod() {
            List<String> findList = testList;
            findList.remove(find1);
            findList.remove(find2);
        }
    };
    findInArrayList.doPerformanceTest();
}
    @Test
    public void linkedListRemove() {
        PerformanceAnalysis findInLinkedList = new PerformanceAnalysis() {
            @Override
            String getName() {
                return "LinkedList remove";
            }

            @Override
            void setup() {
                testList = new LinkedList<String>();
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
                List<String> findList = testList;
                findList.remove(find1);
                findList.remove(find2);
            }
        };
        findInLinkedList.doPerformanceTest();
    }

The output on running the tests on IntelliJ is this.

As you can notice from the output, removing an element is faster in LinkedList as compared to an ArrayList. This is because, removing an element in a LinkedList only requires changes in the pointer locations in the two neighbour nodes (elements) of the node which is going to be removed. While in an ArrayList, all the elements need to be shifted to fill out the space created by removed element.

Get Operation

Our next test cases are to compare the performance of retrieving elements based on index.

Following are the test cases.

@Test
public void arrayListGet() {

    PerformanceAnalysis findInArrayList = new PerformanceAnalysis() {
        int i = 0;

        @Override
        String getName() {
            return "ArrayList get";
        }

        @Override
        void setup() {
            testList = new ArrayList<>(max);
            testList.addAll(stringList);
        }

        @Override
        void runMethod() {
            List<String> findList = testList;
            if (i < max) {
                findList.get(i);
            }
            i++;
        }
    };
    findInArrayList.doPerformanceTest();
}
@Test
public void linkedListGet() {
    PerformanceAnalysis findInLinkedList = new PerformanceAnalysis() {
        int j=0;
        @Override
        String getName() {
            return "LinkedList get";
        }

        @Override
        void setup() {
            testList = new LinkedList<String>();
            testList.addAll(stringList);
        }

        @Override
        void runMethod() {
            List<String> findList = testList;
            if (j < max) {
                findList.get(j);
            }
            j++;

        }
    };
    findInLinkedList.doPerformanceTest();
}

The output of the test cases in IntelliJ is this.

As evident from the output, retrieving an element by index is faster in ArrayList as compared to LinkedList. The reason is because ArrayList internally uses the array data structure to maintain an index based system for its elements, which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element. Therefore, get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Contains Operation

The next test is to compare the performance of both the List implementations when it comes to checking whether or not an element is present in a list.

Following are the test cases.

@Test
public void arrayListContains() {
    PerformanceAnalysis findInArrayList = new PerformanceAnalysis() {
        @Override
        String getName() {
            return "ArrayList contains";
        }

        @Override
        void setup() {
            testList = new ArrayList<>(max);
            testList.addAll(stringList);
        }

        @Override
        void runMethod() {
            List<String> findList = testList;
            findList.contains(find1);
            findList.contains(find2);
        }
    };
    findInArrayList.doPerformanceTest();
}
@Test
public void linkedListContains() {

    PerformanceAnalysis findInLinkedList = new PerformanceAnalysis() {
        @Override
        String getName() {
            return "LinkedList contains";
        }

        @Override
        void setup() {
            testList = new LinkedList<String>();
            testList.addAll(stringList);
        }

        @Override
        void runMethod() {
            List<String> findList = testList;
            findList.contains(find1);
            findList.contains(find2);
        }
    };
    findInLinkedList.doPerformanceTest();
}

The output on running the test cases on IntelliJ is this.

The contains() method of ArrayList and LinkedList internally calls the indexOf() method. The indexOf() method implementation is different in both ArrayList and LinkedList, and as shown in the test output, the ArrayList implementation, being index based is faster than LinkedList.

Find and Remove Operation

The next performance comparison is for the operation of iterating through both the List implementations to find and remove an element.

Following are the test cases.

@Test
public void arrayListFindAndRemove() throws Exception {
        PerformanceAnalysis findAndRemoveInArrayList = new PerformanceAnalysis() {
           @Override
            String getName() {
                return "ArrayList find and remove";
            }

            @Override
            void setup() {
                testList = new ArrayList<String>(max);
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
               List<String> removedList = testList;
                Iterator iterator = removedList.iterator();
                while(iterator.hasNext()) {
                    if(find1.equals(iterator.next())) {
                        iterator.remove();
                    }
                }
            }
        };
        findAndRemoveInArrayList.doPerformanceTest();
}
    @Test
    public void linkedListFindAndRemove() throws Exception {
        PerformanceAnalysis findAndRemoveInLinkedList = new PerformanceAnalysis() {
            @Override
            String getName() {
                return "LinkedList find and remove";
            }

            @Override
            void setup() {
                testList = new LinkedList<String>();
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
                List<String> removedList = testList;
                Iterator iterator = removedList.iterator();
                while(iterator.hasNext()) {
                    if(find1.equals(iterator.next())) {
                        iterator.remove();
                    }
                }
            }
        };
        findAndRemoveInLinkedList.doPerformanceTest();
 }

The output on running the test on IntelliJ is this.

As shown in the output, searching for an element and removing it using an Iterator is faster in ArrayList as compared to LinkedList.

Add All Elements Operation

Finally, let’s compare the operations of adding all the elements of a collection into both an ArrayList and a LinkedList.

The test cases are as follows.

@Test
public void arrayListAddAll() {
    PerformanceAnalysis arrayListAddAll = new PerformanceAnalysis() {
        @Override
        String getName() {
            return "ArrayList add all";
        }

        @Override
        void setup() {
            testList = new ArrayList<>();
        }

        @Override
        void runMethod() {
            testList.addAll(stringList);
        }
    };
    arrayListAddAll.doPerformanceTest();
}
@Test
public void linkedListAddAll() {
    PerformanceAnalysis linkedListAddAll = new PerformanceAnalysis() {
        @Override
        String getName() { return "LinkedList add all"; }

        @Override
        void setup() { testList = new LinkedList<>(); }

        @Override
        void runMethod() { testList.addAll(stringList); }
    };
    linkedListAddAll.doPerformanceTest();
}

The output on running the test on IntelliJ is this.

The following table lists the test results of the operations across three sets of elements.

Summary

LinkedList is not as popular as ArrayList and even Joshua Bloch, who wrote LinkedList tweeted this. However, LinkedList is a specialized solution, and, as any specialized tool, in most cases it is outperformed by a more versatile one, like the ArrayList.

Go for LinkedList if your use case is more insertion and deletion driven and without random access.
Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList.

But again, ArrayDeque may be a better alternative to LinkedList for adding and removing from the head, but it is not a List.