The question of “ArrayList vs. LinkedList” is a rite of passage for every Java developer. We learned the Big O notation in university: LinkedList is $O(1)$ for insertions, while ArrayList is $O(n)$ if resizing occurs.
However, in 2025, theory often fails to align with hardware reality.
With modern CPU architectures, huge L3 caches, and the sophisticated optimizations in OpenJDK 21+, the textbook answers are frequently wrong in production environments. Additionally, legacy classes like Vector still linger in old codebases, confusing new developers.
In this article, we won’t just look at the Javadoc. We will use JMH (Java Microbenchmark Harness) to measure the actual throughput of these collections. We will analyze CPU cache locality, memory overhead, and concurrent implications to give you a definitive answer on what to use in your modern Java applications.
Prerequisites & Environment #
To follow the benchmarks in this guide, ensure you have the following setup:
- JDK: Java 21 LTS (or Java 24)
- Build Tool: Maven 3.9+ or Gradle 8.5+
- IDE: IntelliJ IDEA or Eclipse
- Memory: At least 4GB heap allocated for the benchmark process.
We will rely heavily on JMH, the de facto standard for Java benchmarking, as strictly timing code with System.currentTimeMillis() is notoriously inaccurate due to JVM warm-up and Just-In-Time (JIT) compilation phases.
1. Architectural Differences: A Visual Overview #
Before benchmarking, we must understand how these lists store data in memory. This structural difference is the primary driver of performance.
ArrayList #
Backed by a dynamic Object array. It provides fast random access but requires resizing (copying the array) when capacity is reached. Crucially, arrays occupy contiguous memory, making them incredibly friendly to CPU pre-fetching.
LinkedList #
A Doubly Linked List. Each element is wrapped in a Node object containing pointers to the previous and next nodes. This results in scattered memory allocation and significantly higher memory consumption per element.
Vector #
Architecturally similar to ArrayList but all its methods are synchronized. This introduces thread-safety locking overhead, even when the list is accessed by a single thread.
2. Setting Up the JMH Benchmark #
To get real data, we need to stress test these implementations. Create a new Maven project and add the JMH dependencies.
Maven Dependencies (pom.xml)
#
<dependencies>
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-core</artifactId>
<version>1.37</version>
</dependency>
<dependency>
<groupId>org.openjdk.jmh</groupId>
<artifactId>jmh-generator-annprocess</artifactId>
<version>1.37</version>
<scope>provided</scope>
</dependency>
</dependencies>The Benchmark Class #
We will test three scenarios:
- Iterate: Traversing the list (the most common operation).
- Add Start: Inserting at index 0 (theoretically LinkedList’s strength).
- Random Access: Getting an item from the middle.
package com.javadevpro.benchmarks;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
import java.util.*;
import java.util.concurrent.TimeUnit;
@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@Fork(1)
public class ListBenchmark {
@Param({"1000", "100000"})
private int size;
private List<Integer> arrayList;
private List<Integer> linkedList;
private List<Integer> vector;
@Setup(Level.Trial)
public void setup() {
arrayList = new ArrayList<>();
linkedList = new LinkedList<>();
vector = new Vector<>();
for (int i = 0; i < size; i++) {
arrayList.add(i);
linkedList.add(i);
vector.add(i);
}
}
// --- SCENARIO 1: Iteration ---
@Benchmark
public void iterateArrayList(Blackhole bh) {
for (Integer i : arrayList) {
bh.consume(i);
}
}
@Benchmark
public void iterateLinkedList(Blackhole bh) {
for (Integer i : linkedList) {
bh.consume(i);
}
}
@Benchmark
public void iterateVector(Blackhole bh) {
for (Integer i : vector) {
bh.consume(i);
}
}
// --- SCENARIO 2: Random Access ---
@Benchmark
public void getMiddleArrayList(Blackhole bh) {
bh.consume(arrayList.get(size / 2));
}
@Benchmark
public void getMiddleLinkedList(Blackhole bh) {
bh.consume(linkedList.get(size / 2));
}
// --- SCENARIO 3: Insert at Head (Copy heavy for Array) ---
@Benchmark
public List<Integer> addAtHeadArrayList() {
// We clone to avoid growing indefinitely during benchmark
List<Integer> list = new ArrayList<>(arrayList);
list.add(0, 9999);
return list;
}
@Benchmark
public List<Integer> addAtHeadLinkedList() {
List<Integer> list = new LinkedList<>(linkedList);
list.add(0, 9999);
return list;
}
}To run this, you would typically build your jar and run it via command line, but for brevity, assume we’ve executed this on a standard development machine (Apple M3 Pro or Intel i9 equivalent).
3. Analysis of Performance Results #
Let’s break down what typically happens when you run these benchmarks in a modern JVM environment.
Scenario A: Random Access (get(index))
#
- ArrayList: Instant. Math is simple:
base_address + (index * element_size). - Vector: Fast, but slightly slower than ArrayList due to the synchronization lock acquisition/release, even if uncontended.
- LinkedList: Terrible. It must traverse
n/2nodes to find the middle element.
Winner: ArrayList
Scenario B: Iteration (Looping) #
This is where the CPU Cache (L1/L2) plays a massive role.
Because ArrayList is contiguous in memory, when the CPU fetches the first element, it likely pulls the next several elements into the cache line (usually 64 bytes). This means the CPU rarely waits for RAM.
LinkedList nodes are scattered all over the Heap. To get the next node, the CPU must fetch a pointer, wait for RAM to deliver that address, and repeat. This is a Cache Miss, and it destroys performance.
Key Insight: Even for operations where LinkedList is theoretically $O(1)$ and ArrayList is $O(n)$, ArrayList is often faster for small-to-medium collections simply because memory copy (
System.arraycopy) is intrinsic and blazing fast compared to pointer chasing.
Scenario C: Insertion at Head (add(0, element))
#
Theory says LinkedList is $O(1)$ here (just swap pointers) and ArrayList is $O(n)$ (shift everything right).
Reality: LinkedList creates a new Node object (allocation overhead). ArrayList uses a native memory copy command.
For small lists (< 1,000 elements), ArrayList often beats LinkedList even here! LinkedList only wins consistently on head insertions when the list size becomes very large (e.g., > 100,000 elements).
4. Feature Comparison Matrix #
Here is a summary comparing the three implementations based on 2025 Java standards.
| Feature | ArrayList | LinkedList | Vector |
|---|---|---|---|
| Underlying Structure | Dynamic Array | Doubly Linked List | Dynamic Array |
| Memory Efficiency | High (Compact) | Low (Node overhead: +24-40 bytes per item) | High |
| Cache Locality | Excellent | Poor (Pointer chasing) | Excellent |
| Random Access | $O(1)$ | $O(n)$ | $O(1)$ |
| Insert at End | $O(1)$ (Amortized) | $O(1)$ | $O(1)$ (Amortized) |
| Insert in Middle | $O(n)$ (Array copy) | $O(n)$ (Traversal) + $O(1)$ (Link) | $O(n)$ |
| Thread Safety | No | No | Yes (Synchronized) |
| Resize Growth | 50% (old + old >> 1) |
N/A (Per node allocation) | 100% (Doubles) |
| Recommendation | Default Choice | Rare Queue scenarios | Do Not Use |
5. Why You Should Stop Using Vector #
You might see Vector in legacy banking or enterprise code.
Why is it bad?
Vector synchronizes every single operation.
// Vector source code snippet
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}In the era of Virtual Threads (Project Loom) introduced in Java 21, excessive synchronization on intrinsic locks (monitors) can pin the carrier thread, potentially degrading the throughput of your high-concurrency application.
If you need a thread-safe list, do not use Vector. Instead use:
CopyOnWriteArrayList(Read-heavy, write-rare scenarios).Collections.synchronizedList(new ArrayList<>())(If you must lock).
6. Common Traps and Best Practices #
Trap 1: Using LinkedList for Queues #
While LinkedList implements Queue and Deque, it is rarely the most performant choice.
Solution: Use ArrayDeque. It uses arrays (circular buffer), has better cache locality, produces less garbage, and is generally faster than LinkedList for stack/queue operations.
Trap 2: Initial Capacity Ignorance #
When you do new ArrayList(), it creates a small array (default 10). If you add 1,000,000 items, it has to resize and copy arrays many times (10 -> 15 -> 22 …).
Solution: Always estimate size.
// Much faster - avoids resizing overhead
List<User> users = new ArrayList<>(10000); Trap 3: Premature Optimization #
Don’t choose LinkedList because you “might insert in the middle one day.”
Solution: Start with ArrayList. Only switch if profiling proves that list insertion is a bottleneck.
Conclusion #
In 2025, the landscape of Java collections is clear:
- ArrayList is the King. It should be your default for 99% of use cases due to CPU cache friendliness and low memory overhead.
- LinkedList is a niche tool. Use it only if you have massive lists where you frequently add/remove from the start or middle using a
ListIterator, and random access is never required. Even then, considerArrayDequeif you only need Queue behavior. - Vector is dead. Treat it as deprecated.
Key Takeaway: Modern hardware favors contiguous memory. Big O notation ignores constants and hardware architecture. When in doubt, use ArrayList—your CPU (and your users) will thank you.
Did this performance breakdown change how you view Java lists? Share your experience with collection tuning in the comments below!