How LinkedList works

For this lesson, we'll focus on how Java 21's java.util.LinkedList is built, why it implements both List and Deque, how its node operations work, what node(index) really costs, and how to reverse linked lists in both library code and interview code. Interviewers ask this because the class looks easy, but the real test is whether you can separate pointer rewiring from finding the position.

01Picture it first: a train with two station signs

A Java LinkedList is not one big object containing all elements. It is a small list object that points to a chain of node objects. The list object keeps two station signs, first and last, so operations at either end do not need a scan.

Fig. 1

A LinkedList object stores first, last and size, and each node points to its previous and next node in a doubly linked chain

Notice three things in the picture. Each element has its own wrapper node. The arrows go both ways, so removing a node can stitch its neighbours together. There is no array index to jump through, so reaching node 7 means walking node by node.

02LinkedList under the hood

The shape below is simplified from OpenJDK, but it keeps the important fields. The real class also has modCount from AbstractList, used by fail-fast iterators.

import java.util.LinkedList;
import java.util.ListIterator;

LinkedList<String> queue = new LinkedList<>();
queue.addLast("auth");
queue.addLast("payment");
queue.addFirst("edge");

String head = queue.removeFirst();       // edge
String middle = queue.get(1);            // payment, found by walking

ListIterator<String> it = queue.listIterator(1);
it.add("fraud-check");                  // insert at cursor
System.out.println(queue);               // [auth, fraud-check, payment]

Notice the split. addFirst, addLast, removeFirst and removeLast are O(1). get(1) and listIterator(1) must find the indexed node first. Once the iterator is sitting at the cursor, it.add(...) is O(1).

The internal node is this idea:

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

    Node(Node<E> prev, E item, Node<E> next) {
        this.item = item;
        this.next = next;
        this.prev = prev;
    }
}

The main list object has three fields that matter for structure: first, last and size. These work together through four primitive operations.

Here is a readable version of linkBefore. The important phrase is after succ is known.

private void linkBefore(E item, Node<E> succ) {
    Node<E> pred = succ.prev;
    Node<E> newNode = new Node<>(pred, item, succ);
    succ.prev = newNode;

    if (pred == null) {
        first = newNode;
    } else {
        pred.next = newNode;
    }
    size++;
}

This is where many Big-O explanations go wrong. Inserting beside a node is O(1). Inserting at index 50_000 is not, because Java must first locate index 50_000.

The node(index) trick: walk from the nearer end

LinkedList does not always start from the head. If the index is in the first half, it walks forward from first; otherwise it walks backward from last.

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;
        return x;
    }
}

For a list of 1,000,000 elements, get(10) walks 10 links, while get(999_990) walks 9 links backward. get(500_000) still walks about 500,000 links. The optimisation halves the worst walk, but it does not make indexed access constant time.

03List, Deque and the missing RandomAccess marker

LinkedList implements List<E> and Deque<E>. As a List, it preserves insertion order, permits duplicates, permits null, and exposes indexed methods like get, set, add(index, e) and remove(index). As a Deque, it supports queue and stack methods at both ends: addFirst, addLast, removeFirst, removeLast, offer, poll, push, pop and peek.

It does not implement RandomAccess. That marker tells algorithms, "indexed access is cheap." ArrayList implements it; LinkedList does not. Library code can use that signal to choose an indexed loop for array-backed lists and an iterator walk for linked lists.

static long sum(List<Integer> values) {
    long total = 0;
    if (values instanceof java.util.RandomAccess) {
        for (int i = 0; i < values.size(); i++) total += values.get(i);
    } else {
        for (int value : values) total += value;
    }
    return total;
}

That branch is not about style. On a LinkedList, for (int i = 0; i < n; i++) list.get(i) is O(n^2), because every get(i) starts a new walk.