Removing Every Occurrence: The While-Skip Pattern

Try This First

You have the list [a, a, b, a] and you call removeAllOccurrences("a"). Without writing any code, trace what the list looks like after each removal. How many pointer changes happen, and what is in the list at the end?

What You Need To Walk In With

• A singly linked list stores a head reference and a size counter. There is no sentinel or dummy node. When the list is empty, head is null.
• Removing a node means setting prev.next = prev.next.next, which bypasses the target node entirely.
• Equality for generic data is tested with .compareTo(data) == 0, not ==.
• The very first node (the head) has no prev, so it must be handled as a special case before the general walk.
• When consecutive duplicates exist, advancing the pointer after a removal causes you to skip the node that just moved into position, so removal and advancement are mutually exclusive actions.

How It Works

The method uses two phases. Phase one clears any matches at the front. Phase two walks the rest of the list and bypasses each match it encounters.

Phase one: clean the head

Because there is no dummy node, head is a real data node. If it matches, shift head to head.next and repeat until head is either null or a non-matching node.

Phase two: walk and skip

Use a prev pointer that always points to the last node you decided to keep. Check prev.next: if it matches, relink around it (prev.next = prev.next.next) and do not advance prev. If it does not match, advance prev = prev.next. The “do not advance on removal” rule is what prevents consecutive duplicates from slipping through.

public boolean removeAllOccurrences(final T data) {
    if (data == null) throw new IllegalArgumentException("data must not be null");
    boolean modified = false;

    // Phase 1: remove matching nodes at the head
    while (head != null && head.data.compareTo(data) == 0) {
        head = head.next;
        size--;
        modified = true;
    }

    // Phase 2: walk and skip matching nodes in the remainder
    Node<T> prev = head;
    while (prev != null && prev.next != null) {
        if (prev.next.data.compareTo(data) == 0) {
            prev.next = prev.next.next;   // bypass the match
            size--;
            modified = true;
            // do NOT advance prev: the node now at prev.next is new and unexamined
        } else {
            prev = prev.next;             // safe to advance only on a non-match
        }
    }

    return modified;
}

A pointer sketch for the walk phase with [b, a, c] and target "a":

before removal:
  prev       prev.next    prev.next.next
   |              |              |
  [b]  -->  [a]  -->  [c]  --> null

after prev.next = prev.next.next:
  prev       (bypassed)
   |                    |
  [b]  ------------> [c]  --> null

prev stays at [b] after the bypass. On the next iteration it checks [c], which does not match, so prev advances there and the loop ends.

Worked Example: Predict, Then Check

Consider list = [a, a, a] and removeAllOccurrences("a").

Predict: what is in the list after the call, and what does the method return?

A Common Mistake

A common error is always advancing prev after each iteration, even when a removal just happened:

// WRONG
if (prev.next.data.compareTo(data) == 0) {
    prev.next = prev.next.next;
    size--;
    modified = true;
}
prev = prev.next;   // advances even after removal

After the bypass, prev.next now points to a node that was never checked. Advancing prev immediately skips that node on the next iteration. If two matching nodes appear consecutively, the second one survives the traversal and the method returns a corrupted list. The fix is to move prev = prev.next into an else branch so it only runs when no removal occurred. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The while-skip pattern runs in O(n) time because each node is visited at most once, regardless of how many matches exist. If you later study dummy-head linked lists, you will find that the two-phase split disappears entirely: a sentinel node before the real head means every data node always has a predecessor, so the walk pattern handles all positions uniformly. The course teaches the no-dummy-head form first so you can see exactly why the head case needs special treatment.

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.