# Deep Dive (java.util) - LinkedList

> *"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.

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/fe8fd94d-15fe-45db-9f72-e188be5296e3.png align="center")

* * *

## The Node Structure

Each element in a `LinkedList` is wrapped in a `Node` object:

```java
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:

```java
transient Node<E> first; // Head of the list
transient Node<E> last;  // Tail of the list
transient int size;       // Number of elements
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/84be2149-2ba5-474f-8af0-f0e0a87eeda4.png align="center")

* * *

## How add() Works

### Adding to the End (Most Common)

```java
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++;
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/c9a8fdb7-f40b-41dc-a177-968e66cf54a9.png align="center")

**Time complexity: O(1)** — we have a direct reference to `last`, so no traversal needed.

### Adding at an Index

```java
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()`

```java
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;
    }
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/f17c0c88-b6ff-40de-a6ee-af4d692e8873.png align="center")

Even with this optimization, finding a node by index is still **O(n/2) = O(n)**.

* * *

## How get() Works — The O(n) Problem

```java
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

```java
// ❌ 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

```java
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index)); // Find node (O(n)), then unlink it (O(1))
}
```

### The Unlink Operation

```java
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;
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/b9362f3d-feca-454b-b93d-4e4c60ae4116.png align="center")

**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

```java
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:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/da988fee-0e02-46ac-882c-d88fc10c455f.png align="center")

### As a Stack (LIFO)

```java
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)

```java
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, `ArrayDeque` is almost always faster for both use cases.

* * *

## Memory Overhead — The Hidden Cost

Each node in a LinkedList has significant overhead:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/3723a9fe-0447-403f-bd07-91cf8ab82b71.png align="center")

**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!

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/f07a0806-d9e9-4dcc-964b-13210ec5e638.png align="center")

* * *

## Cache Misses — The Real Performance Killer

This is the most important section. Modern CPUs have a cache hierarchy:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/28caa9d2-5446-44e0-8f75-3ec8a2ac0fbc.png align="center")

### ArrayList Iteration (Cache-Friendly)

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/18e52df8-e52a-4d5a-a5c1-c3c2dd2afa10.png align="center")

### LinkedList Iteration (Cache-Hostile)

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/b16cfe52-dbd4-4bd9-8ae8-caf3e62c1d8a.png align="center")

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:

```java
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
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/3671dcc1-79b1-479f-b830-b35c60daa887.png align="center")

* * *

## 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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/2b4b744b-b303-457d-b9c6-591abdf59773.png align="center")

* * *

## When to Actually Use LinkedList

The honest answer: **almost never.** But here are the rare legitimate cases:

1.  **You need O(1) removal during iteration** — and you're iterating with `ListIterator`, inserting/removing as you go.
    
2.  **You need** `Deque` **+** `List` **simultaneously** — ArrayDeque doesn't implement `List`, so if you need both `get(index)` and `addFirst()`, LinkedList is your only option in the JDK.
    
3.  **Large elements, frequent reordering** — if each element is huge and you're constantly moving elements around, avoiding `System.arraycopy` might 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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/6894e380-ea4e-4831-a866-074d7981716b.png align="center")

**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.