java-core-examples/list-benchmarks/README.md

list-benchmarks

Companion code for the ankurm.com post "ArrayList vs LinkedList in 2026: JMH Benchmarks and Why LinkedList Rarely Wins." Module in java-core-examples, the Java-core series.

Versions this was built and tested against

Component	Version	Notes
JDK	25.0.4.1+1 (Temurin, LTS)
JMH	1.37
JUnit Jupiter	5.11.0	Correctness tests only - do not read these as throughput proof.
Maven	3.9.11
Hardware	shared multi-tenant container	See the honesty note below - this is not an isolated benchmarking box.

Quickstart

export JAVA_HOME=/path/to/jdk-25
mvn package
java -jar target/benchmarks.jar ListOpsBenchmark
java -jar target/benchmarks.jar DequeBenchmark
java -cp target/classes com.ankurm.listbenchmarks.IteratorRemovalDemo

scripts/run-all.sh regenerates every file in output/. scripts/run.sh <Class> [jmh-args] runs one benchmark ad hoc.

What's in here

File	What it shows
src/main/java/.../ListOpsBenchmark.java	ArrayList vs LinkedList: append, front-insert, middle-insert, random get, full iteration. Each mutating benchmark inserts then immediately removes, so list size stays constant across the whole run.
src/main/java/.../DequeBenchmark.java	ArrayDeque vs LinkedList vs ArrayList used as a stack/queue: push/pop at the head, offer/poll at the tail.
src/main/java/.../IteratorRemovalDemo.java	The one case LinkedList can win: removing through an Iterator cursor instead of by index. Plain nanoTime(), not JMH - read as illustrative.
src/test/java/.../CorrectnessTest.java	Sanity checks: both lists agree on contents and ordering; ArrayDeque genuinely does not implement List.
output/01-list-ops-sweep.txt	Full JMH report for ListOpsBenchmark, sizes 1,000 and 100,000.
output/02-deque-ops-sweep.txt	Full JMH report for DequeBenchmark, sizes 1,000 and 100,000.
output/03-iterator-removal-demo.txt	Captured run of the iterator-removal illustration.
output/04-correctness-test.txt	JUnit run (4/4 passing).

Reading the numbers honestly (shared container, not an isolated box)

This run shares CPU with five other concurrent build/benchmark workloads on the same host - JMH was still run one class at a time, back to back, never overlapping with itself, but it cannot see or control what else is scheduled on the machine. Several rows carry an error bar wider than the mean (DequeBenchmark.offerPollTail ArrayDeque @1000: 203,926 ± 985,600 ops/ms), which is the signature of scheduler noise, not of the JVM doing something strange. Treat every number here as directional, and prefer the ratios between rows measured in the same run over the absolute ops/ms.

With that caveat:

• addFront is the one operation where LinkedList clearly and consistently wins - flat ~43,000 ops/ms at both 1,000 and 100,000 elements, because it is an O(1) pointer write regardless of size. ArrayList.addFront falls from ~6,600 ops/ms at 1,000 elements to ~53 ops/ms at 100,000 - two orders of magnitude - because every call shifts the whole array by one.
• addMiddle favors ArrayList by roughly 20-25x at both sizes, even though both implementations are doing O(n) work to get there. ArrayList's half is a single System.arraycopy; LinkedList's is a pointer-chasing walk node by node to find the midpoint, and that walk is the slower half of "O(n) to reach the middle, O(1) to unlink."
• getRandom and iterateSum both favor ArrayList, the first by ~2,000x at 100,000 elements (random access on LinkedList is a full traversal per call), the second by ~4-5x even though iteration is O(n) either way - this is the cache-locality gap the post discusses: one contiguous int[]-backed array versus following a chain of individually-allocated Node objects scattered across the heap.
• For stack/queue-shaped work, ArrayDeque is the one to reach for, not LinkedList - pushPopHead favors ArrayDeque over LinkedList by ~3.6x at 1,000 elements, and ArrayDeque never degrades to ArrayList's O(n) head-shift problem (ArrayList.pushPopHead collapses to 56 ops/ms at 100,000 elements, a 1,800x gap from ArrayDeque's 103,406).
• The iterator-removal illustration (output/03) is the sharpest number in this repository: removing every third element of a 200,000-element list through an Iterator cursor takes 1,314 ms with ArrayList and 5.0 ms with LinkedList - a 262x gap - because ArrayList.remove(index) still shifts the tail of the array on every call even when the index came from an iterator already sitting on it, while LinkedList.Iterator.remove() unlinks the node the cursor already holds. This is also, honestly, close to the only realistic case where reaching for LinkedList over ArrayList is the right call in 2026 code.

License

MIT - see the repo-wide LICENSE.