Choosing Between No-Dummy-Head and Dummy-Head Lists

Try This First

You are building a print queue: jobs arrive at the back and leave from the front. You have two list designs available. Which one gives you O(1) time at both ends?

What You Need To Walk In With

• The no-dummy-head (NDH) list stores a head reference and a size field. Every method that touches the first node must special-case head == null and must update head directly.
• The dummy-head (DH) list adds a permanent sentinel node at position 0 and a tail reference pointing at the last real node. Neither head nor tail ever becomes null after construction.
• NDH addFirst and removeFirst are O(1). NDH addLast and removeLast are O(n) because the list must walk to the end.
• DH addLast is O(1) because tail already points at the last node. That one field change is the whole tradeoff.
• The CSCD 211 lab sequence (Lab 5 then Lab 6) builds NDH first, then upgrades to DH, so the cost difference is visible in your own code.

How It Works

The core question is: which end of the list is “hot”?

NDH is the right fit when only one end is active. A stack pushes and pops at the front. NDH addFirst and removeFirst both run in O(1), and the sentinel node would carry no benefit because tail is never touched. Here is a minimal NDH addFirst:

// NDH -- no sentinel, no tail field
public void addFirst(T element) {
    Node<T> newNode = new Node<>(element);
    newNode.next = head;   // new node points at old head (null if list is empty)
    head = newNode;        // head is updated directly
    size++;
}

The empty-list case is built in: when head == null, newNode.next = null and head = newNode is correct with no extra branch.

DH is the right fit when both ends must be O(1). A queue dequeues from the front and enqueues at the back. The tail reference is what makes O(1) addLast possible:

// DH -- sentinel at position 0, tail points at last real node
public void addLast(T element) {
    Node<T> newNode = new Node<>(element);
    tail.next = newNode;   // splice after current tail
    tail = newNode;        // advance tail to the new last node
    size++;
}

An arrow sketch of the two states:

NDH (stack, 3 elements):
head --> [A] --> [B] --> [C] --> null

DH (queue, 3 elements):
head --> [dummy] --> [A] --> [B] --> [C] --> null
                                     ^
                                    tail

In the DH picture, adding a new element at the back touches only tail.next and tail. No traversal is needed.

Summary rule: if your usage touches only the front (or only the back), NDH is simpler. If your usage touches both ends and one of them must be O(1), add the tail field and use DH.

Worked Example: Predict, Then Check

A stack class uses an NDH singly linked list. It calls push(1), push(2), push(3). A classmate suggests switching to DH to “make it better.” What is the concrete benefit of that change for a stack?

A Common Mistake

A student builds a text-editor undo queue that must add undo records at the back and consume them from the front, then uses NDH. The code works correctly but slows down noticeably as the undo history grows. The problem is that NDH addLast walks the entire list to find the last node, giving O(n) per enqueue. With 1 000 records queued, each new undo entry triggers 1 000 pointer dereferences. The fix is to switch to DH: the tail field makes addLast O(1) at the cost of one extra field and one extra node. For any queue-shaped usage, DH is the deliberate design choice, not a cosmetic upgrade. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The O(n) versus O(1) difference at the back of the list is the only reason DH exists for singly linked lists. If you are curious about the cost model, try timing NDH addLast on lists of 100, 1 000, and 10 000 elements: the time should scale linearly. DH addLast stays flat across all three. This Big-O intuition carries directly into the Java standard library: java.util.LinkedList keeps both a first and a last reference for exactly the same reason.

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.