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

Trade-Off Table

Code Snippets

Deque Operations

LinkedList implements the full Deque interface, giving you O(1) operations at both ends without any traversal. The core methods are addFirst()/addLast() for insertion, removeFirst()/removeLast() for removal, and getFirst()/getLast() for peeking without removal. These four operations touch only the first and last node references that the list maintains internally — performance never degrades as the list grows.

removeFirst() and getFirst() throw NoSuchElementException on an empty list. pollFirst() and pollLast() return null instead. The difference matters: use the throwing variants when an empty list is an error condition; use the poll* variants when an empty list is a valid terminal state, like draining a work queue until it is done. The same pattern applies to peek* versus get* for inspection-only access.

push() and pop() behave like addFirst() and removeFirst(), which makes LinkedList a natural stack drop-in. The contractual difference is that push() throws IllegalStateException on failure while addFirst() returns a boolean. For queue and deque work, the explicit method names are harder to mix up than the stack aliases.

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 iterators are fail-fast — any structural modification to the list during iteration throws ConcurrentModificationException, whether the change comes from another iterator, a regular loop, or a direct method call. The iterator tracks its own expectedModCount independently from the list’s modCount. On every next() or hasNext() call, the iterator checks whether those counts still match — a mismatch throws immediately.

The safe pattern is to modify through the iterator itself. Calling it.remove() increments the iterator’s expectedModCount to match the list’s new modCount, so the cursor stays valid and iteration continues. it.set(element) and it.add(element) work the same way — both keep the iterator in sync as it proceeds.

The code below filters even numbers by calling it.remove() through the iterator rather than calling nums.remove(element) from outside the loop. Using listIterator() instead of iterator() is important here because ListIterator combines forward traversal with remove() in a single cursor object — exactly what you need for conditional removal 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 and expectedModCount
    }
}
// nums = [1, 3, 5]

The common mistake is calling list.remove(element) from outside the loop after capturing the current element. This modifies the list but does not update the iterator’s expectedModCount, so the next iteration step detects the mismatch and throws. If you need to remove elements based on a condition checked during traversal, always do it through the iterator itself.

Converting to Array

toArray() copies LinkedList elements into an array. The method comes in two forms: toArray() returns Object[] (requires casting), while toArray(T[] a) returns a typed array. The typed form is what you want in practice.

LinkedList<String> items = new LinkedList<>(List.of("a", "b", "c"));
String[] array = items.toArray(new String[0]);  // Zero-length array triggers the grow path

The zero-length array pattern is worth understanding. When you pass an array that is too small, toArray() allocates a new array of the correct type and size. This means the returned array is always a freshly allocated one — your original array is never filled in. Passing an empty array avoids wasting space on an array that will be discarded anyway. If you already know the size, passing a pre-sized array is slightly more efficient because it skips the allocation step:

String[] preSized = items.toArray(new String[items.size()]);  // Reuses your array

A few edge cases to keep in mind:

• Null elements: If the list contains null, it appears as null in the resulting array. The array is not sparse — it has a value at every index.
• Empty list: toArray(new String[0]) returns a newly allocated zero-length array, not your empty array.
• Mixed generic types: If the list holds mixed types that do not all extend T, ArrayStoreException is thrown at runtime.

For most cases, items.toArray(new String[0]) is the idiomatic choice.

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

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
• ArrayList — resizable array, the most common List implementation
• Queue and Deque — Queue interface implemented by LinkedList
• HashMap — hash-based maps with different performance tradeoffs

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.