compareTo vs equals: Choosing the Right Match Test

Try This First

A linked list node holds a String. Inside removeAllOccurrences you write:

if (cur.data.compareTo(data) == 0)

A classmate writes:

if (cur.data.equals(data))

Both compile. Both produce identical results for normal strings.

Before reading: what is the one structural difference between the two lines that matters most to the class declaration?

What You Need To Walk In With

• S20 Lab 5 declares the linked list as LinkedList<T extends Comparable<? super T>>. That bound means every T stored in the list is guaranteed to have a compareTo method.
• cur.data.compareTo(data) == 0 means “equal under the natural ordering.” Per the Comparable contract, this result should agree with .equals for well-behaved types.
• cur.data.equals(data) works for any T and does not require the Comparable bound. It is the simpler choice when ordering is not needed elsewhere.
• The lab uses compareTo as a pedagogical move: it shows why the bound exists and makes the bound concrete rather than abstract.
• A null element in cur.data would cause a NullPointerException on either call. The lab spec prevents nulls at insertion (addFirst and add throw IllegalArgumentException on null), so by invariant cur.data is never null.

How It Works

The linked list class declaration in S20 Lab 5 is:

public class LinkedList<T extends Comparable<? super T>>

The bound T extends Comparable<? super T> says: every type argument T must implement Comparable of itself (or a supertype). This allows any method in the class to call compareTo on a stored value.

Inside removeAllOccurrences, the traversal checks each node:

public void removeAllOccurrences(final T data) {
    // empty list: nothing to do
    if (head == null) {
        return;
    }

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

    // traverse the rest, removing matches from interior / tail
    if (head != null) {
        Node<T> cur = head;
        while (cur.next != null) {
            if (cur.next.data.compareTo(data) == 0) {
                cur.next = cur.next.next;
                size--;
            } else {
                cur = cur.next;
            }
        }
    }
}

The match test is cur.next.data.compareTo(data) == 0. Replacing this with cur.next.data.equals(data) changes nothing for types like String and Integer, where compareTo == 0 and equals agree. The structural difference is only in the class declaration: equals works without the bound, while compareTo requires it.

A pointer sketch of what happens when the front node matches:

Before:  head -> [A] -> [B] -> [C]    (removing "A")
         head.data.compareTo("A") == 0  =>  true
After:   head -> [B] -> [C]
         head now points past the old front node

Worked Example: Predict, Then Check

A LinkedList<String> contains: "cat" -> "dog" -> "cat" -> null. Size is 3. You call removeAllOccurrences("cat").

Trace through the method above. After the call, what does the list contain and what is size?

A Common Mistake

Using compareTo when the class does not declare the bound.

If someone copies the compareTo match test into a class declared as LinkedList<T> (no bound), the compiler rejects it: T has no compareTo method. The fix is to either add the bound (<T extends Comparable<? super T>>) or switch the test to .equals. The choice is not arbitrary: if the class uses ordering anywhere else (sorting, finding min/max), the bound already belongs there and compareTo is the natural match. If ordering is never needed, .equals keeps the class more general. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The Comparable contract recommends that compareTo == 0 and equals agree, but it does not require it. A pathological example is a custom type that compares case-insensitively in compareTo but uses exact-case equality in equals. For such a type, removeAllOccurrences("Cat") would remove "cat" nodes under the compareTo test but leave them under equals. Stu’s labs use standard library types where the two always agree, so this distinction is theoretical here. The cost of removeAllOccurrences is O(n): every node is visited exactly once.

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.