
Introduction
In this blog, we will learn to remove duplicates from an unsorted Doubly Linked List.So let's suppose we have a doubly-linked list, and it may or may not contain some duplicate nodes. Now we have to remove all the duplicate nodes from this link list such that we keep the first occurrence of each node and preserve the original order of nodes. For example-
Given linked list- 9 7 7 7 8 4 5
After removing duplicates from the unsorted linked list- 5 4 8 7 9
To remove duplicates from an unsorted doubly-linked list, we will start with the naive approach in which we use two loops. One for traversing the linked list and the other for skipping over the repeated elements, but it is not the most efficient approach. Then we will discuss the optimal approach in which we use a map to keep track of the visited nodes, then traverse through the list and check for each node. If it has been visited, we ignore it, else we print it and mark it as visited.
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm
The basic approach
The naive approach to remove duplicates from an unsorted doubly-linked list is to iterate through the doubly-linked list, and for each node, first print the node then check all the remaining nodes if there are duplicates or not. If yes, then delete the duplicates. Let’s see the algorithm and implementation of this approach.
Algorithm
- Take the doubly linked list from user input-
- Iterate through the doubly linked list and for each node-
- - Print the node
- - Run another loop that compares the current node with the remaining nodes-
- - If any duplicates are found, delete them.
- - Else continue traversing through the list.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
//Structure for a node in the linked list.
struct node
{
int data;
struct node *next;
struct node *prev;
};
//Function to push nodes into the list.
void push(struct node** headr, int newval)
{
//Creating a new node.
struct node* newnode=(struct node*)malloc(sizeof(struct node));
//Putting the value in the node.
newnode->data= newval;
//Linking the node to the list.
newnode->prev=nullptr;
newnode->next=(*headr);
//Shifting the head pointer to the new node.
if((*headr)!=nullptr)
{
(*headr)->prev= newnode;
}
//Updating the head to the new node.
(*headr)=newnode;
}
//Function to delete a node.
void todeletenode(struct node** headr, struct node* todelete)
{
//If the node is null.
if(*headr==nullptr||todelete==nullptr)
{
return;
}
//Special case for the head nodes.
if(*headr==todelete)
{
*headr=todelete->next;
}
//Changing the next pointer of the nodes, only if it is not
//the last node.
if(todelete->next!=nullptr)
{
todelete->next->prev=todelete->prev;
}
//Changing the prev pointer of the nodes, only if it is not
//the head node.
if(todelete->prev!=nullptr)
{
todelete->prev->next=todelete->next;
}
//Free the memory.
free(todelete);
}
//Function to remove duplicates.
void removeduplicates(node** headr)
{
//When the linked list is empty or contains just one element.
if((*headr)==nullptr||(*headr)->next==nullptr)
{
return;
}
//Traversing through the linked list.
struct node* temp1, *temp2;
for(temp1=*headr;temp1!=nullptr;temp1=temp1->next)
{
temp2=temp1->next;
//To compare the element with the rest of the linked list.
while(temp2!=nullptr)
{
//To delete the duplicate elements, if found.
if(temp1->data==temp2->data)
{
//Preserving the next pointer of the node to be
//deleted.
struct node* curr=temp2->next;
//Calling the delete function.
todeletenode(headr, temp2);
temp2=curr;
}
//When we don't have duplicates.
else
{
temp2=temp2->next;
}
}
}
}
//Driver function.
int main()
{
//Creating an empty list.
struct node* head=nullptr;
//Enter no of nodes in the linked list.
int size;
cout<<"Enter the number of nodes in the list- ";
cin>>size;
//Pushing the nodes in it.
cout<<"Enter the nodes in the list- ";
for(int i=0;i<size;i++)
{
int a;
cin>>a;
push(&head,a);
}
//To remove duplicates from an unsorted doubly linked list.
removeduplicates(&head);
//Printing the linked list.
while(head!=nullptr)
{
cout<<head->data<<" ";
head=head->next;
}
return 0;
}
Input-
8
7 5 9 9 9 6 9 5
Output-
Enter the number of nodes in the list-
Enter the nodes in the list-
5 9 6 7
Complexity Analysis
The time complexity of this approach is- O(N2), where N is the number of nodes in the linked list.
The space complexity of this approach is- O(1).