ArrayList vs LinkedList

ArrayList keeps its elements in a resizable array: fast to read by position, slow to insert in the middle.

🔎 Unravel this example Prerequisites (1)

Learn these first

At a glance

Mental model

ArrayList is a row of numbered seats: jump straight to seat 40, but adding someone at seat 2 makes everybody shuffle one seat.

What happens, in order

1list.get(i) is O(1) in ArrayList and O(n) in LinkedListadd(x) at the end is O(1) amortised in an ArrayList; add(0, x) and remove(0) shift everything (O(n)).
2When the backing array is full, ArrayList allocates a bigger one (about 1.5 times) and copiesIf you know the size, new ArrayList<>(10_000) avoids the repeated copying.
3list.subList(from, to) is a view, not a copy: changing the list structurally while using the view throws ConcurrentModificationException
4List.of(...) and Arrays.asList(...) are fixed-size or immutable lists; add on them throws UnsupportedOperationException

Remember

In practice LinkedList is almost never faster: each element costs a 24-byte node, and jumping between nodes defeats the CPU cache
remove(int index) versus remove(Object) on a List<Integer> is a classic mix-up
ArrayList has Object[] elementData and a size

Watch out

Choosing LinkedList "for fast inserts" and then indexing into it in a loop (O(n²))Modifying a list while iterating with for-eachCalling add on Arrays.asList or List.of

Example (highlighted lines explain it)

import java.util.*;public class Lists {  static List<Integer> squares(int n) {    List<Integer> out = new ArrayList<>(n);    for (int i = 0; i < n; i++) out.add(i * i);    return out;  }  static Deque<String> history() { LinkedList<String> h = new LinkedList<>(); h.addFirst("home"); return h; }}

line 4 uses ArrayList, the core of ArrayList vs LinkedList
line 8 uses LinkedList, the core of ArrayList vs LinkedList

Read the full explanation (about 1 min)

ArrayList keeps its elements in a resizable array: fast to read by position, slow to insert in the middle. LinkedList chains nodes: fast at the ends, slow to find anything. Use ArrayList unless you have measured otherwise.

A mental model

ArrayList is a row of numbered seats: jump straight to seat 40, but adding someone at seat 2 makes everybody shuffle one seat. LinkedList is a conga line holding hands: easy to join at the front, but to reach the 40th person you walk past 39.

How it works

list.get(i) is O(1) in ArrayList and O(n) in LinkedList. add(x) at the end is O(1) amortised in an ArrayList; add(0, x) and remove(0) shift everything (O(n)).

When the backing array is full, ArrayList allocates a bigger one (about 1.5 times) and copies. If you know the size, new ArrayList<>(10_000) avoids the repeated copying.

list.subList(from, to) is a view, not a copy: changing the list structurally while using the view throws ConcurrentModificationException.

List.of(...) and Arrays.asList(...) are fixed-size or immutable lists; add on them throws UnsupportedOperationException.

Going deeper

In practice LinkedList is almost never faster: each element costs a 24-byte node, and jumping between nodes defeats the CPU cache. For queues and stacks, ArrayDeque is the better choice.

remove(int index) versus remove(Object) on a List<Integer> is a classic mix-up. Removing while iterating needs an Iterator or removeIf.

Both are not thread safe. Share them only after construction, or use CopyOnWriteArrayList, or guard access.

Under the hood

ArrayList has Object[] elementData and a size. Growth is newCapacity = old + (old >> 1). LinkedList holds first and last references to nodes with item, next, prev, and also implements Deque.

Common mistakes

Choosing LinkedList "for fast inserts" and then indexing into it in a loop (O(n²)).
Modifying a list while iterating with for-each.
Calling add on Arrays.asList or List.of.

How Unravel recognises it

When you paste code, Unravel looks for these signs of arraylist vs linkedlist. Spotting them yourself is a good habit when you read unfamiliar code:

Method calls: ensureCapacity() trimToSize() subList() addFirst() removeFirst() getFirst()
Created with new: ArrayList LinkedList

Part of a learning path

Collections in depth · next: How HashMap works

Related concepts

Collections: List, Set, MapJava language Queue, Deque and StackJava language ConcurrentModificationExceptionErrors and logging

Frequently asked questions

What is ArrayList vs LinkedList?

What are the most common mistakes with ArrayList vs LinkedList?

Choosing LinkedList "for fast inserts" and then indexing into it in a loop (O(n²)). Modifying a list while iterating with for-each. Calling add on Arrays.asList or List.of.

How can I see ArrayList vs LinkedList in real code?

Paste your own Java into Unravel and it will point out where arraylist vs linkedlist appears, explain how it works at the detail level you choose, and draw the flow of the code around it.