How to remove duplicates from an unsorted doubly linked list

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.

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

  1. Take the doubly linked list from user input-
  2. Iterate through the doubly linked list and for each node-
  3.  - Print the node
  4.  - Run another loop that compares the current node with the remaining nodes-
  5.      - If any duplicates are found, delete them.
  6.      - 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). 

Solution using maps

We can find the optimal solution to this problem using an unordered map. It is used to keep track of the visited nodes. We traverse through the doubly linked list, and for each node, we check if it is visited or not. If it is visited, we move on to the next node. If it is not visited, we print the node and mark the node as visited. 

Algorithm

  1. Take the doubly linked list from user input-
  2. Create a map that takes node data and boolean variables as key-value pairs.
  3. Traverse through the doubly linked list for each node check if it is present in the map or not-
  4. If No, print it and mark it as visited on the map.
  5. Else move on to the next node.

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.
    if((*headr)==nullptr)
    {
        return;
    }
    //Creating an unordered set to track the visited nodes.
    unordered_set<int> tracknodes;
    //Traversing through the linked list.
    struct node* temp1=*headr, *temp2;
    while(temp1!=nullptr)
    {
        //If the node is already visited.
        if(tracknodes.find(temp1->data)!=tracknodes.end())
        {
            //Store the next pointer of the duplicate to
            //delete the node from the linked list, and update
            //the iterator to the next node.
            temp2=temp1->next;
            todeletenode(headr, temp1);
            temp1=temp2;
        }
        else
        {
            //If the node is not visited, mark it as visited and
            //update the iterator.
            tracknodes.insert(temp1->data);
            temp1=temp1->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

9
7 5 9 9 9 6 7 9 5

Output

Enter the number of nodes in the list- 
Enter the nodes in the list- 
5 9 7 6 

Complexity Analysis

The time complexity of this approach is- O(N)

The space complexity of this approach is- O(N)

Frequently Asked Questions

  1. How do you count duplicates in a list?
    Ans. We can either use the basic approach of using nested loops or an unordered map that takes node data and their count as key-value pairs.
  2. What is a multiply linked list?
    Ans. Each node contains pointers to multiple nodes in a multiply linked list, depending on their order based on different parameters.
  3. How can we delete a node from a singly linked list?
    Ans. We can delete a node from a singly linked list by following the below steps-
    Traverse through the linked list to get to the node.
    Store the node to be deleted and its previous node.
    Set the next pointer of the previous node to the next node of the next node.
    Delete the variable containing the current node to free the memory.
  4. Mention a few disadvantages of a linked list?
    Ans. Some of the disadvantages of the linked list are as follows-
    Random access is not allowed.
    More memory space is required.
    The memory space is scattered, thus poor localization of the memory.
  5. How can we do the sum of the two linked lists?
    Ans. To find the sum of two linked lists, we do the sum of values in the respective nodes of the linked list to get the value in the node of the resultant linked list.

Key takeaways

In this blog, we learned about the methods to remove duplicates from an unsorted doubly linked list.

  • We started with the basic approach of traversing through the doubly linked list and comparing each node with the remaining nodes in the list, and if we find any duplicates, we delete them and finally print the doubly linked list with the remaining nodes.
  • Another approach to solving this problem uses a map to keep track of the nodes in the doubly linked list. We mark every node that appears for the first time in the map as visited and prints it. If we find a node that is already visited, we continue the traversal without printing. 

You can learn more about the doubly linked lists and also practice similar problems on the CodeStudio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think