Walking to the Predecessor to Remove the Last Node

Try This First

A list holds three integers: 10 -> 20 -> 30 -> null. You want to remove 30. Which reference do you actually need to change, and which node holds it?

What You Need To Walk In With

• In a singly linked list with no dummy head, the only way to disconnect the last node is to null out its predecessor’s next field.
• You cannot disconnect a node by assigning null to a local variable that points to it; you must follow the chain one level back.
• The loop condition prev.next.next != null stops the walk at the predecessor, not at the last node.
• Two special cases must be handled before the walk: an empty list (head == null) and a single-element list (head.next == null).
• The overall cost of this operation is O(n) because the walk visits every node except the last.

How It Works

A singly linked list stores a head reference and a size counter. There is no tail pointer and no dummy head node.

To remove the last element, the method must find the node just before the last one so it can set that node’s next to null.

Three cases to handle:

1. Empty list: throw immediately; there is nothing to remove.
2. Single-element list: set head = null and return the value. No walk is needed, and attempting head.next.next here would cause a NullPointerException.
3. Two or more elements: walk a prev reference forward while prev.next.next != null. When the loop exits, prev is the predecessor of the last node.

Pointer sketch (three-element list):

head
 |
[10] --next--> [20] --next--> [30] --next--> null
                prev (loop stops here)        <-- to be unlinked

After prev.next = null:

head
 |
[10] --next--> [20] --next--> null        [30] (unreachable, GC'd)

Java 25 implementation (no dummy head, generic):

public T removeLast() {
    if (head == null) throw new java.util.NoSuchElementException("Empty list");
    if (head.next == null) {          // single-element case
        T val = head.data;
        head = null;
        size--;
        return val;
    }
    Node<T> prev = head;
    while (prev.next.next != null) {  // stop at predecessor
        prev = prev.next;
    }
    T val = prev.next.data;
    prev.next = null;
    size--;
    return val;
}

The two-level dereference prev.next.next reads as: “the node after the node after prev.” When that is null, prev.next is the last node, so prev is where the cut must happen.

Worked Example: Predict, Then Check

A list currently holds [A, B, C, D] (head points to A). You call removeLast().

Step through the walk mentally:

• Start: prev = A. Is prev.next.next (which is C) null? No. Move forward.
• prev = B. Is prev.next.next (which is D) null? No. Move forward.
• prev = C. Is prev.next.next (D.next = null) null? Yes. Stop.

What value is returned, and what does the list look like after the call?

A Common Mistake

A common first attempt walks to the last node rather than its predecessor:

// WRONG
Node<T> cur = head;
while (cur.next != null) cur = cur.next;
cur = null;   // has no effect on the list

This finds the last node correctly, but then assigns null to the local variable cur. That assignment changes only the local variable; it does not reach back and null out the next field of the node before it. The last node remains connected to the chain. The fix is to walk one step earlier using while (prev.next.next != null) so that after the loop, prev.next = null actually severs the connection at the source. (Source: S20.Lab5-LL_NDH.LinkedList.removeLast)

Go Deeper (optional)

Because the walk visits every node, removeLast on a singly linked list is O(n). Contrast that with removeFirst, which is O(1): you just redirect head. This asymmetry is a fundamental property of singly linked structures. A doubly linked list with a tail pointer can remove the last node in O(1) by following tail.prev, which is the approach introduced later in this course (Liang 10e Ch 24). For now, recognizing the O(n) cost is what matters.

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.