The No-Dummy-Head Linked List: Head, Size, and Why They Are Enough

Try This First

A singly linked list stores head (a reference to the first node) and size (the count of nodes). The list is currently empty.

You call addFirst(42). After the call, what does head reference?

What You Need To Walk In With

• A no-dummy-head (NDH) list keeps exactly two fields: private Node<T> head; and private int size;.
• When the list is empty, head is null and size is 0.
• addFirst is O(1): it only touches the head reference, regardless of list length.
• addLast is O(n): it must walk every node from head until it finds the one whose next is null.
• Storing size as a field keeps size() O(1). Computing it on demand by walking the list would cost O(n) every call.

How It Works

The two-field skeleton looks like this:

public class LinkedList<T> {
    private Node<T> head;   // null when the list is empty
    private int size;       // always kept in sync with actual node count

    public LinkedList() {
        head = null;
        size = 0;
    }
}

addFirst places a new node before the current head. Because you only update one reference, the cost is always O(1):

public void addFirst(T data) {
    Node<T> newNode = new Node<>(data);
    newNode.next = head;   // new node points to old head (null if empty)
    head = newNode;        // head now points to the new node
    size++;
}

addLast must find the tail before it can link a new node. That walk is the source of the O(n) cost:

public void addLast(T data) {
    Node<T> newNode = new Node<>(data);
    if (head == null) {         // special case: empty list
        head = newNode;
    } else {
        Node<T> cur = head;
        while (cur.next != null) {
            cur = cur.next;     // walk until the last node
        }
        cur.next = newNode;     // link new node after the tail
    }
    size++;
}

A pointer sketch after addLast(30) on a list that already holds [10 -> 20]:

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

After addLast(30):
head --> [10 | *] --> [20 | *] --> [30 | null]
                                    ^
                              cur stops here; cur.next = newNode

Notice that addLast checks head == null before attempting cur.next. Without that guard, an empty list would produce a NullPointerException on the very first call.

Worked Example: Predict, Then Check

A list is built with these three calls in order:

list.addLast(1);
list.addFirst(0);
list.addLast(2);

Predict the order of elements from head to tail, and predict the value of size.

A Common Mistake

Forgetting the empty-list guard in addLast is the most frequent error. A student writes:

Node<T> cur = head;
while (cur.next != null) {   // BUG: cur is null when list is empty
    cur = cur.next;
}
cur.next = newNode;

When the list is empty, head is null, so cur starts as null. The expression cur.next immediately throws a NullPointerException. The fix is to check if (head == null) first and set head = newNode directly in that branch, then proceed with the walk only in the else branch. This pattern appears consistently across all quarter lab archives for the NDH list. (Source: Liang 10e Ch 24)

Go Deeper (optional)

Once you are comfortable with the basic NDH structure, consider the cost tradeoff more carefully. Every addLast call pays O(n) because you have no direct reference to the tail. One natural upgrade is to add a tail field alongside head, which reduces addLast to O(1) as well. That variant is covered in a later concept. Another future topic, the dummy-head design, eliminates the empty-list special case by keeping a permanent sentinel node before the first real element. Both improvements build directly on the NDH foundation you have here.

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.