LinkedList in Java

LinkedList in Java is a doubly-linked list implementation of the List and Deque interfaces. Each element is stored in a node containing a value and pointers to both the previous and next nodes. This structure makes insertions and removals at arbitrary positions extremely cheap when you have a reference to the relevant node.

Introduction

LinkedList is a doubly-linked list implementation — each node stores its value plus pointers to both the previous and next nodes. This structure makes insertions and removals at arbitrary positions extremely cheap when you already have a reference to the neighboring node: just reconnect two pointers in O(1), no shifting required. At the head and tail, where the list maintains direct references, operations are always O(1) regardless of list size. This makes LinkedList the natural choice for queue and deque implementations where you frequently add or remove from both ends.

The tradeoff is hidden in the name: linked means pointer-chased. Each node lives separately in heap memory, connected by pointers rather than stored contiguously. The CPU cannot prefetch the next node because it does not know where it is until it dereferences the current node’s pointer. For sequential traversal — the most common iteration pattern — ArrayList is 2-5x faster in practice simply because its elements sit in contiguous memory and the CPU prefetches efficiently. Random access by index is O(n) for LinkedList versus O(1) for ArrayList — a catastrophic difference for index-heavy access patterns.

This post covers the internal node structure and pointer mechanics, the O(1) operations at head and tail via Deque methods, the failure scenarios (empty list exceptions, concurrent modification, null handling), and the performance trade-offs that determine when LinkedList beats ArrayList and when it loses decisively.

When to Use LinkedList

Use LinkedList when:

• You frequently insert or delete elements at arbitrary positions or at the head/tail
• You need a Deque implementation (FIFO/BFIFO operations) with O(1) performance
• You do not need random access by index very often
• You are building data structures like stacks, queues, or adjacency lists

Do not use LinkedList when:

• You frequently access elements by index (use ArrayList)
• You scan through elements in order (ArrayList has better cache locality)
• You need thread-safe operations
• Memory is constrained — each node carries two extra pointer fields

Internal Structure

LinkedList uses a static inner Node class with forward and backward pointers:

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

The list maintains first and last pointers (for O(1) head/tail access) and tracks size.

Mermaid Diagram: LinkedList Node Structure

graph LR
    A["Node prev=null<br/>item=A<br/>next=Node B"] --> B["Node prev=Node A<br/>item=B<br/>next=Node C"]
    B --> C["Node prev=Node B<br/>item=C<br/>next=null"]
    A --> D["null (head)"]
    C --> E["null (tail)"]

Failure Scenarios

Scenario	Cause	Result
NullPointerException	Adding null when list does not permit nulls	Runtime crash
NoSuchElementException	Calling getFirst() / pop() on empty list	Runtime crash
ConcurrentModificationException	Modifying during iteration	Runtime crash
Memory overhead	Very large lists with many nodes	OutOfMemoryError from GC pressure

Trade-Off Table

Aspect	LinkedList	ArrayList
Random access	O(n) — must traverse	O(1)
Insertion at head	O(1)	O(n) — shift all elements
Insertion at tail	O(1)	O(1) amortized
Insertion at middle	O(n) to find position + O(1) to insert	O(n) to find + O(n) to shift
Memory per element	O(n) overhead — 2 pointers + value	O(1) — just value
Cache locality	Poor — nodes scattered	Excellent — contiguous
Iterator invalidation	Only on structural changes at that position	Only on structural changes at that position

Code Snippets

Deque Operations

LinkedList<String> queue = new LinkedList<>();
queue.addLast("task1");    // enqueue
queue.addLast("task2");
queue.addFirst("urgent");  // push front
String first = queue.removeFirst();  // "urgent" — O(1)
String next = queue.removeFirst();   // "task1" — O(1)

Removing During Iteration

LinkedList<Integer> nums = new LinkedList<>(List.of(1, 2, 3, 4, 5));
ListIterator<Integer> it = nums.listIterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) {
        it.remove();  // Safe — iterator maintains position
    }
}
// nums = [1, 3, 5]

Converting to Array

LinkedList<String> items = new LinkedList<>(List.of("a", "b", "c"));
String[] array = items.toArray(new String[0]);  // Zero-length array leverages ArrayList's grow strategy

Observability Checklist

• Track LinkedList size to detect unbounded growth
• Monitor iteration time in hot paths — O(n) scans are often misidentified as slow network calls
• Profile memory usage — each node adds ~32 bytes overhead on a 64-bit JVM
• Check for repeated list.size() == 0 checks in loops — consider explicit isEmpty() for clarity
• Monitor GC frequency for large linked lists — nodes are individually garbage-collectable unlike array padding

Security Notes

• LinkedList is not thread-safe; use ConcurrentLinkedDeque for concurrent access
• Serializing a LinkedList can be expensive — each node is serialized independently
• Avoid storing sensitive data in nodes that may persist in memory after the list is cleared; unlike arrays, there is no efficient way to zero out node contents

Common Pitfalls / Anti-Patterns

1. Assuming O(1) insertion: Insertion is O(1) only if you already have a reference to the node. Finding the node requires O(n) traversal from the nearest end.
2. Memory overhead: A LinkedList of 1 million Integer objects requires ~48MB (3 pointers + object header per node) vs ~4MB for an ArrayList of the same elements.
3. Reverse iteration: Use list descendingIterator() for efficient tail-to-head traversal
4. pollFirst() vs removeFirst(): pollFirst() returns null on empty list; removeFirst() throws NoSuchElementException
5. addFirst() vs push(): Both insert at head, but push() throws NoSuchElementException if insertion fails, while addFirst() returns boolean

Quick Recap

• LinkedList is a doubly-linked list with O(1) insertions/removals at known positions (head/tail)
• Random access is O(n) — do not use LinkedList when index-based access is frequent
• Implements both List and Deque — use as a queue, stack, or list
• Each node stores two pointers in addition to the value — higher memory overhead than ArrayList
• Cache-unfriendly due to pointer chasing — ArrayList is faster for sequential scans

Interview Questions

::: info The following .qa-card components contain typical interview questions you may encounter. Reviewing these will help reinforce key concepts. :::

Further Reading

• Oracle LinkedList Documentation — Official API documentation
• Baeldung: LinkedList vs ArrayList — Detailed performance comparison with benchmarks
• How LinkedList Works Internally — Step-by-step explanation of node structure and operations
• When to Use LinkedList — Use cases where LinkedList outperforms ArrayList

Conclusion

LinkedList excels at O(1) insertions and deletions at known positions — particularly at the head and tail. Its doubly-linked structure means no element shifting, which is its primary advantage over ArrayList. The cost is paid in memory overhead (two pointers per node) and poor cache locality during traversal.

The deciding factor between LinkedList and ArrayList is usually access pattern rather than insertion frequency. If your code accesses elements by index more often than it inserts at arbitrary positions, ArrayList wins. LinkedList also implements Deque, making it a solid choice when you need queue or stack behavior with O(1) operations at both ends.

LinkedList pairs naturally with Queue and Deque for breadth-first traversal and task scheduling. For sorted unique collections, TreeSet offers O(log n) operations with ordering guarantees instead of pointer chasing.