Java ArrayList vs LinkedList — when to use each

ArrayList vs LinkedList

Both implement List. The difference is internal structure — choose based on your dominant operation pattern.

ArrayList — Backed by Array

import java.util.ArrayList;
import java.util.List;

List names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

System.out.println(names.get(1));   // Bob — O(1)
names.remove("Bob");                // shifts elements — O(n)
System.out.println(names.size());   // 2

LinkedList — Doubly Linked Nodes

import java.util.LinkedList;

LinkedList deque = new LinkedList<>();
deque.addFirst("first");   // O(1) insertion at head
deque.addLast("last");     // O(1) insertion at tail
deque.removeFirst();       // O(1) removal at head
System.out.println(deque.get(0)); // O(n) — must traverse

Immutable List (Java 9+)

List fixed = List.of("a", "b", "c");
// fixed.add("d"); → UnsupportedOperationException

Rule of thumb: Use ArrayList by default. Random access is O(1) and iteration is cache-friendly due to contiguous memory. Use LinkedList only when you predominantly insert or remove at the head/tail and never access by index.

In practice, LinkedList is rarely faster despite better asymptotic insertion performance — each node is a separate heap object, causing poor CPU cache utilization. Benchmark before switching. For stack or queue semantics, prefer ArrayDeque over LinkedList.

When you need both O(1) access and O(1) insertion at the front, consider ArrayDeque — it implements both Deque and Queue with better performance than LinkedList for most real workloads.