Remove duplicates from an unsorted doubly linked list

Remove the node from doubly linked list which are exist in more than once. Note that linked list nodes is not an sorted. In this post are given iterative solution of this problem to find duplicates node and deleted all duplicates.

Suppose we are inserted the following (1,1,4,6,6,6,7,8,1) node in a sequence.

Remove duplicates from an unsorted doubly linked list After Removing of duplicate nodes in doubly linked list

Hint of implementation process: We are need two while-loops. outer loop are used to iterate linked list nodes. and inner loop are find to the duplicates nodes. If inner loop are find repeated node then we are delete this node to linked list. This process are repeated until outer loop are not iterates all nodes of linked list. The time complexity of this process is O(n^2).

Here given code implementation process.

//C Program
//Remove duplicates from doubly linked list 
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
  struct Node*prev;
};

//insert Node element of end of linked list
void insert(struct Node**head,int value)
{

  //Create a dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL)
  {
    printf("Memory overflow\n");
  }
  else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(*head==NULL)
    {
      *head=node;
    }
    else
    {
      struct Node*temp=*head;
      //find last node
      while(temp!=NULL && temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add new node to last positions
      temp->next=node;
      node->prev=temp;

    }
  }
}
//display element of Node
void display(struct Node*temp)
{

  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  else
  {

    //Traverse doubly linked list from front to rear
    while(temp!=NULL)
    {
      //print node value
      printf("%d  ",temp->data);
      temp=temp->next;
    }
  }

}
//delete duplicates from doubly linked list 
void remove_node(struct Node*head)
{

  if(head!=NULL)
  {

    struct Node*current=head,*temp=NULL,*find=NULL;

    while(current!=NULL)
    {

      temp=current->next;

      while(temp!=NULL)
      {
        //duplicate nodes
        if(temp->data==current->data)
        {
          find=temp;
        }

        temp=temp->next;

        if(find!=NULL)
        {
          //When find deleted node
          if(find->prev!=NULL)
          {
            find->prev->next=temp;
          }
          if(temp!=NULL)
          {
            temp->prev=find->prev;
          }
          find->prev=NULL;
          find->next=NULL;
          //Free node element
          free(find);
          find=NULL;
        }
      }
      //visit next node
      current=current->next;
    }

  }
}
int main()
{
  //set node pointer value
  struct Node*head=NULL;
  //Insert element of linked list
  insert(&head,1);
  insert(&head,1);
  insert(&head,4);
  insert(&head,6);
  insert(&head,6);
  insert(&head,6);
  insert(&head,7);
  insert(&head,8);
  insert(&head,1);
  printf("Before Delete duplicate nodes : \n");
  //display all node
  display(head);
  printf("\nAfter Delete duplicate nodes : \n");
  remove_node(head);
  display(head);
}

Output

Before Delete duplicate nodes : 
1  1  4  6  6  6  7  8  1  
After Delete duplicate nodes : 
1  4  6  7  8 
//C++ Program
//Remove duplicates from doubly linked list 

#include <iostream> 
using namespace std;
//create structure
struct Node
{
  int data;
  Node*next;
  Node*prev;
};
class DoublyList
{
  struct Node*head;
public:
  DoublyList();
  void insert(int);
  void display();
  void remove_node();
};
//set inital value
DoublyList::DoublyList()
{
  head=NULL;
}

//insert a linked list Node element
void DoublyList:: insert(int value)
{
  //Create a dynamic node
  Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }
  else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(head==NULL)
    {
      head=node;
    }else
    {
      Node*temp=head;
      //find last node
      while(temp!=NULL && temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add new node to last positions
      temp->next=node;
      node->prev=temp;

    }
  }
}
//display all element of doubly linked list
void DoublyList::display()
{

  if(head==NULL)
  {
    //when linked list is empty
    cout<<"Empty linked list";
  }
  else
  {
    cout<<"Linked List Element :";
    Node*temp=head;
    while(temp!=NULL)
    {
      //display node elemement
      cout<<" "<<temp->data;
      temp=temp->next;
    }
  }

}
//delete duplicates from doubly linked list 
void  DoublyList::remove_node()
{

  if(head!=NULL)
  {

    struct Node*current=head,*temp=NULL,*find=NULL;

    while(current!=NULL)
    {

      temp=current->next;

      while(temp!=NULL)
      {
        //duplicate nodes
        if(temp->data==current->data) find=temp;

        temp=temp->next;

        if(find!=NULL)
        {
          //When find deleted node
          if(find->prev!=NULL)
          {
            find->prev->next=temp;
          }
          if(temp!=NULL)
          {
            temp->prev=find->prev;
          }
          find->prev=NULL;
          find->next=NULL;
          //Free node element
          delete find;
          find=NULL;
        }
      }
      //visit next node
      current=current->next;
    }

  }
}
int main()
{
  DoublyList obj=DoublyList();

  //Insert element of linked list
  obj.insert(1);
  obj.insert(1);
  obj.insert(4);
  obj.insert(6);
  obj.insert(6);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  obj.insert(1);
  cout<<"Before delete duplicates "<<endl;
  //display all node
  obj.display();

  cout<<"\nAfter delete duplicates "<<endl;
  obj.remove_node();
  obj.display();
}

