Difference between ArrayList and LinkedList in Java

This post will discuss differences between the ArrayList and LinkedList in Java.

1. Overview of `ArrayList`

An ArrayList is the implementation of the List interface and is one of the most commonly used class in Java. It uses a dynamically resizable array as its underlying data structure to store its elements. It preserves the order of the elements in the list, and allows null and duplicate values in the list. However, it is not synchronized by default, and is not suitable for multithreading environments where thread-safety is needed. Here is an example of how to create and use an ArrayList in Java:

import java.util.ArrayList;

import java.util.List;

class Main

{

public static void main(String[] args)

{

// Create an ArrayList object

List<String> list = new ArrayList<>();

// Add some elements to the list

list.add("Java");

list.add("Python");

list.add("C++");

// Print the list

System.out.println(list); // [Java, Python, C++]

// // Add a new element at a specific index

list.add(1, "Ruby");

// Replace an existing element with a new element

list.set(2, "JavaScript");

// Remove an element from a specific index

list.remove(3);

// Print the updated list

System.out.println(list); // [Java, Ruby, JavaScript]

}

Download Run Code

2. Overview of `LinkedList`

LinkedList is another class that implements the List interface and uses a doubly linked list as its underlying data structure to store elements. Like ArrayList, a LinkedList is not synchronized by default, preserves the order of the elements, and allows null values. However, unlike ArrayList, LinkedList does not use an array internally, but rather uses nodes that have references to the previous and next nodes in the list. This makes LinkedList more suitable for frequent insertion and deletion operations, as it does not require shifting or copying of elements in memory. Here is an example of how to create and use a LinkedList in Java:

import java.util.LinkedList;

import java.util.List;

class Main

{

public static void main(String[] args)

{

// Create a LinkedList object

List<String> list = new LinkedList<String>();

// Add some elements to the list

list.add("Java");

list.add("Python");

list.add("C++");

// Print the list

System.out.println(list); // [Java, Python, C++]

// Add a new element at a specific index

list.add(1, "Ruby");

// Replace an existing element with a new element

list.set(2, "JavaScript");

// Remove an element from a specific index

list.remove(3);

// Print the updated list

System.out.println(list); // [Java, Ruby, JavaScript]

}

Download Run Code

3. Differences between `ArrayList` and `LinkedList`

Both ArrayList and LinkedList are two different implementations of the List interface. Here are some of the main differences between ArrayList and LinkedList in Java:

1. Underlying Data Structure

ArrayList uses a dynamically resizable array as its underlying data structure, while LinkedList uses a doubly linked list as its underlying data structure. This means that ArrayList allows fast random access of elements by their index, but slow insertion and deletion of elements. While LinkedList allows fast insertion and deletion of elements, but slow random access of elements by their index.

2. Capacity

An ArrayList capacity at least as large as the list size, and it grows automatically as more elements are added to it. Its default capacity is just 10 elements. Since resizing degrades performance, it is always better to specify the initial capacity of the ArrayList during initialization itself. On the contrary, a LinkedList capacity is exactly equal to the list size, and we cannot specify the capacity during the list initialization.

3. Memory Overhead

LinkedList comes up with memory overhead since every element is a node object which stores references to the next and previous nodes. But since the memory needed for each node might not be contiguous, a LinkedList won’t result in any major performance issues. On the contrary, an ArrayList needs a contiguous block of memory in a heap for allocating the dynamic array. This might be space efficient but sometimes costs performance issues when the Garbage Collector ends up doing some work to free up a necessary contiguous block of memory in a heap. Also, an ArrayList may also waste some memory space if it is not fully utilized, since it has an initial capacity that may be larger than the actual number of elements.

4. Caching

Traversing through the elements of an ArrayList is always faster than a LinkedList. This is because of Sequential locality or locality of reference where hardware will cache contiguous memory blocks for faster read access.

5. Performance

We can measure the performance based on the following parameters:

1. Insertion at the end

The add(E element) operation for an ArrayList runs in amortized O(1) time, but is O(n) in the worst case. The worst-case happens when the maximum capacity of ArrayList is reached, and elements from the old array are copied to the new array, which is double the size of the old array. For a LinkedList, add is a O(1) time operation since the specified element is appended at the end of the list and pointer to the last node is maintained by LinkedList class.

2. Insertion at the specified index

The add(int index, E element) operation at the specified index is O(n) time operation for an ArrayList as it requires shifting of all elements past the insertion point for accommodating the new element. For a LinkedList, insertion at the specified index costs O(n) as it has to traverse the list from the beginning or the end to get to the specified index.

3. Deletion

For both ArrayList and LinkedList, the remove(int index) operation takes O(n) time. For an ArrayList, it requires shifting of all latter elements, and for the LinkedList, it has to traverse the list from the beginning or the end, whichever is closer to the specified index.

4. Access

An ArrayList allows fast random read access, so get(int index) operation takes only O(1) time. For a LinkedList, get operation takes O(n) time since it has to traverse the list from the beginning or the end, whichever is closer.

4. What to use and when?

Here are some general recommendations on choosing between ArrayList and LinkedList in Java:

If you need a list that can store any type of objects of an unknown or variable size, and allows fast access of elements by their index, we should use ArrayList.
If you need a list that can store any type of objects of an unknown or variable size, and allows fast insertion and deletion of elements at the beginning or the end of the list, we should use LinkedList.

In general, an ArrayList is more suitable for scenarios where frequent read operations are required, but infrequent write operations are performed. For example, if we need to store and access a large number of elements by their index, but rarely add or remove elements from the list. A LinkedList is more suitable for scenarios where frequent write operations are required, but infrequent read operations are performed. For example, if we need to add or remove elements from the beginning or end of the list frequently, but rarely access elements by their index.

That’s all about the differences between ArrayList and LinkedList in Java.