Returning a Boolean Flag from removeAllOccurrences

Try This First

You call removeAllOccurrences("z") on the list [a, b, c]. The value "z" is not present anywhere.

What does the method return?

What You Need To Walk In With

• removeAllOccurrences walks the entire list and removes every node whose data equals the target value.
• A boolean flag, initialized to false, tracks whether any removal happened during the walk.
• The flag is set to true only inside the branch where an actual removal occurs, not unconditionally at every step.
• Returning size > 0 after the operation does not answer “did we change the list?” It answers “is the list non-empty?”, which is a different question.
• This return convention mirrors Collection.remove(Object) from the Java standard library: callers typically need to know only whether state changed, not how many items were removed.

How It Works

The key idea is a single local variable declared before the traversal begins:

boolean modified = false;

Every time a node is unlinked from the chain, you set:

modified = true;

At the end of the method, return modified;.

Here is a complete no-dummy-head implementation using a singly linked list with a head reference and a size field:

public boolean removeAllOccurrences(T value) {
    boolean modified = false;

    // Remove matching nodes at the front
    while (head != null && head.data.equals(value)) {
        head = head.next;
        size--;
        modified = true;
    }

    if (head == null) {
        return modified;
    }

    // Walk the rest: prev trails one behind current
    Node<T> prev = head;
    Node<T> current = head.next;

    while (current != null) {
        if (current.data.equals(value)) {
            prev.next = current.next;   // unlink current
            size--;
            modified = true;
            // prev stays; advance only current
        } else {
            prev = current;
        }
        current = current.next;
    }

    return modified;
}

Pointer sketch for a removal step (list [a, z, b], removing "z"):

Before:
  prev      current     current.next
  [a] ---> [z] -------> [b] ---> null

After:  prev.next = current.next
  prev                  current.next
  [a] ---------------> [b] ---> null
  [z] is unlinked; modified = true

The prev pointer does not advance when a node is removed because the new current.next might also match and needs to be checked against the same prev.

Worked Example: Predict, Then Check

List before the call: [a, z, b]

boolean r = list.removeAllOccurrences("z");

Trace through the method:

1. head.data is "a", not "z", so the front-removal loop does not fire.
2. prev = head (the "a" node), current = head.next (the "z" node).
3. current.data.equals("z") is true: prev.next = current.next (points to "b"), size--, modified = true.
4. current = current.next (now the "b" node).
5. current.data.equals("z") is false: prev = current (the "b" node), advance current.
6. current is now null; loop ends.
7. Return modified, which is true.

What are r and the list contents after the call?

A Common Mistake

A frequent error is initializing modified to true instead of false, or unconditionally setting it inside the loop body rather than only in the removal branch. If you write modified = true; after every loop iteration regardless of whether a node was removed, the method always returns true, even when the target value was never in the list. The caller then cannot trust the return value, so any code that branches on it (for example, “only rebuild an index if the list changed”) will execute needlessly. The fix is simple: keep the default at false and set it to true only inside the if-branch where prev.next = current.next actually happens. (Source: Liang 10e Ch 24)

Go Deeper (optional)

This method runs in O(n) time because it visits every node exactly once. The boolean flag adds no extra traversal cost. If you later study the Java Collections Framework, you will see that java.util.Collection.remove(Object) follows the same convention: it returns true only if the collection changed as a result of the call. That consistency matters when your list is used inside higher-level algorithms that rely on the return value to decide whether to proceed.

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.