ArrayList vs LinkedList

JavaMidjava

The Question

What is the difference between ArrayList and LinkedList?

What a Strong Answer Covers

• ArrayList = dynamic array O(1) get
• LinkedList = doubly linked list O(1) add/remove at ends
• ArrayList better for random access
• LinkedList better for frequent insertions/deletions
• LinkedList implements Deque

Senior-Level Answer

ArrayList and LinkedList are both implementations of the List interface in Java, but they are backed by fundamentally different data structures.

ArrayList is backed by a dynamically resizing array. Elements are stored sequentially in contiguous memory, giving O(1) random access. When the array reaches capacity, ArrayList allocates a new array approximately 1.5x the size and copies all elements, making add() amortized O(1) at the end. Insertion or removal at arbitrary positions is O(n) because elements must be shifted.

LinkedList is a doubly-linked list. Each element is wrapped in a Node object with pointers to the previous and next nodes. Insertion and removal at head or tail is O(1). Accessing an element by index is O(n) because you must traverse from the head or tail. LinkedList also implements the Deque interface.

The textbook analysis suggests LinkedList is better for frequent insertions in the middle. In practice, ArrayList benefits enormously from cache locality — contiguous memory enables CPU prefetching, and sequential access is extremely fast. LinkedList nodes are scattered across the heap, causing frequent cache misses. The Node object overhead (24+ bytes per node for object header and two pointers) also adds up. Benchmarks consistently show ArrayList outperforms LinkedList for most real-world workloads.

LinkedList is genuinely appropriate when used strictly as a queue or deque, or when removing elements during iteration with ListIterator.remove(). However, even for queue operations, ArrayDeque is often better due to contiguous memory.

In practice: default to ArrayList. Use LinkedList only when you specifically need Deque operations and have measured that it performs better.

Key Differences

What Separates a 2/3 from a 3/3

Common Mistakes

• Claiming LinkedList is better for frequent insertions without noting that finding the insertion point is O(n)
• Ignoring cache locality — the single most important practical factor
• Not mentioning that LinkedList implements Deque
• Forgetting that ArrayList resize is amortized O(1), not O(n) for every add
• Recommending LinkedList for queue operations without mentioning ArrayDeque

Follow-Up Questions

• Why does ArrayList typically outperform LinkedList even for insertion-heavy workloads? — Cache locality — contiguous memory allows CPU prefetching.
• What happens when an ArrayList needs to grow? — Allocates a new array ~1.5x the current size and copies elements. Amortized O(1).
• When would you use ArrayDeque instead of LinkedList? — For queue/stack operations. ArrayDeque has better cache performance and lower memory overhead.
• How does the RandomAccess marker interface relate to ArrayList? — Signals that index-based access is O(1). Algorithms can check this to choose optimal strategies.

Related Questions

• JVM vs JRE vs JDK
• Java Platform Independence
• How JVM Works
• Main Features of Java
• public static void main