Remove duplicates from an unsorted doubly linked list | C ++ implementation to remove duplicates from an unsorted doubly linked list ; a node of the doubly linked list ; Function to delete a node in a Doubly Linked List . head_ref -- > pointer to head node pointer . del -- > pointer to node to be deleted . ; base case ; If node to be deleted is head node ; Change next only if node to be deleted is NOT the last node ; Change prev only if node to be deleted is NOT the first node ; function to remove duplicates from an unsorted doubly linked list ; if DLL is empty or if it contains only a single node ; pick elements one by one ; Compare the picked element with the rest of the elements ; if duplicate , then delete it ; store pointer to the node next to ' ptr2' ; delete node pointed to by ' ptr2' ; update ' ptr2' ; else simply move to the next node ; Function to insert a node at the beginning of the Doubly Linked List ; allocate node ; put in the data ; since we are adding at the beginning , prev is always NULL ; link the old list off the new node ; change prev of head node to new node ; move the head to point to the new node ; Function to print nodes in a given doubly linked list ; if list is empty ; Driver program to test above ; Create the doubly linked list : 8 < -> 4 < -> 4 < -> 6 < -> 4 < -> 8 < -> 4 < -> 10 < -> 12 < -> 12 ; remove duplicate nodes
#include <bits/stdc++.h> NEW_LINE 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 << " Doubly linked list after " STRNEWLINE TABSYMBOL TABSYMBOL TABSYMBOL " removing duplicates : n " ; printList ( head ) ; return 0 ; }