Given an unsorted doubly linked list containing n nodes. The problem is to remove duplicate nodes from the given list.
Examples:
Method 1 (Naive Approach):
This is the simplest way where two loops are used. The outer loop is used to pick the elements one by one and the inner loop compares the picked element with the rest of the elements.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void deleteNode( struct Node** head_ref, struct Node* del)
{
if (*head_ref == NULL || del == NULL)
return ;
if (*head_ref == del)
*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free (del);
}
void removeDuplicates( struct Node** head_ref)
{
if ((*head_ref) == NULL ||
(*head_ref)->next == NULL)
return ;
struct Node* ptr1, *ptr2;
for (ptr1 = *head_ref; ptr1 != NULL; ptr1 = ptr1->next) {
ptr2 = ptr1->next;
while (ptr2 != NULL) {
if (ptr1->data == ptr2->data) {
struct Node* next = ptr2->next;
deleteNode(head_ref, ptr2);
ptr2 = next;
}
else
ptr2 = ptr2->next;
}
}
}
void push( struct Node** head_ref, int new_data)
{
struct Node* new_node =
( struct Node*) malloc ( sizeof ( struct Node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void printList( struct Node* head)
{
if (head == NULL)
cout << "Doubly Linked list empty" ;
while (head != NULL) {
cout << head->data << " " ;
head = head->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 12);
push(&head, 12);
push(&head, 10);
push(&head, 4);
push(&head, 8);
push(&head, 4);
push(&head, 6);
push(&head, 4);
push(&head, 4);
push(&head, 8);
cout << "Original Doubly linked list:\n" ;
printList(head);
removeDuplicates(&head);
cout << "\nDoubly linked list after "
"removing duplicates:\n" ;
printList(head);
return 0;
}
|
Java
import java.util.*;
import java.io.*;
public class GFG
{
static class Node
{
int data;
Node next;
Node prev;
}
static Node deleteNode(Node head_ref, Node del)
{
if (head_ref == null || del == null )
return head_ref;
if (head_ref == del)
head_ref = del.next;
if (del.next != null )
del.next.prev = del.prev;
if (del.prev != null )
del.prev.next = del.next;
return head_ref;
}
static Node removeDuplicates(Node head_ref)
{
if ((head_ref) == null ||
(head_ref).next == null )
return head_ref;;
Node ptr1, ptr2;
for (ptr1 = head_ref;
ptr1 != null ; ptr1 = ptr1.next)
{
ptr2 = ptr1.next;
while (ptr2 != null )
{
if (ptr1.data == ptr2.data)
{
Node next = ptr2.next;
head_ref = deleteNode(head_ref, ptr2);
ptr2 = next;
}
else
ptr2 = ptr2.next;
}
}
return head_ref;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head_ref);
if ((head_ref) != null )
(head_ref).prev = new_node;
(head_ref) = new_node;
return head_ref;
}
static void printList( Node head)
{
if (head == null )
System.out.print( "Doubly Linked list empty" );
while (head != null )
{
System.out.print( head.data + " " );
head = head.next;
}
}
public static void main(String args[])
{
Node head = null ;
head = push(head, 12 );
head = push(head, 12 );
head = push(head, 10 );
head = push(head, 4 );
head = push(head, 8 );
head = push(head, 4 );
head = push(head, 6 );
head = push(head, 4 );
head = push(head, 4 );
head = push(head, 8 );
System.out.print( "Original Doubly linked list:\n" );
printList(head);
head=removeDuplicates(head);
System.out.print( "\nDoubly linked list after" +
" removing duplicates:\n" );
printList(head);
}
}
|
Python
class Node:
def __init__( self , data = None , next = None ):
self . next = next
self .data = data
def deleteNode(head_ref,del_):
if (head_ref = = None or del_ = = None ):
return head_ref
if (head_ref = = del_):
head_ref = del_. next
if (del_. next ! = None ):
del_. next .prev = del_.prev
if (del_.prev ! = None ):
del_.prev. next = del_. next
return head_ref
def removeDuplicates( head_ref):
if ((head_ref) = = None or (head_ref). next = = None ):
return head_ref
ptr1 = head_ref
ptr2 = None
while (ptr1 ! = None ) :
ptr2 = ptr1. next
while (ptr2 ! = None ):
if (ptr1.data = = ptr2.data):
next = ptr2. next
head_ref = deleteNode(head_ref, ptr2)
ptr2 = next
else :
ptr2 = ptr2. next
ptr1 = ptr1. next
return head_ref
def push( head_ref, new_data):
new_node = Node()
new_node.data = new_data
new_node.prev = None
new_node. next = (head_ref)
if ((head_ref) ! = None ):
(head_ref).prev = new_node
(head_ref) = new_node
return head_ref
def printList( head):
if (head = = None ):
print ( "Doubly Linked list empty" )
while (head ! = None ):
print ( head.data ,end = " " )
head = head. next
head = None
head = push(head, 12 )
head = push(head, 12 )
head = push(head, 10 )
head = push(head, 4 )
head = push(head, 8 )
head = push(head, 4 )
head = push(head, 6 )
head = push(head, 4 )
head = push(head, 4 )
head = push(head, 8 )
print ( "Original Doubly linked list:" )
printList(head)
head = removeDuplicates(head)
print ( "\nDoubly linked list after removing duplicates:" )
printList(head)
|
C#
using System;
class GFG
{
public class Node
{
public int data;
public Node next;
public Node prev;
}
static Node deleteNode(Node head_ref, Node del)
{
if (head_ref == null || del == null )
return head_ref;
if (head_ref == del)
head_ref = del.next;
if (del.next != null )
del.next.prev = del.prev;
if (del.prev != null )
del.prev.next = del.next;
return head_ref;
}
static Node removeDuplicates(Node head_ref)
{
if ((head_ref) == null ||
(head_ref).next == null )
return head_ref;;
Node ptr1, ptr2;
for (ptr1 = head_ref;
ptr1 != null ; ptr1 = ptr1.next)
{
ptr2 = ptr1.next;
while (ptr2 != null )
{
if (ptr1.data == ptr2.data)
{
Node next = ptr2.next;
head_ref = deleteNode(head_ref, ptr2);
ptr2 = next;
}
else
ptr2 = ptr2.next;
}
}
return head_ref;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head_ref);
if ((head_ref) != null )
(head_ref).prev = new_node;
(head_ref) = new_node;
return head_ref;
}
static void printList( Node head)
{
if (head == null )
Console.Write( "Doubly Linked list empty" );
while (head != null )
{
Console.Write( head.data + " " );
head = head.next;
}
}
public static void Main(String []args)
{
Node head = null ;
head = push(head, 12);
head = push(head, 12);
head = push(head, 10);
head = push(head, 4);
head = push(head, 8);
head = push(head, 4);
head = push(head, 6);
head = push(head, 4);
head = push(head, 4);
head = push(head, 8);
Console.Write( "Original Doubly linked list:\n" );
printList(head);
head=removeDuplicates(head);
Console.Write( "\nDoubly linked list after" +
" removing duplicates:\n" );
printList(head);
}
}
|
Javascript
<script>
class Node {
constructor() {
this .data = 0;
this .prev = null ;
this .next = null ;
}
}
function deleteNode(head_ref, del) {
if (head_ref == null || del == null )
return head_ref;
if (head_ref == del)
head_ref = del.next;
if (del.next != null )
del.next.prev = del.prev;
if (del.prev != null )
del.prev.next = del.next;
return head_ref;
}
function removeDuplicates(head_ref) {
if ((head_ref) == null || (head_ref).next == null )
return head_ref;
var ptr1, ptr2;
for (ptr1 = head_ref; ptr1 != null ; ptr1 = ptr1.next) {
ptr2 = ptr1.next;
while (ptr2 != null ) {
if (ptr1.data == ptr2.data) {
var next = ptr2.next;
head_ref = deleteNode(head_ref, ptr2);
ptr2 = next;
}
else
ptr2 = ptr2.next;
}
}
return head_ref;
}
function push(head_ref , new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head_ref);
if ((head_ref) != null )
(head_ref).prev = new_node;
(head_ref) = new_node;
return head_ref;
}
function printList(head) {
if (head == null )
document.write( "Doubly Linked list empty" );
while (head != null ) {
document.write(head.data + " " );
head = head.next;
}
}
var head = null ;
head = push(head, 12);
head = push(head, 12);
head = push(head, 10);
head = push(head, 4);
head = push(head, 8);
head = push(head, 4);
head = push(head, 6);
head = push(head, 4);
head = push(head, 4);
head = push(head, 8);
document.write( "Original Doubly linked list:<br/>" );
printList(head);
head = removeDuplicates(head);
document.write( "<br/>Doubly linked list after"
+ " removing duplicates:<br/>" );
printList(head);
</script>
|
Output
Original Doubly linked list:n8 4 4 6 4 8 4 10 12 12
Doubly linked list after removing duplicates:n8 4 6 10 12
Time Complexity: O(n2)
Auxiliary Space: O(1)
Method 2 (Sorting): Following are the steps:
- Sort the elements of the doubly linked list using Merge Sort. Refer this post.
- Remove duplicates in linear time using the algorithm to remove duplicates from a sorted doubly linked list.
Time Complexity: O(nLogn)
Auxiliary Space: O(1)
Note that this method doesn’t preserve the original order of elements.
Method 3 Efficient Approach(Hashing):
We traverse the doubly linked list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table. Hash table is implemented using unordered_set in C++.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void deleteNode( struct Node** head_ref, struct Node* del)
{
if (*head_ref == NULL || del == NULL)
return ;
if (*head_ref == del)
*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free (del);
}
void removeDuplicates( struct Node** head_ref)
{
if ((*head_ref) == NULL)
return ;
unordered_set< int > us;
struct Node* current = *head_ref, *next;
while (current != NULL) {
if (us.find(current->data) != us.end()) {
next = current->next;
deleteNode(head_ref, current);
current = next;
}
else {
us.insert(current->data);
current = current->next;
}
}
}
void push( struct Node** head_ref, int new_data)
{
struct Node* new_node =
( struct Node*) malloc ( sizeof ( struct Node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void printList( struct Node* head)
{
if (head == NULL)
cout << "Doubly Linked list empty" ;
while (head != NULL) {
cout << head->data << " " ;
head = head->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 12);
push(&head, 12);
push(&head, 10);
push(&head, 4);
push(&head, 8);
push(&head, 4);
push(&head, 6);
push(&head, 4);
push(&head, 4);
push(&head, 8);
cout << "Original Doubly linked list:n" ;
printList(head);
removeDuplicates(&head);
cout << "\nDoubly linked list after "
"removing duplicates:n" ;
printList(head);
return 0;
}
|
Java
import java.util.*;
public class GFG
{
static class Node
{
int data;
Node next;
Node prev;
};
static Node deleteNode(Node head_ref, Node del)
{
if (head_ref == null || del == null )
return null ;
if (head_ref == del)
head_ref = del.next;
if (del.next != null )
del.next.prev = del.prev;
if (del.prev != null )
del.prev.next = del.next;
return head_ref;
}
static Node removeDuplicates(Node head_ref)
{
if ((head_ref) == null )
return null ;
HashSet<Integer> us = new HashSet<>();
Node current = head_ref, next;
while (current != null )
{
if (us.contains(current.data))
{
next = current.next;
head_ref = deleteNode(head_ref, current);
current = next;
}
else
{
us.add(current.data);
current = current.next;
}
}
return head_ref;
}
static Node push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head_ref);
if ((head_ref) != null )
(head_ref).prev = new_node;
(head_ref) = new_node;
return head_ref;
}
static void printList(Node head)
{
if (head == null )
System.out.print( "Doubly Linked list empty" );
while (head != null )
{
System.out.print(head.data + " " );
head = head.next;
}
}
public static void main(String[] args)
{
Node head = null ;
head = push(head, 12 );
head = push(head, 12 );
head = push(head, 10 );
head = push(head, 4 );
head = push(head, 8 );
head = push(head, 4 );
head = push(head, 6 );
head = push(head, 4 );
head = push(head, 4 );
head = push(head, 8 );
System.out.println( "Original Doubly linked list:" );
printList(head);
head = removeDuplicates(head);
System.out.println( "\nDoubly linked list after " +
"removing duplicates:" );
printList(head);
}
}
|
Python3
class Node:
def __init__( self ):
self .data = 0
self . next = None
self .prev = None
def deleteNode( head_ref, del_):
if (head_ref = = None or del_ = = None ):
return None
if (head_ref = = del_):
head_ref = del_. next
if (del_. next ! = None ):
del_. next .prev = del_.prev
if (del_.prev ! = None ):
del_.prev. next = del_. next
return head_ref
def removeDuplicates(head_ref):
if ((head_ref) = = None ):
return None
us = set ()
current = head_ref
next = None
while (current ! = None ):
if ((current.data) in us):
next = current. next
head_ref = deleteNode(head_ref, current)
current = next
else :
us.add(current.data)
current = current. next
return head_ref
def push(head_ref,new_data):
new_node = Node()
new_node.data = new_data
new_node.prev = None
new_node. next = (head_ref)
if ((head_ref) ! = None ):
(head_ref).prev = new_node
(head_ref) = new_node
return head_ref
def printList( head):
if (head = = None ):
print ( "Doubly Linked list empty" )
while (head ! = None ):
print (head.data , end = " " )
head = head. next
head = None
head = push(head, 12 )
head = push(head, 12 )
head = push(head, 10 )
head = push(head, 4 )
head = push(head, 8 )
head = push(head, 4 )
head = push(head, 6 )
head = push(head, 4 )
head = push(head, 4 )
head = push(head, 8 )
print ( "Original Doubly linked list:" )
printList(head)
head = removeDuplicates(head)
print ( "\nDoubly linked list after removing duplicates:" )
printList(head)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public class Node
{
public int data;
public Node next;
public Node prev;
};
static Node deleteNode(Node head_ref, Node del)
{
if (head_ref == null || del == null )
return null ;
if (head_ref == del)
head_ref = del.next;
if (del.next != null )
del.next.prev = del.prev;
if (del.prev != null )
del.prev.next = del.next;
return head_ref;
}
static Node removeDuplicates(Node head_ref)
{
if ((head_ref) == null )
return null ;
HashSet< int > us = new HashSet< int >();
Node current = head_ref, next;
while (current != null )
{
if (us.Contains(current.data))
{
next = current.next;
head_ref = deleteNode(head_ref, current);
current = next;
}
else
{
us.Add(current.data);
current = current.next;
}
}
return head_ref;
}
static Node push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head_ref);
if ((head_ref) != null )
(head_ref).prev = new_node;
(head_ref) = new_node;
return head_ref;
}
static void printList(Node head)
{
if (head == null )
Console.Write( "Doubly Linked list empty" );
while (head != null )
{
Console.Write(head.data + " " );
head = head.next;
}
}
public static void Main(String[] args)
{
Node head = null ;
head = push(head, 12);
head = push(head, 12);
head = push(head, 10);
head = push(head, 4);
head = push(head, 8);
head = push(head, 4);
head = push(head, 6);
head = push(head, 4);
head = push(head, 4);
head = push(head, 8);
Console.WriteLine( "Original Doubly linked list:" );
printList(head);
head = removeDuplicates(head);
Console.WriteLine( "\nDoubly linked list after " +
"removing duplicates:" );
printList(head);
}
}
|
Javascript
<script>
class Node {
constructor(val) {
this .data = val;
this .prev = null ;
this .next = null ;
}
}
function deleteNode(head_ref, del) {
if (head_ref == null || del == null )
return null ;
if (head_ref == del)
head_ref = del.next;
if (del.next != null )
del.next.prev = del.prev;
if (del.prev != null )
del.prev.next = del.next;
return head_ref;
}
function removeDuplicates(head_ref) {
if ((head_ref) == null )
return null ;
var us = new Set();
var current = head_ref, next;
while (current != null ) {
if (us.has(current.data)) {
next = current.next;
head_ref = deleteNode(head_ref, current);
current = next;
} else {
us.add(current.data);
current = current.next;
}
}
return head_ref;
}
function push(head_ref , new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.prev = null ;
new_node.next = (head_ref);
if ((head_ref) != null )
(head_ref).prev = new_node;
(head_ref) = new_node;
return head_ref;
}
function printList(head) {
if (head == null )
document.write( "Doubly Linked list empty" );
while (head != null ) {
document.write(head.data + " " );
head = head.next;
}
}
var head = null ;
head = push(head, 12);
head = push(head, 12);
head = push(head, 10);
head = push(head, 4);
head = push(head, 8);
head = push(head, 4);
head = push(head, 6);
head = push(head, 4);
head = push(head, 4);
head = push(head, 8);
document.write( "Original Doubly linked list:<br/>" );
printList(head);
head = removeDuplicates(head);
document.write( "<br/>Doubly linked list after " + "removing duplicates:<br/>" );
printList(head);
</script>
|
Output
Original Doubly linked list:n8 4 4 6 4 8 4 10 12 12
Doubly linked list after removing duplicates:n8 4 6 10 12
Time Complexity: O(n)
Auxiliary Space: O(n)
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!