Output

Before delete duplicates 
Linked List Element : 1 1 4 6 6 6 7 8 1
After delete duplicates 
Linked List Element : 1 4 6 7 8
//Java program
//Remove duplicates from doubly linked list 
class Node 
{
  public int data;
  public Node next, prev;
  Node(int data)
  {
    this.data=data;
    this.next=this.prev=null;
  }
}
public class LinkedList 
{


  //head of linked list
  public Node head;
  //Class constructors
  LinkedList() 
  {
    head = null;
  }
  //add newly created node at End of linked list
  public void insert(int value) 
  {
    //Create a dynamic node
    Node node = new Node(value);

    //when no element
    if (head == null) 
    {
      head = node;
    }
    else 
    {
      Node temp = head;
      //find last node
      while (temp.next != null) temp = temp.next;
      //add node
      node.prev = temp;
      temp.next = node;
    }
  }
  //display all Linked List node value
  public void display() 
  {
    if (head != null) 
    {
      System.out.print(" Linked List Element :");
      Node temp = head;
      while (temp != null) 
      {
        //Display node value
        System.out.print("  " + temp.data);
        temp = temp.next;
      }
    } 
    else 
    {
      System.out.println("Empty Linked list");
    }
  }

  //Delete duplicates from doubly linked list 
  public void removeNode() 
  {

    if (head != null) 
    {

      Node current = head, temp = null, find = null;

      while (current != null) 
      {

        temp = current.next;

        while (temp != null) 
        {
          //duplicate nodes check
          if (temp.data == current.data) find = temp;

          temp = temp.next;

          if (find != null) 
          {
            //When find deleted node
            if (find.prev != null) 
            {
              find.prev.next = temp;
            }
            if (temp != null) 
            {
              temp.prev = find.prev;
            }
            find.prev = null;
            find.next = null;
            find = null;
          }
        }
        //visit next node
        current = current.next;
      }

    }
  }

  public static void main(String[] args) 
  {

    LinkedList obj = new LinkedList();
    //add elements
    obj.insert(1);
    obj.insert(1);
    obj.insert(4);
    obj.insert(6);
    obj.insert(6);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    obj.insert(1);
    System.out.println("Before delete duplicates ");
    //display all node
    obj.display();

    System.out.println("\nAfter delete duplicates ");
    obj.removeNode();
    obj.display();
  }
}

Output

Before delete duplicates 
 Linked List Element :  1  1  4  6  6  6  7  8  1
After delete duplicates 
 Linked List Element :  1  4  6  7  8
#Python Program
#Remove duplicates from doubly linked list
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
        self.prev=None

#create class LinkedList    
class LinkedList:
  def __init__(self):
    #set initial head value
    self.head=None


  #insert new node to end of Linked List  
  def insert(self,data):
    #make a new node
    node=Node(data)

    if(self.head==None):
      #when empty list
      self.head=node
    else:
      temp=self.head
      #find last node
      while temp.next!=None:
          temp=temp.next
      #add node    
      temp.next=node
      node.prev=temp

   

  #view all node values    
  def display(self):
    temp=self.head
    print("Linked List Elements : ")

    while(temp!=None):
      #print node value
      print(temp.data,end=" ")
      temp=temp.next
    print("\n")

  #delete duplicates from doubly linked list 
  def  removeNode(self):

    if(self.head!=None):

      current=self.head
      temp=None
      find=None

      while(current!=None):
        temp=current.next

        while(temp!=None):
          #duplicate nodes check
          if(temp.data==current.data):
            find=temp

          temp=temp.next

          if(find!=None):
            #When find deleted node
            if(find.prev!=None):
              find.prev.next=temp
            
            if(temp!=None):
              temp.prev=find.prev
            
            find.prev=None
            find.next=None
            find=None
            
        #visit next node
        current=current.next
      

      
    
def main():

    #Create Object of class LinkedList
    obj=LinkedList()
    #insert element
    obj.insert(1)
    obj.insert(1)
    obj.insert(4)
    obj.insert(6)
    obj.insert(6)
    obj.insert(6)
    obj.insert(7)
    obj.insert(8)
    obj.insert(1)
    print("Before delete duplicates ")
    #display all node
    obj.display()

    print("\nAfter delete duplicates ")
    obj.removeNode()
    obj.display()

if(__name__=="__main__"):
    main()

Output

Before delete duplicates 
Linked List Elements : 
1 1 4 6 6 6 7 8 1 


After delete duplicates 
Linked List Elements : 
1 4 6 7 8 
//C# program
//Remove duplicates from doubly linked list 
using System;
public class Node 
{
  public int data;
  public Node next, prev;
  public Node(int data)
  {
    this.data=data;
    this.next=this.prev=null;
  }
}
public class LinkedList 
{


