Difference between ArrayList and LinkedList in Java

Last Updated On Aug 24, 2024 by Mukesh Kumar

LinkedList and ArrayList are two popular implementations of the List interface in Java. They both allow you to store a sequence of elements, but they have different performance characteristics and use cases due to their underlying data structures. Here's a comparison between the two

Underlying Data Structure

ArrayList: Internally uses a dynamic array to store elements. This means elements are stored in contiguous memory locations.
LinkedList: Internally uses a doubly linked list to store elements. Each element (node) contains a reference to both the previous and the next element in the list.

Let us compare these two data structures as far as the running times are concerned. Let us consider below java program which will show running time when elements are added in both the data structure.


package com.example;

import java.util.ArrayList;
import java.util.LinkedList;

public class Test {

	public static void main(String[] args) {
		ArrayList list = new ArrayList<>();
		long now = System.currentTimeMillis();
		for (int i = 0; i < 500000; ++i) {
			list.add(0, i);
		}
		System.out.println("Time taken by ArrayList " + (System.currentTimeMillis() - now));

		LinkedList linkedList = new LinkedList<>();
		now = System.currentTimeMillis();
		for (int i = 0; i < 500000; ++i) {
			linkedList.addFirst(i);
		}
		System.out.println("Time taken by LinkedList " + (System.currentTimeMillis() - now));

	}

}

In this example we have an ArrayList and a LinkedList and we would like to insert half a million items to the beginning of the data structures.So we inserted half a million items to the beginning of the ArrayList.So, with index zero, the first item naturally has the index 0.Basically, we are going to insert all the items at the beginning of the ArrayList data structure.After that We will measure the time it takes.First, we get the current system time in milliseconds.After the add operation, we print out the difference between the current system time and the time when we started (now).This way, we measure how long it takes for Java to insert half a million items into an ArrayList and then, we perform the same operation with a LinkedList.

We measure the time taken as we insert half a million items at the beginning of the linked list.Intuitively, linked lists should be faster because when manipulating the first item we only need to update the references however, when manipulating the first item of an ArrayList, we have to shift all the existing items to make room for the new one.So, if we run the application LinkedList will naturally be much faster. Run the above program and see the output of the program execution.

Output:

Time taken by ArrayList 9455
Time taken by LinkedList 11

As expected, LinkedList are extremely fast as you can see, manipulating the first item in an ArrayList is approximately a thousand times slower than in a LinkedList.It takes about 11 milliseconds for the LinkedList, while the ArrayList takes approximately 11,000 milliseconds.

Now insert the items at the end of the ArrayList and observe the program execution.

Updated code for this is given below


package com.example;

import java.util.ArrayList;
import java.util.LinkedList;

public class Test {

	public static void main(String[] args) {
		ArrayList list = new ArrayList<>();
		long now = System.currentTimeMillis();
		for (int i = 0; i < 500000; ++i) {
			//list.add(0, i);
			list.add(i);
		}
		System.out.println("Time taken by ArrayList " + (System.currentTimeMillis() - now));

		LinkedList linkedList = new LinkedList<>();
		now = System.currentTimeMillis();
		for (int i = 0; i < 500000; ++i) {
			linkedList.addFirst(i);
		}
		System.out.println("Time taken by LinkedList " + (System.currentTimeMillis() - now));

	}

}

Output:

Time taken by ArrayList 12
Time taken by LinkedList 11

Consider the output of above program, the execution time for ArrayList and LinkedList will be approximately the same. This is because appending elements to the end of an ArrayList is quite fast. We simply need to add the items, and appending elements to the end of a LinkedList is also very efficient

Performance difference between ArrayList and LinkedList for various operations

1) Search (Access Time):

ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Reason : ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list.ArrayList Provides constant-time performance (O(1)) for accessing elements by index because it directly accesses the array On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element. linkedList Provides linear-time performance (O(n)) for accessing elements by index because it needs to traverse the list from the beginning or the end to reach the specified index.

2) Deletion

LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in while removing first element and O(1) While removing last element. So LinkedList element deletion is faster compared to ArrayList.

Reason : Each element in a LinkedList maintains two pointers (addresses) that point to both neighboring elements in the list. Hence, removal only requires changing the pointer locations in the two neighboring nodes (elements) of the node being removed. In contrast, in an ArrayList, all the elements need to be shifted to fill the space created by the removed element.

3) Insertion Performance

Adding elements at the end of ArrayList typically gives 0(1) performance. Inserting elements in the middle or beginning of ArrayList requires shifting of elements, so it is O(n).

Inserting elements in LinkedList gives O(1) performance if the iterator is already at the correct position. For example adding or at the beginning or end. However, finding the position itself takes O(n) time if you need to traverse the list, making the overall operation O(n).

Memory Usage

ArrayList: Consumes less memory because it stores only the data and the array's internal structure. However, it may allocate extra space to accommodate growth (e.g., when the array is resized).

LinkedList: Consumes more memory because each element requires additional space for storing references to the next and previous elements.

Use Cases

ArrayList:

Best for scenarios where you need fast random access to elements.
It is suitable for lists where additions and deletions occur mostly at the end.

LinkedList:

Best for scenarios where there are frequent insertions and deletions in the middle or at the beginning of the list.
Ideal when you need to frequently iterate over the list and modify it at various points.

When to use LinkedList and when to use ArrayList?

Choose ArrayList if you need efficient random access to elements and the list is primarily used for reading, with occasional additions or deletions at the end.
Choose LinkedList if you need frequent insertions and deletions, especially at the beginning or middle of the list, and random access is not a priority.