Java: What is the difference between ArrayList and LinkedList?

ArrayList — array-backed, fast access. LinkedList — node-backed, fast insert/delete at ends.

Analogy: ArrayList = numbered parking lot (drive to spot #50). LinkedList = treasure hunt (follow chain to 50th item).

ArrayList:

• Backed by resizable array.
• O(1) random access.
• O(n) insert/delete in middle.
• Better cache locality.

1ArrayList<String> list = new ArrayList<>();
2list.add("Alice");       // O(1)
3list.add(1, "Bob");     // O(n)
4String s = list.get(2); // O(1)
5list.remove(0);         // O(n)
6
7// Pre-size:
8ArrayList<Integer> big = new ArrayList<>(10000);
9
10// Search:
11list.contains("Alice"); // O(n)
12list.indexOf("Bob");    // O(n)

LinkedList:

• Backed by doubly-linked list.
• O(1) insert/delete at head/tail.
• O(n) random access.
• Implements Deque.

1LinkedList<String> linked = new LinkedList<>();
2linked.add("Alice");        // O(1) tail
3linked.addFirst("Bob");     // O(1) head
4String s = linked.get(2);   // O(n)
5linked.removeFirst();       // O(1)
6linked.removeLast();        // O(1)
7
8// Deque:
9linked.push("item");  // O(1)
10linked.pop();         // O(1)
11linked.offer("item"); // O(1)
12linked.poll();        // O(1)

Comparison:

• get(i): ArrayList O(1), LinkedList O(n)
• add(end): Both O(1)
• add(middle): ArrayList O(n), LinkedList O(1) if node known
• remove(middle): ArrayList O(n), LinkedList O(1) if node known

When to use:

• ArrayList — random access, reads, appends (99% of cases).
• LinkedList — queue/deque, frequent head/tail operations.

Common mistake: Choosing LinkedList for index access — ArrayList is almost always faster.