Pointer Update Order in addFirst

Try This First

You have a non-empty singly linked list. You write this addFirst code:

Node<T> newNode = new Node<>(item);
head = newNode;
newNode.next = head;

What is wrong with the resulting list?

What You Need To Walk In With

• A linked list stores its first node in a head reference; inserting at the front requires updating both newNode.next and head.
• The two assignments are order-dependent: the old value of head must be captured before head is overwritten.
• The correct manual order is always: set newNode.next = head first, then head = newNode.
• A two-argument constructor new Node<>(item, head) evaluates head before any assignment occurs, making it immune to this mistake.
• An empty list (head == null) is handled naturally by the same logic: newNode.next becomes null, which is correct for the only node.

How It Works

When you call addFirst, you need to wire the new node in front of whatever is already there. The wrong instinct is to claim the head reference first:

// WRONG: self-cycle bug
Node<T> newNode = new Node<>(item);
head = newNode;          // head now points to newNode
newNode.next = head;     // head IS newNode, so newNode points to itself

After these two lines, newNode.next == newNode. The old list is orphaned, and traversal loops forever.

The fix is to save the forward link before you move head:

// CORRECT: manual two-line form
Node<T> newNode = new Node<>(item);
newNode.next = head;   // 1. newNode aims at the old front
head = newNode;        // 2. now head moves to the new front

Arrow sketch (non-empty case, item = 5, existing front = 10):

Before:
  head --> [10 | next] --> [20 | null]

Step 1 (newNode.next = head):
  newNode [5 | next] --> [10 | next] --> [20 | null]
  head still --> [10 | next]

Step 2 (head = newNode):
  head --> [5 | next] --> [10 | next] --> [20 | null]

A two-argument constructor achieves the same result in one expression:

head = new Node<>(item, head);

Java evaluates the argument head before executing the assignment, so the old front is captured as the new node’s next automatically (JLS 15.26).

A complete addFirst method with the empty-list case:

public void addFirst(T item) {
    Node<T> newNode = new Node<>(item);
    newNode.next = head;   // works even when head is null
    head = newNode;
    size++;
}

Worked Example: Predict, Then Check

A list currently holds [3, 7] (head points to 3, which points to 7). You call addFirst(1). Trace the two correct steps and state the final order of elements.

A Common Mistake

The reversed-order bug assigns head = newNode before newNode.next = head. Once head has been overwritten, newNode.next = head sets newNode.next to newNode itself, creating a self-referential cycle. Any while (cur != null) loop will spin indefinitely because cur.next never becomes null. The fix is always to set newNode.next = head first, then move head. The two-argument constructor form avoids the problem entirely because Java evaluates arguments left to right before any assignment takes place. (Source: Liang 10e Ch 24)

Go Deeper (optional)

Both the manual two-step form and the constructor form run in O(1) time because no traversal is needed. If you are curious about why argument evaluation order guarantees safety in the constructor form, that rule comes from JLS 15.26 (assignment evaluation order). Later in the course you will see a dummy-head variant where a sentinel node sits permanently at the front of the list, which eliminates the empty-list special case entirely. Understanding why pointer order matters here will make that trade-off clear when you encounter it.

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.