  //head of linked list
  public Node head;
  //Class constructors
  LinkedList() 
  {
    head = null;
  }
  //add newly created node at End of linked list
  public void insert(int value) 
  {
    //Create a dynamic node
    Node node = new Node(value);

    //when no element
    if (head == null) 
    {
      head = node;
    }
    else 
    {
      Node temp = head;
      //find last node
      while (temp.next != null) temp = temp.next;
      //add node
      node.prev = temp;
      temp.next = node;
    }
  }
  //display all Linked List node value
  public void display() 
  {
    if (head != null) 
    {
      Console.Write(" Linked List Element :");
      Node temp = head;
      while (temp != null) 
      {
        //Display node value
        Console.Write("  " + temp.data);
        temp = temp.next;
      }
    } 
    else 
    {
      Console.WriteLine("Empty Linked list");
    }
  }

  //Delete duplicates from doubly linked list 
  public void removeNode() 
  {

    if (head != null) 
    {

      Node current = head, temp = null, find = null;

      while (current != null) 
      {

        temp = current.next;

        while (temp != null) 
        {
          //duplicate nodes check
          if (temp.data == current.data) find = temp;

          temp = temp.next;

          if (find != null) 
          {
            //When find deleted node
            if (find.prev != null) 
            {
              find.prev.next = temp;
            }
            if (temp != null) 
            {
              temp.prev = find.prev;
            }
            find.prev = null;
            find.next = null;
            find = null;
          }
        }
        //visit next node
        current = current.next;
      }

    }
  }

  public static void Main(String[] args) 
  {

    LinkedList obj = new LinkedList();
    //add elements
    obj.insert(1);
    obj.insert(1);
    obj.insert(4);
    obj.insert(6);
    obj.insert(6);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    obj.insert(1);
    Console.WriteLine("Before delete duplicates ");
    //display all node
    obj.display();

    Console.WriteLine("\nAfter delete duplicates ");
    obj.removeNode();
    obj.display();
  }
}

Output

Before delete duplicates 
 Linked List Element :  1  1  4  6  6  6  7  8  1
After delete duplicates 
 Linked List Element :  1  4  6  7  8
<?php
//Php program 
//Remove duplicates from doubly linked list 
class Node
{
  public $data;
  public $next;
  public $perv;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
    $this->prev = NULL;
  }
}
class LinkedList
{

  private $head;
  function __construct()
  {
    $head=NULL;
  }
  /*
  * Append the Given data value at Beginning of linked list
  * Fun : insert
  * Parm: data value
  *@return None
  */
  function insert($data)
  {
    //Create a dynamic node
    $node=new Node($data);
    if($node==NULL)
    {
      echo "Memory overflow\n";
    }
    else
    {
      if($this->head==NULL)
      {
        $this->head=$node;
      }
      else
      {
        $temp=$this->head;
        //find last node
        while($temp!=NULL && $temp->next!=NULL)
        {
          $temp=$temp->next;
        }
        //add new node to last positions
        $temp->next=$node;
        $node->prev=$temp;

      }
    }
  }

  //Display all inserted node in linked list
  function display()
  {
    if($this->head==NULL)
    {
      echo "Empty Linked List";
    }
    else
    {
      $temp=$this->head;
      echo "Doubly Linked List :";
      while($temp!=NULL)
      {
        //display node value
        echo "  ".$temp->data;
        $temp=$temp->next; //visit to next node
      }
    }   
  }
  //delete duplicates from doubly linked list 
  public function  remove_node()
  {

    if($this->head!=NULL)
    {

      $current=$this->head;
      $temp=NULL;
      $find=NULL;

      while($current!=NULL)
      {

        $temp=$current->next;

        while($temp!=NULL)
        {
          //duplicate nodes
          if($temp->data==$current->data) 
          {
            $find=$temp;
          }

          $temp=$temp->next;

          if($find!=NULL)
          {
            //When find deleted node
            if($find->prev!=NULL)
            {
              $find->prev->next=$temp;
            }
            if($temp!=NULL)
            {
              $temp->prev=$find->prev;
            }
            $find->prev=NULL;
            $find->next=NULL;
          
            $find=NULL;
          }
        }
        //visit next node
        $current=$current->next;
      }

    }
  }
}
function main()
{
  //Make a object of LinkedList class
  $obj= new LinkedList();

  //Insert element of linked list
  $obj->insert(1);
  $obj->insert(1);
  $obj->insert(4);
  $obj->insert(6);
  $obj->insert(6);
  $obj->insert(6);
  $obj->insert(7);
  $obj->insert(8);
  $obj->insert(1);
  echo "Before delete duplicates \n";
  //display all node
  $obj->display();

  echo "\nAfter delete duplicates \n";
  $obj->remove_node();
  $obj->display();
}
main();
?>


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved