Lists in Java

ArrayList vs LinkedList in Java

In Java, ArrayList and LinkedList are two commonly used classes that implement the List interface from the Java Collections Framework. While they provide similar APIs, they differ significantly in performance and internal implementation.

🔹 1. ArrayList
✅ Characteristics:
  • Backed by a dynamic array
  • Fast random access (O(1) time complexity for get() and set())
  • Slower insertions/removals in the middle or beginning (due to shifting elements)
📌 Example:

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        System.out.println(list.get(1));  // Output: Banana
    }
}
🚀 Performance:
Operation Time Complexity
get(index) O(1)
add(elem) O(1) amortized
remove() O(n) (worst case, due to shifting)
contains() O(n)
🔹 2. LinkedList
✅ Characteristics:
  • Backed by a doubly linked list
  • Better performance for frequent insertions/deletions anywhere in the list
  • Slower random access (O(n) for get() and set())
📌 Example:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("Apple");
        list.addFirst("Banana");
        list.addLast("Cherry");
        System.out.println(list.get(1));  // Output: Apple
    }
}
🚀 Performance:
Operation Time Complexity
get(index) O(n)
add(elem) O(1)
remove() O(1) (if using iterator or first/last)
contains() O(n)
🔍 When to Use Which?
Use Case Choose
Frequent random access ✅ ArrayList
Frequent insertions/removals (not at end) ✅ LinkedList
Minimal memory overhead ✅ ArrayList
Queue or Stack implementations ✅ LinkedList (supports addFirst(), removeFirst(), etc.)
✅ Summary
Feature ArrayList LinkedList
Underlying Structure Dynamic Array Doubly Linked List
Access Time Fast (O(1)) Slow (O(n))
Insert/Delete (Mid) Slow (O(n)) Fast (O(1) with iterator)
Memory Usage Less More (due to node pointers)
Thread-Safety ❌ (use Collections.synchronizedList()) ❌