# 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.

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;
{
}
else
{
//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)
{
}
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
{

{

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
//Insert element of linked list
printf("Before Delete duplicate nodes : \n");
//display all node
printf("\nAfter Delete duplicate nodes : \n");
}``````

#### 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
{
public:
DoublyList();
void insert(int);
void display();
void remove_node();
};
//set inital value
DoublyList::DoublyList()
{
}

//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;
{
}else
{
//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()
{

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

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

{

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;
}
}
{

//Class constructors
{
}
//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)
{
}
else
{
Node temp = head;
//find last node
while (temp.next != null) temp = temp.next;
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
{
}
}

//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)
{

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

def __init__(self):
#set initial head value

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

#when empty list
else:
#find last node
while temp.next!=None:
temp=temp.next
temp.next=node
node.prev=temp

#view all node values
def display(self):
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):

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
#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;
}
}
{

//Class constructors
{
}
//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)
{
}
else
{
Node temp = head;
//find last node
while (temp.next != null) temp = temp.next;
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
{
}
}

//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)
{

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;
}
}
{

function __construct()
{
}
/*
* 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
{
{
}
else
{
//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()
{
{
echo "Empty Linked List";
}
else
{
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()
{

{

\$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

//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.