Append: Walking to the Tail

Try This First

You have a three-element list: [A] -> [B] -> [C] -> null. You call add("D"). What does cur point to when the while loop exits?

What You Need To Walk In With

• A singly linked list with no dummy head has a head reference (possibly null) and a size field.
• When head == null the list is empty; any traversal must be guarded by checking for this case first.
• To reach the last node you walk forward one step at a time: cur = cur.next until cur.next == null.
• The walk takes O(n) time because it visits every node in a list of length n.
• Attaching a new node means setting the current tail’s next reference to the new node; then size increases by one.

How It Works

Appending to the tail in a no-dummy-head list has two distinct situations.

Empty list. When head == null there is no chain to walk. The new node becomes the head directly.

Non-empty list. Start a cursor at head and advance it one step at a time. The stopping condition is cur.next != null becoming false, which means cur is sitting on the last node. You attach the new node by writing cur.next = new Node<>(item).

public void add(final T item) {
    if (item == null) throw new IllegalArgumentException("item cannot be null");
    if (head == null) {
        head = new Node<>(item);   // empty-list special case
    } else {
        Node<T> cur = head;
        while (cur.next != null) {
            cur = cur.next;        // advance one step
        }
        // cur is now the last node
        cur.next = new Node<>(item);
    }
    size++;
}

Arrow sketch of the walk on [A -> B -> C] before the new node arrives:

head
 |
[A] -> [B] -> [C] -> null
                ^
               cur  (loop exits here because cur.next == null)

After: cur.next = [D]

[A] -> [B] -> [C] -> [D] -> null

Worked Example: Predict, Then Check

Start with an empty list. You call add("X"), then add("Y"), then add("Z"). After all three calls, what is the value of head.next.next.data?

A Common Mistake

A common error is writing while (cur != null) instead of while (cur.next != null). When cur != null becomes false, cur is null, so the line cur.next = new Node<>(item) immediately throws a NullPointerException. You have walked one step too far and lost the reference to the last node. The fix is to stop one step earlier: while (cur.next != null) ensures that when the loop exits, cur is still pointing at the last node and you can attach to it. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The O(n) cost of append becomes significant when you call it inside a loop to build a large list. A dummy-head design that also stores a tail reference bypasses the walk entirely, making append O(1). That trade-off is worth revisiting after you are comfortable with the no-dummy-head form covered here. The walk pattern itself, starting a cursor at head and advancing until a condition on cur.next is met, reappears in many other linked-list operations, so the time spent understanding it here pays off repeatedly.

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.