What is the difference between ArrayList and LinkedList in Java?

The Java Collections Framework provides a comprehensive set of classes and interfaces to handle and manipulate collections of objects. Two commonly used classes for storing and managing dynamic lists of elements are ArrayList and LinkedList. While both serve the same purpose, there are key differences in their internal implementations and performance characteristics. In the below sections, we’ll discuss the internal implementations, performance characteristics, and example usage of ArrayList and LinkedList in Java. Additionally, we’ll explore considerations for choosing between these two classes based on specific application requirements.

`ArrayList`

It is a part of the Java Collections Framework and is implemented as a dynamic array. This means it is backed by an array that can dynamically resize itself to accommodate a varying number of elements.
It provides constant-time random access to elements, making it efficient to retrieve elements by index. It implements the List interface, allowing access to elements based on their index.
It allocates a contiguous block of memory to store elements.
It is generally faster than LinkedList for scenarios where random access and iteration are frequent operations.
Adding or removing elements from the middle of the list can be slower due to the need to shift elements to maintain contiguous memory.

`LinkedList`

It is implemented as a doubly linked list. Each element in a LinkedList is represented by a node that contains data and two pointers. One pointer stores the reference to the next node, and the other stores the reference to the previous node.
It does not provide random access to elements; instead, we have to iterate the linked list sequentially to access an element.
It does not use a contiguous block of memory. Instead, it uses nodes connected by pointers. It has a higher memory overhead due to the additional memory required for storing pointers in each node.
It is slower than ArrayList for random access and iteration.
Insertion and deletion operations within the LinkedList are more efficient than in ArrayList because they involve updating pointers, not shifting elements.

import java.util.ArrayList;
import java.util.List;
class Main {
    public static void main(String[] args) {
        // Creating an ArrayList of integers
        List<Integer> numbers = new ArrayList<>();
        // Adding elements to the ArrayList
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        // Accessing elements by index (random access)
        int secondElement = numbers.get(1);
        System.out.println("Second element: " + secondElement);
        // Iterating through the ArrayList
        System.out.println("Elements in ArrayList:");
        for (int num : numbers) {
            System.out.println(num);
        }
    }
}

Implementation of ArrayList

Code explanation

Line 7: We declare a variable named numbers of type List<Integer>, which is an interface for a list that holds integers. It is initialized with an ArrayList instance, creating an empty list of integers.
Lines 10–12: We add integer elements (10, 20, and 30) to the numbers list using the add method of the ArrayList class.
Line 15: We retrieve the element at index 1 (the second element since indexing starts from 0) from the numbers list using the get method and assigns it to the variable secondElement.
Lines 20–22: The for loop iterates through each element (num) in the numbers list, printing each element on a new line using System.out.println.

Implementation of `LinkedList`

Below is an example demonstrating the use of LinkedList in Java.

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        // Creating a LinkedList of strings
        LinkedList<String> colors = new LinkedList<>();
        // Adding elements to the LinkedList
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        // Inserting an element in the middle of the LinkedList
        colors.add(1, "Yellow");
        System.out.println("Updated LinkedList: " + colors);
        // Accessing elements sequentially
        System.out.println("Elements in LinkedList:");
        for (String color : colors) {
            System.out.println(color);
        }
    }
}

Implementation of Linkedlist

Code explanation

Line 6: We declare a variable named colors of type LinkedList<String>, which is a linked list that holds strings. It initializes an empty linked list of strings.
Lines 9–11: We add string elements ("Red", "Green", and "Blue") to the colors linked list using the add method.
Line 14: We insert the string "Yellow" at index 1 in the colors linked list.
Lines 19–21: The for loop iterates through each element (color) in the colors list, printing each element on a new line using System.out.println.

Choosing between `ArrayList` and `LinkedList`

The choice between ArrayList and LinkedList depends on the specific requirements of your application. Here are some considerations:

Use ArrayList when:

Random access and iteration are frequent operations.
The list size remains relatively constant, reducing the need for resizing.

Use LinkedList when:

Frequent insertion or deletion operations are anticipated, especially in the middle of the list.
Memory overhead is not a critical concern.

Example scenario

Imagine you’re developing a music playlist application. Each song in the playlist is represented by an object of type Song, which contains information like the song’s title, artist, and duration.

Using ArrayList:
1. You might use an ArrayList<Song> to store the playlist. This is because ArrayList provides fast access to elements by index. In a playlist, users often want to skip to the next or previous song directly, which ArrayList supports efficiently.
Using LinkedList:
1. You might use a LinkedList<Song> to implement a queue for playing songs. When a song finishes playing, the next song in the queue should start. LinkedList is suitable for this because it offers efficient insertion and removal at both ends of the list (front and back).

In this scenario, use the following:

ArrayList for the playlist where direct access to songs by index is important (e.g., for shuffling or selecting a specific song).
LinkedList for the song queue where adding songs to the end and removing songs from the front are frequent operations (e.g., for playing songs sequentially).

Conclusion

In conclusion, both ArrayList and LinkedList have their strengths and weaknesses. ArrayList is ideal for scenarios where random access and iteration are frequent, while LinkedList excels in situations where insertion and deletion operations are more prevalent. Understanding the differences between these two classes is crucial for making informed decisions when designing and implementing data structures in Java. The choice between ArrayList and LinkedList should be based on the specific requirements and performance considerations of your application.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is the difference between ArrayList and LinkedList in Java?

ArrayList

LinkedList

Implementation of ArrayList

Code explanation

Implementation of LinkedList

Code explanation

Choosing between ArrayList and LinkedList

Example scenario

Conclusion

`ArrayList`

`LinkedList`

Implementation of `ArrayList`

Implementation of `LinkedList`

Choosing between `ArrayList` and `LinkedList`