Performance Analysis of ArrayList and LinkedList in Java
A detailed analysis of ArrayList and LinkedList in Java.
Join the DZone community and get the full member experience.
Join For FreeArrayList
and LinkedList
are frequently used classes in the Java collection framework. If you know only understand basic performance comparisons of ArrayList
and LinkedList
, but not the minor details of these two classes, then this article is for you.
"ArrayList
should be used where more search operations are required, andLinkedList
should be used where more insert and delete operation is needed."
ArrayList
uses the Array
data structure, and LinkedList uses the DoublyLinkedList
data structure. Here, we are going to discuss how the underlying data structure affects the performance of insert, search, and delete operation on ArrayList
and LinkedList
.
Below is an example of different operations using ArrayList
and LinkedList
.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Example {
public static void main(String[] args) {
List<Integer> linkedList = new LinkedList<>();
List<Integer> arrayList = new ArrayList<>();
/*Block 1: Insert at last in LinkedList*/
linkedList.add(1);
linkedList.add(111);
System.out.println(linkedList); /* Output: [1, 111]*/
/*Block 2: Insert at last in Arraylist*/
arrayList.add(1);
arrayList.add(111);
System.out.println(arrayList); /* Output: [1, 111]*/
/*Block 3: Insert at given index in LinkedList*/
linkedList.add(1, 11);
linkedList.add(3, 1111);
System.out.println(linkedList); /* Output: [1, 11, 111, 1111]*/
/*Block 4: Insert at given index in Arraylist*/
arrayList.add(1, 11);
arrayList.add(3, 1111);
System.out.println(arrayList); /* Output: [1, 11, 111, 1111]*/
/*Block 5: Search by value in LinkedList(searching 111 value)*/
for(int i=0; i < linkedList.size(); i++) {
if(linkedList.get(i).equals(111)){
System.out.println("Value found at index: "+i); /* Output: Value found at index: 2*/
}
}
/*Block 6: Search by value in ArrayList(searching 111 value)*/
for(int i=0; i < arrayList.size(); i++) {
if(arrayList.get(i).equals(111)){
System.out.println("Value found at index: "+i); /* Output: Value found at index: 2*/
}
}
/*Block 7: Get value by index in LinkedList*/
Integer value = linkedList.get(2);
System.out.println(value); /* Output: 111*/
/*Block 8: Get value by index in ArrayList*/
value = arrayList.get(2);
System.out.println(value); /* Output: 111*/
/*Block 9: Remove by value in LinkedList(remove 111)*/
boolean isDeleted = linkedList.remove(new Integer(111));
System.out.println(isDeleted); /* Output: true*/
/*Block 10: Remove by value in ArrayList(remove 111)*/
isDeleted = arrayList.remove(new Integer(111));
System.out.println(isDeleted); /* Output: true*/
/*Block 11: Remove by index in LinkedList*/
value = linkedList.remove(2);
System.out.println("Removed value: "+value); /* Output: Removed value: 1111*/
/*Block 12: Remove by index in ArrayList*/
value = arrayList.get(2);
System.out.println("Removed value: "+value); /* Output: Removed value: 1111*/
}
}
Now, we will compare similar operations on ArrayList
and LinkedList
and see which is more efficient in terms of performance and why.
Insert Value at Last Index(Block 1 and 2)
When we insert a value at last index, ArrayList has to —
Check whether the underlying array is already full or not.
If the array is full then it copies the data from the old array to new array(size double than an old array),
Then add the value at the last index.
On the other hand, LinkedList simply adds that value at the tail of the underlying DoublyLinkedList.
Both have time complexity O(1), but due to the added steps of creating a new array in ArrayList its worstcase complexity reaches to order of N, that is why we prefer using LinkedList where multiple inserts are required.
Insert Value at Given Index(Block 3 and 4)
When we insert a value at a given index, ArrayList has to
Check whether the underlying array is already full or not.
If the array is full then it copies the data from the old array to a new array(size double than an old array).
After that, starting from the given index, shift values by one index to create space for the new value.
Then add the value at the given index.
On the other hand, LinkedList simply finds the index and adds that value at a given index by rearranging pointers of underlying DoublyLinkedList.
Both have time complexity O(N), but due to the added steps of creating a new array in ArrayList, and copying the existing values to the new index, we prefer using LinkedList where multiple inserts are required.
Search by Value(Block 5 and 6)
When we search any value in ArrayList or LinkedList, we have to iterate through all elements. This operation has O(N) time complexity. It looks like ArrayList and LinkedList both will have the same performance.
Here we need to notice that array(underlying data structure of ArrayList) stores all values in a continuous memory location, but DoublyLinkedList store each node at a random memory location. Iterating through continuous memory location is more performance efficient than random memory location, that is why we prefer ArrayList over LinkedList when searching by value.
Get Element by Index(Block 7 and 8)
When we get an element by Index then ArrayList is a clear winner.
ArrayList can give you any element in O(1) complexity as the array has random access property. You can access any index directly without iterating through the whole array.
LinkedList has a sequential access property. It needs to iterate through each element to reach a given index, so time complexity to get a value by index from LinkedList is O(N).
Remove by Value(Block 9 and 10)
It is similar to adding value at a given index. To remove an element by value in ArrayList and LinkedList we need to iterate through each element to reach that index and then remove that value. This operation is of O(N) complexity.
The difference is that to remove an element from LinkedList, we just need to modify pointers, which is O(1) complexity, but In ArrayList, we need to shift all elements after the index of the removed value to fill the gap created.
As shifting is costly operation then modifying pointers, so even after the same overall complexity O(N), we prefer LinkedList where more delete by value operation is required.
Remove by Index(Block 11 and 12)
To remove by index, ArrayList find that index using random access in O(1) complexity, but after removing the element, shifting the rest of the elements causes overall O(N) time complexity.
On the other hand, LinkedList takes O(N) time to find the index using sequential access, but to remove the element, we just need to modify pointers.
As shifting is costly operation than iterating, so LinkedList is more efficient if we want to delete element by index.
Summary
Let's summarize the whole discussion in the below table.
Operation  LinkedList time complexity  ArrayList time complexity  Preferred 
Insert at last index  O(1)  O(1) (If array copy operation is Considered then O(N)) 
LinkedList 
Insert at given index  O(N) 
O(N) 
LinkedList 
Search by value  O(N) 
O(N) 
ArrayList 
Get by index  O(N) 
O(1) 
ArrayList 
Remove by value  O(N) 
O(N) 
LinkedList 
Remove by index  O(N) 
O(N) 
LinkedList 
Thanks for reading...
If you enjoyed this article and want to learn more about Java Collections, check out this collection of tutorials and articles on all things Java Collections.
Opinions expressed by DZone contributors are their own.
Trending

Integrating AWS With Salesforce Using Terraform

Tactics and Strategies on Software Development: How To Reach Successful Software [Video]

RBAC With API Gateway and Open Policy Agent (OPA)

Seven Steps To Deploy Kedro Pipelines on Amazon EMR
Comments