Linked Lists

A linked list stores each element in its own node, along with a reference to the next one. Nothing is contiguous, nothing has an index, and the whole structure is held together by references.

The node

    /** A record cannot be used here: next has to be reassigned as the list changes. */
    private static final class Node<E> {
        E value;
        Node<E> next;

        Node(E value) {
            this.value = value;
        }
    }

The comment is worth pausing on. A record would be the obvious modern choice for a two-field carrier, but record components are final, and building a list means reassigning next constantly. This is one of the few places where a plain mutable class is genuinely the right tool.

The trade, in both directions

Neither structure is faster. They are fast at different things, and that is the only honest summary.

Adding at the front — the O(1) case

    /** O(1) - the whole point of a linked list. */
    public void addFirst(E value) {
        Node<E> node = new Node<>(value);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head = node;
        }
        size++;
    }

No element moves. Compare an array, where inserting at index 0 shifts every one of n elements.

Why the tail reference is not optional

    /** O(1) only because of the tail reference. */
    public void addLast(E value) {
        Node<E> node = new Node<>(value);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }

Without tail, appending has to walk from the head to find the end — O(n) — and building an n-element list by appending becomes O(n²). One extra field turns a quadratic loop into a linear one.

The asymmetry that argues for doubly linked lists

        Node<E> current = head;
        while (current.next != tail) {
            current = current.next;
        }

Removing the last element is O(n) even with a tail reference, because you need the node before the tail and a singly linked list has no way back. That single asymmetry is the argument for a doubly linked list — each node also pointing at its predecessor — which is what java.util.LinkedList actually is. The cost is another reference per node.

Reversing in one pass

The classic interview exercise, and it is genuinely instructive: three references, four lines, and the order of the lines is the whole problem.

    public void reverse() {
        Node<E> previous = null;
        Node<E> current = head;
        tail = head;
        while (current != null) {
            Node<E> next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        head = previous;
    }

Stash next before overwriting current.next. Reverse those two lines and the rest of the list becomes unreachable — you have reversed the first node and dropped everything else on the floor.

Note tail = head near the top. The old head becomes the new tail, and forgetting it leaves the list working perfectly until the next addLast appends to the wrong end — which is exactly what this assertion is for:

        list.reverse();
        Check.eq(list.toString(), "[3, 2, 1]", "reverse in place");
        // The tail must have moved too, or a later addLast appends to the wrong end.
        list.addLast(0);
        Check.eq(list.toString(), "[3, 2, 1, 0]", "tail is correct after reverse");

Floyd's cycle detection

A linked list can point back into itself, and then any naive traversal loops forever. The obvious fix is a HashSet of visited nodes — correct, and O(n) extra memory. Floyd's algorithm does it in O(1) space:

    public boolean hasCycle() {
        Node<E> slow = head;
        Node<E> fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

One pointer takes one step, the other takes two. If there is a cycle the fast one eventually laps the slow one and they land on the same node; if there is not, the fast one runs off the end. Known universally as the tortoise and the hare.

Note slow == fast, not equals — this compares node identity, and two distinct nodes holding equal values are not a cycle.

When to use one

Rarely, directly. ArrayDeque gives you O(1) at both ends with contiguous memory and beats LinkedList at nearly everything.

What linked structures are genuinely for is being a component of something else. LinkedHashMap threads a linked list through its hash table entries to remember insertion order and make LRU eviction O(1). A hash table with separate chaining makes each bucket a small linked list. The structure earns its place inside other structures.

What to remember

• O(1) at the front, O(n) by index — the mirror image of an array.
• A tail reference is what keeps addLast O(1).
• Removing the last element is O(n) unless the list is doubly linked.
• Reversal: stash next first, and move the tail.
• Floyd's cycle detection is O(n) time and O(1) space.
• Prefer ArrayDeque in application code.