ArrayList vs LinkedList in Java - Java Tutorial Site

ArrayList vs LinkedList in Java

Java provides several data structures for handling collections of data efficiently, and among the most commonly used are ArrayList and LinkedList. Both are implementations of the List interface, but they have different underlying structures and performance characteristics. Choosing between them depends on the specific use case.

In this blog post, we will explore the differences between ArrayList and LinkedList, their internal workings, performance comparisons, and when to use each.

Understanding ArrayList and LinkedList

1. ArrayList Overview

An ArrayList is a resizable array implementation of the List interface. Internally, it uses a dynamic array that grows as needed when elements are added.

Characteristics of ArrayList:

Uses a dynamic array to store elements.
Provides fast random access (O(1)) due to index-based access.
Insertion and deletion in the middle of the list can be costly (O(n)) due to shifting of elements.
Expands automatically when capacity is exceeded.

Example of ArrayList Usage:

import java.util.*;

public class ArrayListExample {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Cherry");
        
        System.out.println(arrayList); // Output: [Apple, Banana, Cherry]
    }
}

2. LinkedList Overview

A LinkedList is a doubly linked list implementation of the List and Deque interfaces. Each element is stored in a node that contains references to both the previous and next node.

Characteristics of LinkedList:

Uses a doubly linked list internally.
Insertion and deletion are fast (O(1)) when modifying the list at the beginning or middle.
Random access is slow (O(n)) because traversal is needed to reach a specific index.
More memory overhead due to storage of node references.

Example of LinkedList Usage:

import java.util.*;

public class LinkedListExample {
    public static void main(String[] args) {
        List<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");
        
        System.out.println(linkedList); // Output: [Apple, Banana, Cherry]
    }
}

Performance Comparison: ArrayList vs LinkedList

Operation	ArrayList	LinkedList
Access (get(index))	O(1) - Fast	O(n) - Slow (traversal required)
Insertion at end (add(E))	O(1) (amortized)	O(1)
Insertion at beginning/middle	O(n) (shifting required)	O(1) (if reference is known)
Deletion at beginning/middle	O(n) (shifting required)	O(1) (if reference is known)
Deletion at end	O(1)	O(1)
Memory usage	Less (only stores data)	More (stores data + references)

When to Use ArrayList vs LinkedList?

Use ArrayList when:

You need fast random access to elements.
The list size is stable and frequent insertions/removals in the middle are not required.
Memory overhead is a concern (since ArrayList has lower overhead compared to LinkedList).

Use LinkedList when:

You need frequent insertions or deletions in the middle or at the beginning of the list.
You do not require fast random access.
You have large-sized lists with frequent modifications, despite the extra memory overhead.

Example: Performance Comparison

To demonstrate performance differences, let's compare the time taken for insertion at the beginning of ArrayList and LinkedList.

import java.util.*;

public class PerformanceTest {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        long startTime, endTime;
        
        // Testing ArrayList insertion at beginning
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            arrayList.add(0, i);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList insertion time: " + (endTime - startTime) + " ns");
        
        // Testing LinkedList insertion at beginning
        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(0, i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList insertion time: " + (endTime - startTime) + " ns");
    }
}

Expected Results:

LinkedList performs much better for insertions at the beginning.
ArrayList suffers due to shifting of elements.

Conclusion

Feature	ArrayList	LinkedList
Underlying Structure	Dynamic Array	Doubly Linked List
Fast Random Access	✅ Yes (O(1))	❌ No (O(n))
Insert/Delete at Beginning	❌ Slow (O(n))	✅ Fast (O(1))
Insert/Delete at Middle	❌ Slow (O(n))	✅ Fast (O(1))
Insert/Delete at End	✅ Fast (O(1))	✅ Fast (O(1))
Memory Usage	✅ Less	❌ More (extra references stored)

Both ArrayList and LinkedList have their own advantages and disadvantages. The choice between them depends on the use case:

If random access is required, use ArrayList.
If frequent insertions and deletions are required, use LinkedList.

Understanding their strengths and weaknesses allows developers to write more efficient and optimized Java programs.