In Java, both ArrayList and LinkedList are popular List implementations, providing a dynamic array that grows and shrinks as needed. Both classes implement the List interface, but they differ significantly in their underlying data structures and performance characteristics.
Let’s explore the differences between these two classes, their internal mechanisms, and the key factors that influence their performance.
ArrayList
The ArrayList class is part of Java’s java.util package. It uses a dynamic array to store elements. The main feature of ArrayList is that it provides constant-time access (O(1)) to elements by their index, making it ideal for scenarios where fast retrieval is important.
How ArrayList Works
When you add elements to an ArrayList, the array grows dynamically to accommodate new elements. However, when the array reaches its capacity, it creates a new, larger array and copies the elements to the new array, which can be costly in terms of time.
Advantages of ArrayList
- Fast access to elements by index (O(1))
- Efficient memory usage for a large number of elements
- Good performance for search and retrieval operations
Disadvantages of ArrayList
- Slow insertion or deletion of elements, especially in the middle (O(n))
- Resizing the array can be costly
Code Example: ArrayList
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
// Creating an ArrayList
ArrayList list = new ArrayList<>();
// Adding elements
list.add("Apple");
list.add("Banana");
list.add("Cherry");
// Accessing elements
System.out.println("Element at index 1: " + list.get(1)); // Banana
// Removing an element
list.remove(0); // Removes "Apple"
// Displaying the list
System.out.println("ArrayList: " + list);
}
}
LinkedList
In contrast, LinkedList is another List implementation in Java, but it uses a doubly linked list to store elements. Each element in a LinkedList is stored in a node, which contains the data and references (or links) to the previous and next nodes.
How LinkedList Works
Unlike ArrayList, LinkedList doesn’t use a contiguous block of memory. Each element points to the next one, allowing for efficient insertions and deletions at both ends. However, accessing an element requires traversing the list, which makes index-based access slower (O(n)) compared to ArrayList.
Advantages of LinkedList
- Efficient insertions and deletions (O(1)) at both ends
- Better performance for frequent additions or removals of elements
- Dynamic memory allocation (no resizing needed)
Disadvantages of LinkedList
- Slower access to elements by index (O(n))
- Increased memory usage due to storing additional pointers for each element
Code Example: LinkedList
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// Creating a LinkedList
LinkedList list = new LinkedList<>();
// Adding elements
list.add("Apple");
list.add("Banana");
list.add("Cherry");
// Accessing elements
System.out.println("Element at index 1: " + list.get(1)); // Banana
// Removing an element
list.remove(0); // Removes "Apple"
// Displaying the list
System.out.println("LinkedList: " + list);
}
}
Performance Comparison
Here’s a quick comparison of the performance characteristics of both ArrayList and LinkedList:
| Operation | ArrayList | LinkedList |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insertion/Deletion (End) | O(1) | O(1) |
| Insertion/Deletion (Middle) | O(n) | O(n) |
| Memory Overhead | Low | High (due to node structure) |
When to Use ArrayList or LinkedList
– Use ArrayList when you need fast random access to elements and your application will involve a lot of lookups and not many insertions or deletions. ArrayList is ideal for scenarios where the number of elements is known beforehand or doesn’t change often.
– Use LinkedList when you need efficient insertions and deletions at both ends or in the middle of the list. It’s a good choice when the list size changes frequently, and the application doesn’t require frequent access by index.
