Java LinkedList duplicate removal: first and last occurrence

Last updated: 30 Sept 20264 min read

tutorial

LinkedList can remove the first or last equal element, and those choices produce different order-preserving results when duplicates exist.

This complete Java 8 program has a checked output. Compile it as the named public class, then run it without additional libraries.

Define which duplicate is retired

A receipt feed may contain two events with the same code separated by another event. removeFirstOccurrence removes the earlier one; removeLastOccurrence removes the later one. Neither method is an idempotent record-key policy by itself, because equality may cover fewer fields than the domain's identity.

Both operations scan to find a match. LinkedList removes a known node cheaply after locating it, but lookup is still linear. A map or set with a stable key is a better fit when repeated membership checks dominate.

Check the return value

The boolean reports whether an equal value was found and removed. A false result should not be reported as successful cleanup if the caller expected a pending item. The fixture compares the remaining order after each operation.

Working program

import java.util.LinkedList;
import java.util.Arrays;
public class ReceiptDuplicateRetirement {
    public static void main(String[] args) {
        LinkedList<String> events = new LinkedList<>(Arrays.asList("R-9", "R-10", "R-9"));
        System.out.println("first=" + events.removeFirstOccurrence("R-9") + " " + events);
        events.addFirst("R-9");
        System.out.println("last=" + events.removeLastOccurrence("R-9") + " " + events);
        System.out.println("missing=" + events.removeLastOccurrence("R-11"));
    }
}

Output

first=true [R-10, R-9]
last=true [R-9, R-10]
missing=false

Costs and boundaries

Each occurrence search takes O(n) time and O(1) auxiliary space; the existing list retains O(n) nodes. The call is not a transactional deduplication operation.

Common Mistakes

Do not ignore a false removal result when absence is an error.
Do not confuse object equality with a business event identifier.
Do not sell fast relinking as fast value lookup.