Deep Dive (java.util) - LinkedList
How It Really Works Under the Hood
"LinkedList is the data structure everyone learns first and should use last."
This article tears apart java.util.LinkedList — a doubly-linked list that also implements Deque. We'll look at the node structure, pointer mechanics, and most importantly, why you almost never want to use it.
1. What is LinkedList, Really?
LinkedList is a doubly-linked list — a chain of nodes where each node holds a reference to the previous and next nodes. It also implements the Deque (double-ended queue) interface, making it usable as a stack, queue, or deque.
The Node Structure
Each element in a LinkedList is wrapped in a Node object:
private static class Node<E> {
E item; // The actual data
Node<E> next; // Pointer to next node
Node<E> prev; // Pointer to previous node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
The LinkedList itself only holds two pointers:
transient Node<E> first; // Head of the list
transient Node<E> last; // Tail of the list
transient int size; // Number of elements
How add() Works
Adding to the End (Most Common)
public boolean add(E e) {
linkLast(e); // Always appends to the end
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode; // Empty list — new node is also first
else
l.next = newNode; // Link old last to new node
size++;
modCount++;
}
Time complexity: O(1) — we have a direct reference to last, so no traversal needed.
Adding at an Index
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element); // Append
else
linkBefore(element, node(index)); // Insert before node at index
}
The node(index) call is the expensive part — it must traverse the list to find the node at that position.
The Clever Optimization in node()
Node<E> node(int index) {
if (index < (size >> 1)) {
// Search from the front
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// Search from the back
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Even with this optimization, finding a node by index is still O(n/2) = O(n).
How get() Works — The O(n) Problem
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
That's it — it calls node(index), which traverses from the nearest end.
This is the fundamental problem with LinkedList. Every indexed access requires walking the chain. Compare:
| Operation | ArrayList | LinkedList |
|---|---|---|
get(0) |
O(1) | O(1) |
get(size/2) |
O(1) | O(n/2) |
get(size-1) |
O(1) | O(1) |
get(random) |
O(1) | O(n) |
The Deadly for Loop Pattern
// ❌ CATASTROPHIC — O(n²) with LinkedList!
LinkedList<String> list = new LinkedList<>(/* 10,000 elements */);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i)); // Each get() walks from the start!
}
// get(0): 0 hops
// get(1): 1 hop
// get(2): 2 hops
// ...
// get(9999): 5000 hops (from the back)
// Total: ~25,000,000 hops = O(n²)!
// ✅ CORRECT — use iterator, which walks sequentially
for (String s : list) {
System.out.println(s); // Iterator moves node-by-node — O(n) total
}
How remove() Works
Removing by Index
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index)); // Find node (O(n)), then unlink it (O(1))
}
The Unlink Operation
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next; // Removing the first node
} else {
prev.next = next; // Bypass x
x.prev = null; // Help GC
}
if (next == null) {
last = prev; // Removing the last node
} else {
next.prev = prev; // Bypass x
x.next = null; // Help GC
}
x.item = null; // Help GC
size--;
modCount++;
return element;
}
Key insight: The unlink operation itself is O(1) — just pointer reassignment. But finding the node is O(n). If you already have a reference (via Iterator), removal is genuinely O(1).
Removing via Iterator — The True O(1) Path
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String element = it.next();
if (element.equals("Cherry")) {
it.remove(); // O(1) — iterator already points to the node!
}
}
The Deque Interface — Stack & Queue
LinkedList implements Deque, so it can be used as multiple data structures:
As a Stack (LIFO)
LinkedList<String> stack = new LinkedList<>();
stack.push("first"); // addFirst()
stack.push("second"); // addFirst()
stack.push("third"); // addFirst()
stack.pop(); // "third" — removeFirst()
stack.pop(); // "second" — removeFirst()
stack.peek(); // "first" — peekFirst() without removing
As a Queue (FIFO)
LinkedList<String> queue = new LinkedList<>();
queue.offer("first"); // addLast()
queue.offer("second"); // addLast()
queue.offer("third"); // addLast()
queue.poll(); // "first" — removeFirst()
queue.poll(); // "second" — removeFirst()
queue.peek(); // "third" — peekFirst() without removing
Warning: While LinkedList can be used as a stack or queue,
ArrayDequeis almost always faster for both use cases.
Memory Overhead — The Hidden Cost
Each node in a LinkedList has significant overhead:
Comparison for storing 1,000,000 Strings:
| ArrayList | LinkedList | |
|---|---|---|
| Reference storage | 4 MB (Object[]) | 4 MB (item refs in nodes) |
| Node overhead | 0 | 32 MB (32 bytes × 1M nodes) |
| ArrayList wrapper | ~40 bytes | ~40 bytes |
| Total overhead | ~4 MB | ~36 MB |
| Ratio | 1x | 9x more memory |
LinkedList uses 9x more memory than ArrayList just for structural overhead!
Cache Misses — The Real Performance Killer
This is the most important section. Modern CPUs have a cache hierarchy:
ArrayList Iteration (Cache-Friendly)
LinkedList Iteration (Cache-Hostile)
Each node.next dereference jumps to a random heap location. The CPU's prefetcher cannot predict the pattern, so nearly every access is a cache miss — 100x slower than a cache hit.
This is why ArrayList often beats LinkedList even for operations where LinkedList has better Big-O. Cache misses dominate real-world performance.
Iterator — The Only Fast Way to Traverse
The ListIterator is the only efficient way to use LinkedList:
LinkedList<String> list = new LinkedList<>();
// ... populate ...
// ✅ ListIterator — O(n) traversal
ListIterator<String> iter = list.listIterator();
while (iter.hasNext()) {
String val = iter.next(); // O(1) per step — follows node.next
if (val.equals("target")) {
iter.remove(); // O(1) — unlinks current node
iter.add("replacement"); // O(1) — links new node
}
}
// ✅ Can also go backwards
while (iter.hasPrevious()) {
String val = iter.previous(); // O(1) per step — follows node.prev
}
LinkedList vs ArrayList — The Honest Comparison
| Operation | ArrayList | LinkedList | Winner |
|---|---|---|---|
get(index) |
O(1) | O(n) | ArrayList |
set(index, e) |
O(1) | O(n) | ArrayList |
add(end) |
O(1) amortized | O(1) | Tie |
add(beginning) |
O(n) | O(1) | LinkedList |
add(index, e) |
O(n) | O(n)* | Tie† |
remove(index) |
O(n) | O(n)* | Tie† |
remove(via iterator) |
O(n) shift | O(1) | LinkedList |
contains(o) |
O(n) | O(n) | Tie |
| Memory per element | ~4 bytes | ~32 bytes | ArrayList |
| Cache locality | Excellent | Terrible | ArrayList |
| Iterator traversal | O(n) | O(n) | ArrayList** |
* O(n) for finding the node + O(1) for unlinking
† LinkedList wins Big-O for the operation but cache misses make it slower in practice
** ArrayList wins due to cache locality despite same asymptotic complexity
The Verdict
When to Actually Use LinkedList
The honest answer: almost never. But here are the rare legitimate cases:
You need O(1) removal during iteration — and you're iterating with
ListIterator, inserting/removing as you go.You need
Deque+Listsimultaneously — ArrayDeque doesn't implementList, so if you need bothget(index)andaddFirst(), LinkedList is your only option in the JDK.Large elements, frequent reordering — if each element is huge and you're constantly moving elements around, avoiding
System.arraycopymight pay off.
Joshua Bloch (creator of the Collections Framework) has said: "Does anyone actually use LinkedList? I wrote it, and I never use it."
Summary
The one-liner: LinkedList is a doubly-linked structure with O(1) end operations but O(n) indexed access, terrible cache locality, and 9x the memory overhead of ArrayList — making it the wrong choice for almost every use case.