ArrayList vs LinkedList in Java — Performance and When to Use Each

ArrayList is backed by a dynamically resizing array, giving O(1) random access by index but O(n) insertion/removal in the middle (elements must shift). LinkedList is backed by doubly-linked nodes, giving O(1) insertion/removal at the ends but O(n) random access (it must walk the list from an end).

Common causes

• The two implementations trade off differently between contiguous-memory access speed and pointer-based flexible insertion, matching the classic array-vs-linked-list tradeoff at the data structure level

How to fix it

• Use ArrayList by default — most real-world access patterns involve iteration and indexed access, both of which ArrayList handles efficiently, and it has better cache locality
• Use LinkedList specifically when you're frequently inserting/removing at the beginning or in the middle via an iterator, and rarely need random indexed access
• In practice, ArrayDeque often outperforms LinkedList even for queue/stack use cases and should be considered as an alternative

Example

List<Integer> list = new ArrayList<>();
list.get(500);       // O(1)

List<Integer> linked = new LinkedList<>();
linked.get(500);     // O(n) — must traverse from the start

FAQ

Which one should be the default choice?

ArrayList, in almost all cases — it has better cache performance and handles both iteration and indexed access efficiently, which covers the vast majority of real-world usage.