Remove Duplicates from a Sorted Doubly Linked List

This chapter covers the algorithmic approach to removing duplicate elements from a sorted doubly linked list (DLL). Because the list is already sorted, all identical values are guaranteed to appear in a contiguous block, allowing us to traverse and prune duplicates efficiently in a single pass without extra memory overhead.

1. Why Do We Need This? (Problem Statement & Status Quo)

When dealing with data streams, database query results, or deserialized lists, sorted doubly linked lists can often accumulate contiguous duplicate nodes. Leaving these duplicates wastes memory and degrades downstream processing performance.

• The Objective: Given the head pointer of a sorted doubly linked list, remove all duplicate nodes such that each unique value appears only once.
• The Output: Return the head of the modified doubly linked list.
• Key Observation: Because the list is sorted, any identical values will always be adjacent (contiguous) to one another. They will never be scattered randomly across the list.

2. Core Mental Model & The Contiguity Property

Real-Life Analogy: The Sorted Line of People

Imagine a line of people arranged strictly by height (or alphabetical order of their last names). If multiple people share the exact same height, they will naturally end up standing right next to each other.

• You do not need to walk down the entire line to check if someone far away shares a height.
• You can stand at the first person of a specific height, look immediately to your right, skip over all the identical copies until you hit someone of a different height, and then bridge the gap directly from the first person to that new person.

3. Naive vs. Optimal Approach

The Naive Approach

• Compare every single node with every other node using a nested loop structure ($O(n^2)$ time complexity).
• Inefficient and completely ignores the structural advantage provided by the sorted nature of the linked list.

The Optimal Pointer-Skipping Approach

• Utilize a single outer traversal pointer (temp) starting at the head.
• Utilize an inner pointer (next node) to scan forward and locate the first node with a distinct (non-equivalent) value.
• Re-wire the pointers (temp->next and next_node->prev) to bypass the entire block of duplicates in $O(1)$ pointer operations.

4. Step-by-Step Evolution of the Algorithm

1. Initialize temp at head: We never modify the head pointer directly because the first element will never be deleted (it is the first occurrence of its value).
2. Scan for Duplicates: From temp, set a next_node pointer to temp->next. Advance next_node forward as long as:
   • next_node is not null, AND
   • next_node->data == temp->data
3. Re-wire Pointers: Once next_node lands on the first element that does not match temp->data, bridge the gap:
   • temp->next = next_node
   • If next_node is valid (not null), set next_node->prev = temp
4. Advance temp: Move temp = temp->next to repeat the process for the next unique value.
5. Termination Condition: Stop when temp reaches null or when temp->next reaches null (meaning no further elements exist to check).

5. Visual Flow Walkthrough

Let us trace the algorithm on the list: 1 <-> 1 <-> 1 <-> 2 <-> 3 <-> 3 <-> 4

6. Pseudocode Implementation

Function removeDuplicates(head):
    If head is NULL:
        Return NULL

    temp = head

    While temp is not NULL and temp.next is not NULL:
        next_node = temp.next

        // Find the first node whose data does not match temp's data
        While next_node is not NULL and next_node.data == temp.data:
            next_node = next_node.next

        // Bridge the gap between temp and the first non-duplicate node
        temp.next = next_node

        If next_node is not NULL:
            next_node.prev = temp

        // Move temp forward for the next iteration
        temp = temp.next

    Return head

7. Language-Specific Considerations: Memory Management (C++ vs. Java/Python)

Note: In managed runtime environments like Java, Python, or JavaScript, the built-in garbage collector automatically reclaims memory for unreferenced duplicate nodes once their pointers are severed. However, in unmanaged languages like C++, you must explicitly free the memory to prevent memory leaks.

C++ Deallocation Snippet

Node* removeDuplicates(Node* head) {
    if (!head) return nullptr;

    Node* temp = head;
    while (temp != nullptr && temp->next != nullptr) {
        Node* next_node = temp->next;

        // Traverse and delete duplicates
        while (next_node != nullptr && next_node->data == temp->data) {
            Node* duplicate = next_node;
            next_node = next_node->next;
            delete duplicate; // Explicitly free memory in C++
        }

        temp->next = next_node;
        if (next_node != nullptr) {
            next_node->prev = temp;
        }

        temp = temp->next;
    }
    return head;
}

8. Complexity Analysis

9. Summary and Key Takeaways

• Sorted List Advantage: Contiguous grouping of duplicates in sorted doubly linked lists allows $O(N)$ single-pass removal without extra memory buffers.
• Pointer Preservation: Always keep a reference to head intact; start traversals using a temporary pointer (temp = head).
• Inner Scanning: Use an inner pointer (next_node) to fast-forward through duplicate clusters until the first non-matching value is encountered.
• Bidirectional Linking: Remember to update both forward (temp->next) and backward (next_node->prev) pointers during the re-wiring phase.
• Null Safety: Always check if next_node is not null before attempting to access or mutate next_node->prev.
• Memory Management: Free unlinked duplicate nodes explicitly when working in languages without automatic garbage collection (such as C++).