Java LinkedList Deep Dive — Doubly-Linked Nodes

3 minute read

LinkedList is a doubly-linked list that implements both List and Deque. It excels at O(1) insertions/removals at the head and tail — but its poor cache locality means ArrayList is almost always faster in practice.

Internal Structure

LinkedList<String> list = LinkedList of ["A", "B", "C"]

   ┌──────────┐    ┌──────────┐    ┌──────────┐
   │ prev: null│←──│ prev     │←──│ prev     │
   │ item: "A" │    │ item: "B" │    │ item: "C" │
   │ next     │──→│ next     │──→│ next: null│
   └──────────┘    └──────────┘    └──────────┘
        ↑                               ↑
       first                           last

   size = 3

Each element is stored in a Node object:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Big-O Complexity

Operation Time Notes
addFirst(e) / addLast(e) O(1) Direct pointer update
removeFirst() / removeLast() O(1) Direct pointer update
getFirst() / getLast() O(1) Direct access to head/tail
get(index) O(n) Must traverse from nearest end
add(index, element) O(n) O(n) to find + O(1) to insert
remove(index) O(n) O(n) to find + O(1) to unlink
contains(Object) O(n) Linear search
size() O(1) Stored field

The O(n) traversal for get(index) is the killer — it makes LinkedList unsuitable for random access.

LinkedList as a Deque

LinkedList implements Deque (double-ended queue), making it usable as both a stack and a queue:

As a Queue (FIFO)

Deque<String> queue = new LinkedList<>();
queue.offer("First");     // add to tail
queue.offer("Second");
queue.offer("Third");

queue.poll();   // "First" — remove from head
queue.peek();   // "Second" — look at head without removing

As a Stack (LIFO)

Deque<String> stack = new LinkedList<>();
stack.push("Bottom");   // add to head
stack.push("Middle");
stack.push("Top");

stack.pop();    // "Top" — remove from head
stack.peek();   // "Middle"

Prefer ArrayDeque over LinkedList for both stack and queue use cases — it’s faster due to array-backed cache locality.

When LinkedList Is Appropriate

Use Case Why
Implementing a Queue/Deque O(1) head + tail operations
Frequent insert/remove at both ends No shifting like ArrayList
Iterator-based insert/remove O(1) when you already have the position

When LinkedList Is NOT Appropriate

Situation Why Not
Random access by index O(n) traversal
Large lists with iteration Poor cache locality
General-purpose list ArrayList is faster in practice
Memory-constrained ~40 bytes per node vs ~8 bytes per slot

Memory Overhead

ArrayList element:  1 reference (8 bytes on 64-bit)
LinkedList element: Node object (16 bytes header + 8 prev + 8 next + 8 item = 40 bytes)

For 1 million elements:

  • ArrayList: ~8 MB + some wasted capacity
  • LinkedList: ~40 MB (5× more memory)

Plus, each Node is a separate heap object → more garbage collection pressure.

Cache Locality — The Hidden Performance Killer

ArrayList: [A][B][C][D][E][F] ← contiguous in memory → CPU cache friendly
                                 One cache line loads multiple elements

LinkedList: [A]→...→[B]→...→[C] ← scattered in memory → cache misses
                                    Each access may be a cache miss

Modern CPUs are optimised for sequential memory access. ArrayList’s contiguous array lets the CPU prefetch next elements. LinkedList nodes are scattered across the heap, causing frequent cache misses.

This is why ArrayList often outperforms LinkedList even for operations where LinkedList has better theoretical complexity.

Practical Comparison

// Benchmark: Iterating 1 million elements
ArrayList:   ~2 ms   (sequential memory access)
LinkedList:  ~8 ms   (pointer chasing, cache misses)

// Benchmark: Adding 1 million elements to end
ArrayList:   ~15 ms  (amortized O(1), occasional resize)
LinkedList:  ~25 ms  (O(1) per add, but object creation overhead)

// Benchmark: Adding at position 0 (1000 elements)
ArrayList:   ~0.5 ms (shifts all elements — O(n) per insert)
LinkedList:  ~0.1 ms (pointer update — O(1))

LinkedList wins only for repeated inserts/removes at the head of large lists.

Using ListIterator for Efficient Modification

If you already have an Iterator positioned at the right spot, insert/remove is O(1):

LinkedList<String> list = new LinkedList<>(List.of("A", "C", "D"));
ListIterator<String> it = list.listIterator();

it.next();        // advance past "A"
it.add("B");      // insert "B" after "A" → O(1)
// list = [A, B, C, D]

it.next();        // advance past "C"
it.remove();      // remove "C" → O(1)
// list = [A, B, D]

The Verdict

Factor ArrayList LinkedList Winner
Random access O(1) O(n) ArrayList
Append to end O(1) amortized O(1) Tie
Insert at head O(n) O(1) LinkedList
Memory usage Low High (~5×) ArrayList
Cache performance Excellent Poor ArrayList
As a Deque ❌ ✅ (but ArrayDeque is better) ArrayDeque

Bottom line: Use ArrayList for List operations. Use ArrayDeque for Deque operations. LinkedList is rarely the optimal choice.

Key Takeaways

  1. LinkedList is a doubly-linked list — O(1) at head/tail, O(n) random access.
  2. It implements both List and Deque interfaces.
  3. Memory overhead is ~5× that of ArrayList per element.
  4. Cache locality makes ArrayList faster in practice for most operations.
  5. Use LinkedList only for Deque operations where ArrayDeque isn’t suitable, or for iterator-based insertions in the middle of a traversal.
  6. The correct answer in most cases: use ArrayList.

What’s Next?

Next: Stack and Queue — LIFO/FIFO structures with Deque, ArrayDeque, and real-world use cases.

Updated:

You may also enjoy