Remove the Head of a Linked List (with Empty-List Guard)

Try This First

You have a list [10, 20, 30]. Write, from memory, the three lines inside remove() that capture the value, advance head, and decrement size. Do not look below yet.

T val = head.data;   // capture before you move head
head = head.next;    // advance
size--;
return val;

What You Need To Walk In With

• head is the only entry point to your list. When the list is empty, head == null.
• Removing the head means advancing head to head.next and decrementing size.
• You must capture the old head’s data before you move the pointer, or you cannot return it.
• Calling remove() on an empty list must throw NoSuchElementException, not produce a NullPointerException.
• This operation runs in O(1) time because no traversal is needed.

How It Works

A no-dummy-head singly linked list holds a head reference of type Node<T> and an integer size. There is no sentinel node. When the list is empty, head is null.

Removing the head is a three-step sequence:

1. Guard: if head == null, throw NoSuchElementException.
2. Capture the data from head before touching the pointer.
3. Advance head to head.next, decrement size, and return the captured value.

public T remove() {
    if (head == null) throw new NoSuchElementException("Empty list");
    T val = head.data;    // step 2: capture first
    head = head.next;     // step 3: advance
    size--;
    return val;
}

Here is what the pointer state looks like for [10, 20, 30]:

Before remove():
  head
   |
  [10] --> [20] --> [30] --> null
   val = 10

After head = head.next:
  head
   |
  [20] --> [30] --> null
  (node holding 10 is now unreferenced)

The old node holding 10 is unreferenced after the reassignment. Java’s garbage collector reclaims it automatically, so no explicit deletion step is needed.

Source: Liang 10e Ch 24

Worked Example: Predict, Then Check

After these three calls:

MyLinkedList<Integer> list = new MyLinkedList<>();
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
// list is now [1, 2, 3]

int x = list.remove();

What is x? What does the list contain after the call?

A Common Mistake

A common error is to advance head before capturing the data:

// WRONG
head = head.next;
return head.data;   // returns the NEW head's data, not the removed node's data

On a list [10, 20, 30] this returns 20 instead of 10. Worse, on a one-element list [10], head becomes null before the return, causing a NullPointerException on head.data.

The fix is to always capture first: T val = head.data; before you write to head. The order is capture, advance, return. (Source: Liang 10e Ch 24)

Go Deeper (optional)

remove() runs in O(1) time because you access only the first node regardless of list size. Compare that to removeLast(), which must traverse the entire list to find the second-to-last node, making it O(n) without a tail reference. If your design adds a tail pointer, removing the last element still requires that traversal because singly linked nodes do not point backward. A dummy-head variant (covered later in the course) can simplify the bookkeeping for some edge cases, but this course builds the no-dummy-head form first so you can see exactly what each pointer update does.

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.