Within the expansive Java Collections Framework, the List interface finds its two most popular implementations in the form of ArrayList and LinkedList. While both serve as containers for ordered collections of elements, they come with inherently different data structures, leading to varied strengths and trade-offs. In this post, we will learn the differences between ArrayList and LinkedList in Java with examples.
Learn ArrayList: Java ArrayList Tutorial
Learn LinkedList: Java LinkedList Tutorial
ArrayList vs. LinkedList in Java
| Criteria | ArrayList | LinkedList |
|---|---|---|
| Underlying Data Structure | Dynamic array | Doubly-linked list |
| Implementation | Implements List interface only | Implements both List and Deque interfaces |
| Access Time | Fast random access (O(1) for get method) | Slower access (O(n) for get method in worst case) |
| Insertion/Deletion Time | Slow in middle (O(n) in worst case) | Faster at start and end, slower in the middle (O(n) in worst case) |
| Memory Overhead | Less, as it holds only data | More, as it holds data + two references (for previous and next node) |
| Resizable | Resizes automatically when it gets full | Doesn’t need resizing |
| Usage | Best for storing and accessing data | Best for data manipulation operations |
| Method to add at start | Requires shifting all elements | Directly adds at start |
Example: Difference Between ArrayList and LinkedList in Java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ArrayListVsLinkedListDemo {
public static void main(String[] args) {
// Create an ArrayList and add some elements
List<String> arrayList = new ArrayList<>();
arrayList.add("apple");
arrayList.add("banana");
arrayList.add("cherry");
arrayList.add("date");
System.out.println("ArrayList:");
arrayList.forEach(System.out::println);
// Create a LinkedList and add some elements
List<String> linkedList = new LinkedList<>();
linkedList.add("elephant");
linkedList.add("fox");
linkedList.add("grape");
linkedList.add("honeydew");
System.out.println("\nLinkedList:");
linkedList.forEach(System.out::println);
}
}
Output:
ArrayList: apple banana cherry date LinkedList: elephant fox grape honeydew
Explanation:
1. ArrayList: An ArrayList is a resizable array implementation of the List interface. It provides fast random access and fast iteration but slower insertion and removal at the middle.
2. LinkedList: A LinkedList is a doubly-linked list implementation of the List and Deque interfaces. It provides faster insertion and removal operations compared to ArrayList, especially when adding/removing at the beginning or middle of the list. However, it has slower access times for indexed operations.
3. In the given example, both arrayList and linkedList provide similar behaviors for the add and forEach methods. However, the internal workings and performance characteristics for these two types of lists differ, especially in larger datasets or more complex operations.