Java ArrayList vs LinkedList
1 CommentLists 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 inLinkedList
, 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 anArrayList
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
thanArrayList
. - Queue functionality:
ArrayList
can act only as list butLinkedList
can act both as list and queue as it implements theList
andDeque
interfaces. - Memory overhead: Memory overhead in
LinkedList
is more as compared toArrayList
as a node inLinkedList
needs to maintain the addresses of next and previous nodes. Whereas an ArrayList doesn’t have this overhead as in anArrayList
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 anArrayList
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 theArrayList
with a higher initial capacity. - Reverse iterator:
LinkedList
can be iterated in reverse direction usingdescendingIterator()
while there is nodescendingIterator()
inArrayList
. 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.
Operation | ArrayList | LinkedList |
get(int index) | Runs in constant time i.e O(1) | Runs proportionately to the amount of data because it has to traverse the list from the beginning or end (whichever is closer) to get to the n-th element. A time complexity of O(n) , on average. However, for index =0 , it is O(1) |
add(E element) | Adds to the end of list. Comes with memory resizing cost.
This happens because there is extra cost of resizing the array and copying elements to the new array. | Adds to the end of the list.
|
add(int index, E element) | Adds to the specific index position. Requires shifting and possible memory resizing cost if internal array is filled. O(n) | O(n) but O(1) when index = 0 |
remove(int index) | O(n) | O(n) |
Iterator.remove() | O(n) | O(1) |
ListIterator.add(E element) | O(n) | O(1) |
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.
List Implementation | Number of Elements (MAX_ELEMENTS) | Add a single element List.add() ns/run | Remove a single element List.remove() ns/run | Retrieve a single element List.get() ns/run | Check if an element is present List.contains() ns/run | Iterate to find an element and remove ns/run | Add all elements of a collection List.addAll() ns/run |
content | content | content | content | content | content | content | content |
content | content | content | content | content | content | content | content |
content | content | content | content | content | content | content | content |
content | content | content | content | content | content | content | content |
content | content | content | content | content | content | content | content |
content | content | content | content | content | content | content | content |
content | content | content | content | content | content | content | content |
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
.
Diederik
The overview of the testresults are replaced with ‘content’ can you fix this ?