Remove Duplicates from a Sorted Linked List in C

This program demonstrates how to remove duplicate elements from a sorted linked list using the C programming language. The solution provided maintains the order of elements and ensures that each value appears only once in the list.

Program Explanation

The program includes a linked list node structure and functions for creating nodes, inserting nodes to build a sorted list, removing duplicates, and displaying the list. The core functionality focuses on efficiently identifying and removing any consecutive duplicates from the sorted list.

• struct Node: Represents each node in the linked list.
• insertNode: Inserts new elements into the linked list in a sorted manner.
• removeDuplicates: Traverses the list and removes any duplicate nodes found.
• printList: Utility function to display the list.

Source Code

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Function to insert a node into the linked list in sorted order
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = newNode(new_data);
    struct Node* current;
    // Special case for head end
    if (*head_ref == NULL || (*head_ref)->data >= new_data) {
        new_node->next = *head_ref;
        *head_ref = new_node;
    } else {
        // Locate the node before point of insertion
        current = *head_ref;
        while (current->next != NULL && current->next->data < new_data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

// Function to remove duplicates from a sorted linked list
void removeDuplicates(struct Node* head) {
    struct Node* current = head;
    struct Node* next_next;
    if (current == NULL) return; // do nothing if the list is empty

    while (current->next != NULL) {
        if (current->data == current->next->data) {
            next_next = current->next->next;
            free(current->next);
            current->next = next_next;
        } else {
            current = current->next; // only advance if no deletion
        }
    }
}

// Function to print nodes in a given linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\\n");
}

int main() {
    struct Node* head = NULL;

    // Constructing the linked list
    insertNode(&head, 12);
    insertNode(&head, 11);
    insertNode(&head, 12);
    insertNode(&head, 21);
    insertNode(&head, 43);
    insertNode(&head, 43);
    insertNode(&head, 60);

    printf("Original List: ");
    printList(head);

    removeDuplicates(head);

    printf("Modified List: ");
    printList(head);

    return 0;
}
        

Conclusion

The provided C program efficiently removes duplicate entries from a sorted linked list. By maintaining pointers to the current and next nodes, it ensures that all duplicates are removed without leaving any behind, preserving the sorted order of the list and improving the list’s integrity.