Here we’ll see how to write C program to remove duplicate entries from linked list. Linked list contains duplicate entries when nodes with same value appear multiple times in the list.
In the above Linked list entries, 43, 24 and 5 appeared more than once. We’ll write a C program to remove these duplicate elements such that they appear only once in the resulted linked list along with other non-duplicate elements. Another important thing, the order of the elements will remain intact in the resulted linked list. The result will look like this.
C Program to Remove Duplicate Entries from Linked List
#include <stdio.h>
#include <stdlib.h>
struct node{
int val;
struct node *next;
};
void print_list(struct node *head)
{
printf("H->");
while(head)
{
printf("%d->", head->val);
head = head->next;
}
printf("|||\n");
}
void insert_front(struct node **head, int value)
{
struct node * new_node = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("Failed to insert element. Out of memory");
}
new_node->val = value;
new_node->next = *head;
*head = new_node;
}
void delete_node(struct node **head, struct node *node)
{
struct node *tmp = NULL;
if (head == NULL || *head == NULL) return;
if(*head == node)
{
/*Delete the head node*/
*head = (*head)->next;
free(node);
return;
}
tmp = *head;
while(tmp->next && tmp->next != node) tmp = tmp->next;
if(tmp->next)
{
tmp->next = tmp->next->next;
free(node);
}
else
{
printf("Node not found in the list.\n");
}
}
void remove_duplicate(struct node *head)
{
struct node *tmp = NULL;
struct node *tmp1 = NULL;
struct node *tmp2 = NULL;
if (head == NULL) return;
tmp = head;
while(tmp)
{
tmp1 = tmp->next;
while(tmp1)
{
tmp2 = tmp1;
tmp1 = tmp1->next;
if(tmp->val == tmp2->val) delete_node(&head, tmp2);
}
tmp = tmp->next;
}
}
void main()
{
int count = 0, i, val;
struct node * head = NULL;
printf("Enter number of elements: ");
scanf("%d", &count);
for (i = 0; i < count; i++)
{
printf("Enter %dth element: ", i);
scanf("%d", &val);
insert_front(&head, val);
}
printf("Initial List: ");
print_list(head);
remove_duplicate(head);
printf("List after removing duplicate entries: ");
print_list(head);
}
Output of the Program
If you run the program the output would look like
Enter number of elements: 8 Enter 1th element: 43 Enter 2th element: 24 Enter 4th element: 5 Enter 5th element: 5 Enter 6th element: 24 Enter 7th element: 65 Enter 8th element: 43 Enter 9th element: 6 Initial List: H->6->43->65->24->5->5->24->43->||| List after removing duplicate entries: H->6->43->65->24->5->|||
Explanation of the Program
The program takes input from user to construct the linked list. The user needs to enter some duplicate entries to see the affect. The remove_duplicate() function is used to remove duplicate entries from the linked list passed as argument.
void remove_duplicate(struct node *head)
{
struct node *tmp = NULL;
struct node *tmp1 = NULL;
struct node *tmp2 = NULL;
if (head == NULL) return;
tmp = head;
while(tmp)
{
tmp1 = tmp->next;
while(tmp1)
{
tmp2 = tmp1;
tmp1 = tmp1->next;
if(tmp->val == tmp2->val) delete_node(&head, tmp2);
}
tmp = tmp->next;
}
}
Logic is simple. The outer loop takes a node in every iteration starting from the first node and compares its value will rest of the right nodes in the list. If the value of any other node matches with outer loop node, the inner loop deletes that node from the linked list. The delete_node() function is used to delete the node. When the outer loop reaches end of the linked list, the linked list becomes duplicate entry free. The time complexity of the remove_duplicate() function is O(n2).
