Remove duplicates from an unsorted Linked List
Remove duplicates from an unsorted Linked List
This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will remove duplicates from the given linked list.
Example: Ifthe given linked list is 4 -> 1 -> 1 -> 5 -> 2 then the output will be 4 -> 1 -> 5 -> 2.
Here, we will see the ways to remove duplicates from the linked list.
Method 1: Using 2 - Loops
This method will use two loops to remove duplicates. The first loop will pick the linked list elements one by one, and the second loop will compare the picked element with other elements of the linked list.
Source code to implement method 1 in C language:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *next;
};
struct node *start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node *t, *p;
t = (struct node *)malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node *p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For removing the duplicated from the linked list
void removeDuplicates(struct node * t)
{
struct node *p1, *p2, *temp;
p1 = t;
/* Pick elements one by one */
while (p1 != NULL && p1->next != NULL)
{
p2 = p1;
while (p2->next != NULL)
{
if (p1->info == p2->next->info)
{
temp = p2->next;
p2->next = p2->next->next;
}
else
p2 = p2->next;
}
p1 = p1->next;
}
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ",t -> info);
t = t -> next;
}
printf("%d",t -> info);
}
// Driver Function
int main()
{
add(10);
add(4);
add(2);
add(9);
add(2);
removeDuplicates(start);
traverse(start);
return 0;
}
Output: -
Time Complexity: O(n^2)
Method 2: Using Hashing
This method will use the HashSet to remove duplicates. It will first traverse the linked list from head to tail and check every element of the linked list whether it is present in the HashSet or not. If it finds duplicates, we remove them. Otherwise, it will put them into the HashSet.
Source code to implement method 2 in Java:
import java.util.*;
public class removeDuplicates
{
static class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
next = null;
}
}
/* Function to remove duplicates from an unsorted linked list */
static void removeDuplicate(Node head)
{
// Hash to store seen values
HashSet<Integer> hs = new HashSet<>();
/* Pick elements one by one */
Node temp = head;
Node prev = null;
while (temp != null)
{
int v = temp.data;
if (hs.contains(v)) {
prev.next = temp.next;
}
else
{
hs.add(v);
prev = temp;
}
temp = temp.next;
}
}
/* Function to print nodes in a given linked list */
static void traverse(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the total no of elements");
int t = sc.nextInt();
int a1= sc.nextInt();
Node head= new Node(a1);
Node tail = head;
for (int i = 1; i < t; i++)
{
int a = sc.nextInt();
tail.next = (new Node(a));
tail = tail.next;
}
System.out.println("Linked list before removing duplicates :");
traverse(head);
removeDuplicate(head);
System.out.println("\nLinked list after removing duplicates :");
traverse(head);
}
}
Output: -
Time Complexity: O(n)