addFirst: Wiring the New Node onto the Front

Try This First

You have a list that currently holds [10, 20]. Your code calls addFirst(5). Without reading further, draw the three Node boxes and the arrows after the call completes. Which reference changes, and which stays the same?

What You Need To Walk In With

• head is the single reference that anchors the chain. When head == null, the list is empty.
• Every new node holds two fields: a data value and a next reference.
• Inserting at the front is O(1) because you only touch head, never walk the chain.
• Every mutation must update size so that size() stays accurate.
• The method must reject null input with an IllegalArgumentException before touching the list.

How It Works

addFirst prepends a new element. The same two-statement logic handles both the empty list and the non-empty list uniformly.

public void addFirst(final T item) {
    if (item == null) {
        throw new IllegalArgumentException("item cannot be null");
    }
    head = new Node<>(item, head);  // new node's next = old head (null when empty)
    size++;
}

The key move is new Node<>(item, head). The two-argument Node constructor sets the new node’s next to whatever head currently is.

• Empty list (head == null): the new node’s next is null, which is correct for a single-element list.
• Non-empty list (head != null): the new node’s next points to the former first node, preserving the rest of the chain.

Either way, head is then reassigned to the new node, and size is incremented.

Before addFirst(5)   [10] -> [20] -> null    head -> [10]

Step 1: nn = new Node(5, head)
         nn.next = [10]

Step 2: head = nn
         head -> [5] -> [10] -> [20] -> null

size: 2 -> 3

No special branch on “empty vs non-empty” is needed because head == null is a valid value for next.

Worked Example: Predict, Then Check

MyLinkedList<Integer> list = new MyLinkedList<>();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);

What does the list contain from front to back after all three calls?

A Common Mistake

Some implementations add the node but skip the size++ line. The node is physically in the chain, so the list appears to work when you walk it manually. But size() now returns a stale count. Any code that loops with for (int i = 0; i < list.size(); i++) will either terminate too early or produce off-by-one behavior depending on the loop direction. The fix is simple: every method that adds or removes a node must pair that change with a size++ or size--. Make it a habit to write the size update on the very next line after the pointer assignment so you cannot forget it. (Source: Liang 10e Ch 24)

Go Deeper (optional)

addFirst runs in O(1) time regardless of how long the list is, which is one of the structural advantages of a linked list over an array-backed list where prepending requires shifting every element right. If you later study a dummy-head (DH) variant of this class, the logic is nearly identical except that you insert after the sentinel node rather than directly at head. In that variant you also need to update a tail reference when the list was previously empty. That comparison is worth revisiting after you are comfortable with the no-dummy-head form you are building now.

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.