Head and Tail: The Doubly-Anchored Linked List

Try This First

A singly linked list stores only a head reference. Adding a new node at the end costs O(n) because you have to walk every node to find the last one.

What single field addition changes addLast from O(n) to O(1), and what new responsibility does that field introduce?

What You Need To Walk In With

• A linked list with only head must walk all n nodes to add at the end: O(n).
• Adding a tail field gives O(1) access to the last node for addLast and (on a doubly linked variant) removeLast.
• The DH (Doubly-Headed) convention declares three fields: head, tail, and size.
• An empty DH list maintains the invariant head == null and tail == null and size == 0.
• Any operation that changes the last node (addLast, removeLast, clear, a remove that hits the only element) must update tail.

How It Works

The DH convention names come from adding a second anchor to the front-only design. The field declaration looks like this:

private Node<T> head;
private Node<T> tail;
private int size;

addLast: the payoff

Without a tail reference you walk from head until current.next == null. With tail you skip straight to the end:

public void addLast(T data) {
    Node<T> newNode = new Node<>(data, null);
    if (head == null) {         // empty list: both anchors point to the one node
        head = newNode;
        tail = newNode;
    } else {
        tail.next = newNode;    // wire the old last node forward
        tail = newNode;         // advance the tail anchor
    }
    size++;
}

Pointer picture after adding “C” to a list that already holds “A” -> “B”:

Before:
  head --> [A] --> [B] --> null
  tail ---------> [B]

After addLast("C"):
  head --> [A] --> [B] --> [C] --> null
  tail -----------------------> [C]

removeLast: the bookkeeping cost

tail gives fast access to the last node, but removing it still requires walking to the predecessor so you can set predecessor.next = null. The critical extra step is updating tail:

public T removeLast() {
    if (head == null) throw new NoSuchElementException();
    T data;
    if (head == tail) {         // only one node
        data = head.data;
        head = null;
        tail = null;            // both anchors must go null
    } else {
        Node<T> current = head;
        while (current.next != tail) {
            current = current.next;
        }
        data = tail.data;
        current.next = null;
        tail = current;         // advance tail backward to the new last node
    }
    size--;
    return data;
}

clear: reset both anchors

public void clear() {
    head = null;
    tail = null;
    size = 0;
}

The invariant after clear() is that head == null and tail == null. Leaving tail pointing to the old last node is a bug (see the common mistake below).

Worked Example: Predict, Then Check

A DH list currently holds three integers in order: 10, 20, 30. head points to the node with 10; tail points to the node with 30.

You call removeLast().

Predict: what does tail point to after the call returns?

A Common Mistake

When removeLast runs on a list with exactly one node, you null out head but forget to null out tail. The code continues to point tail at the removed node object. The list now reports head == null (empty), but tail still references old data. The next call to addLast executes the else branch, writes to tail.next on a garbage node, and silently corrupts the list.

The fix is simple: whenever size drops to zero, set both head and tail to null. The invariant is that an empty list has head == null and tail == null, no exceptions. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The O(1) addLast that tail enables is exactly what makes a linked list efficient as a queue: enqueue at the tail in O(1), dequeue at the head in O(1). The no-dummy-head form you see here is the foundation; some courses introduce a sentinel (dummy) head node to eliminate the empty-list special case in every method. That approach trades the null checks for an extra node that is never removed. You will see that pattern labeled “DH” in older 211 labs from the F17 and SP18 quarters.

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.