Java: What is the difference between ArrayList and LinkedList?

ArrayList — backed by a dynamic array. LinkedList — backed by a doubly-linked list.

Analogy: ArrayList is like a numbered parking lot — you can drive straight to spot #50 (fast access by index). LinkedList is like a treasure hunt with clues — you have to follow the chain from the beginning to find the 50th item.

ArrayList (java.util.ArrayList):

• Backed by a resizable array (Object[]).
• O(1) random access by index — extremely fast.
• O(n) insert/delete in the middle — must shift elements.
• O(1) amortized append at the end.
• Better cache locality — elements are contiguous in memory.
• Uses extra memory only for unused capacity (typically 50% over size).
• Default initial capacity: 10, grows by 50% when full.

1ArrayList<String> list = new ArrayList<>();
2
3// Adding elements
4list.add("Alice");       // O(1) amortized — append at end
5list.add("Bob");
6list.add(1, "Charlie"); // O(n) — shifts Bob right
7
8// Accessing elements
9String first = list.get(0);     // O(1) — instant access
10String third = list.get(2);     // O(1) — instant access
11
12// Removing elements
13list.remove(1);  // O(n) — shifts elements to fill gap
14
15// Searching
16list.contains("Alice"); // O(n) — must scan
17list.indexOf("Bob");    // O(n) — must scan
18
19// Pre-sizing for performance
20ArrayList<Integer> big = new ArrayList<>(10000); // No resizing needed

LinkedList (java.util.LinkedList):

• Backed by a doubly-linked list (Node objects with prev/next pointers).
• O(1) insert/delete at head or tail — just update pointers.
• O(n) random access by index — must traverse from head or tail.
• Also implements Deque (double-ended queue) — can be used as a queue or stack.
• Uses more memory per element (each node stores prev + next pointers).
• Poor cache locality — nodes scattered across memory.

1LinkedList<String> linked = new LinkedList<>();
2
3// Adding elements
4linked.add("Alice");        // O(1) — append at tail
5linked.addFirst("Bob");     // O(1) — add at head
6linked.addLast("Charlie");  // O(1) — add at tail
7
8// Accessing elements
9String first = linked.get(0);   // O(n) — must traverse!
10String third = linked.get(2);   // O(n) — must traverse!
11
12// Removing elements
13linked.removeFirst(); // O(1)
14linked.removeLast();  // O(1)
15
16// Deque operations (stack/queue)
17linked.push("item");   // O(1) — push to head (stack)
18linked.pop();          // O(1) — pop from head (stack)
19linked.offer("item");  // O(1) — add to tail (queue)
20linked.poll();         // O(1) — remove from head (queue)

Complexity comparison:

• get(index): ArrayList O(1), LinkedList O(n)
• add(end): Both O(1) amortized
• add(middle): ArrayList O(n), LinkedList O(1) if you have the node, O(n) to find it
• remove(middle): ArrayList O(n), LinkedList O(1) if you have the node, O(n) to find it
• contains(): Both O(n)

When to use which:

• ArrayList — when you need fast random access (index-based retrieval).
• ArrayList — when most operations are reads or appends at the end.
• ArrayList — in almost all cases (better cache locality, less memory).
• LinkedList — when you need frequent insertions/deletions at both ends (queue/deque).
• LinkedList — rarely the right choice — in practice, ArrayList wins almost always.

Common mistake: Choosing LinkedList thinking it's faster for inserts. In reality, ArrayList is almost always faster due to CPU cache locality, and LinkedList uses more memory per element.