Java: What is the difference between ArrayList and LinkedList?

ArrayList — array-based, fast random access. LinkedList — linked-list-based, fast insert/delete at ends.

Analogy: ArrayList is like a numbered apartment building — go straight to apartment #50. LinkedList is like a chain of rooms — you must walk through each room to reach the 50th one.

ArrayList:

• Backed by a resizable array (Object[]).
• O(1) random access by index.
• O(n) insert/delete in middle — shifts elements.
• Better cache locality — elements are contiguous.
• Default capacity: 10, grows by 50%.

1ArrayList<String> list = new ArrayList<>();
2
3list.add("Alice");       // O(1) — append
4list.add("Bob");
5list.add(1, "Charlie"); // O(n) — shifts elements
6
7String first = list.get(0);     // O(1) — instant
8String third = list.get(2);     // O(1) — instant
9
10list.remove(1);  // O(n) — shifts elements
11
12// Pre-size for performance:
13ArrayList<Integer> big = new ArrayList<>(10000);

LinkedList:

• Backed by a doubly-linked list (Node objects).
• O(1) insert/delete at head or tail.
• O(n) random access by index — must traverse.
• Also implements Deque (queue/stack operations).
• More memory per element (prev/next pointers).

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

Complexity comparison:

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

When to use:

• ArrayList — fast random access, reads, appends at end (99% of cases).
• LinkedList — frequent insertions/deletions at both ends (queue/deque).

Common mistake: Choosing LinkedList for frequent index access — it's actually slower than ArrayList due to poor cache locality.