What Are the Key Differences Between ArrayList and LinkedList in Java?

Introduction to Java Lists

In Java, the List interface is a part of the java.util package and provides a collection of elements in a sequential manner. There are two primary implementations of the List interface in Java: ArrayList and LinkedList. Both of these implementations serve the same purpose of storing a list of elements, but they differ significantly in terms of their internal data structures, performance, and use cases.

Internal Structure: ArrayList vs LinkedList

The main difference between ArrayList and LinkedList lies in their internal structure:

• ArrayList: It is backed by a dynamic array, which means it stores elements in contiguous memory locations. This allows for fast random access (i.e., accessing elements by index) but slower insertion and deletion operations, especially when the size of the list grows and requires resizing.
• LinkedList: It is backed by a doubly-linked list, where each element is stored in a node that holds references to the next and previous elements. This allows for efficient insertion and deletion at both ends of the list, but accessing elements by index is slower compared to an ArrayList due to the need to traverse the list.

Performance Comparison

Performance is one of the most critical factors when choosing between ArrayList and LinkedList. The choice depends on the specific requirements of the application:

1. Access Time

For ArrayList, accessing an element by index is very fast (constant time operation O(1)) due to its array-based implementation. However, for LinkedList, accessing an element by index requires traversing the list from the start or end, making it slower (linear time operation O(n)).

2. Insertion and Deletion

In terms of insertion and deletion, LinkedList is more efficient, especially when performing operations at the beginning or middle of the list. Insertion or removal at the head or tail of a LinkedList is an O(1) operation. On the other hand, an ArrayList has an O(n) time complexity for inserting or deleting elements in the middle, as it requires shifting elements.

3. Memory Usage

Since LinkedList uses nodes with two references (next and previous), it consumes more memory compared to ArrayList, which only stores the elements in an array. However, the extra memory overhead of LinkedList is often outweighed by its advantages in insertion and deletion performance.

4. Resizing

ArrayList needs to be resized when the capacity is exceeded, which is a costly operation, as it requires allocating a new, larger array and copying all the elements. On the other hand, LinkedList dynamically adjusts as elements are added or removed without needing to reallocate or copy elements.

Code Examples

ArrayList Example:

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        System.out.println("ArrayList Elements: " + list);

        // Accessing an element by index
        System.out.println("Element at index 1: " + list.get(1));

        // Removing an element
        list.remove("Banana");
        System.out.println("ArrayList after removal: " + list);
    }
}
        

LinkedList Example:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        System.out.println("LinkedList Elements: " + list);

        // Accessing an element by index
        System.out.println("Element at index 1: " + list.get(1));

        // Removing an element
        list.remove("Banana");
        System.out.println("LinkedList after removal: " + list);
    }
}
        

When to Use ArrayList vs LinkedList

Choosing between ArrayList and LinkedList depends on the specific use case:

• Use ArrayList: When you need fast random access to elements and the majority of operations are accessing elements by index or iterating through the list. Example: Storing and accessing a list of items in a UI or a list of records in a database.
• Use LinkedList: When you need frequent insertions or deletions, especially at the beginning or middle of the list. Example: Implementing a queue, stack, or a list where elements are dynamically added or removed.