Tutorialspoint.dev

Remove duplicates from a sorted doubly linked list

Given a sorted doubly linked list containing n nodes. The problem is to remove duplicate nodes from the given list.

Examples:



Algorithm:

removeDuplicates(head_ref, x)
      if head_ref == NULL
          return
      Initialize current = head_ref
      while current->next != NULL
           if current->data == current->next->data
               deleteNode(head_ref, current->next)
           else
               current = current->next

The algorithm for deleteNode(head_ref, current) (which deletes the node using the pointer to the node) is discussed in this post.

C++

/* C++ implementation to remove duplicates from a 
   sorted doubly linked list */
#include <bits/stdc++.h>
  
using namespace std;
  
/* a node of the doubly linked list */
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
  
/* Function to delete a node in a Doubly Linked List.
   head_ref --> pointer to head node pointer.
   del  -->  pointer to node to be deleted. */
void deleteNode(struct Node** head_ref, struct Node* del)
{
    /* base case */
    if (*head_ref == NULL || del == NULL)
        return;
  
    /* If node to be deleted is head node */
    if (*head_ref == del)
        *head_ref = del->next;
  
    /* Change next only if node to be deleted 
        is NOT the last node */
    if (del->next != NULL)
        del->next->prev = del->prev;
  
    /* Change prev only if node to be deleted 
       is NOT the first node */
    if (del->prev != NULL)
        del->prev->next = del->next;
  
    /* Finally, free the memory occupied by del*/
    free(del);
}
  
/* function to remove duplicates from a 
   sorted doubly linked list */
void removeDuplicates(struct Node** head_ref)
{
    /* if list is empty */
    if ((*head_ref) == NULL)
        return;
  
    struct Node* current = *head_ref;
    struct Node* next;
  
    /* traverse the list till the last node */
    while (current->next != NULL) {
  
        /* Compare current node with next node */
        if (current->data == current->next->data)
  
            /* delete the node pointed to by
              'current->next' */
            deleteNode(head_ref, current->next);
  
        /* else simply move to the next node */
        else
            current = current->next;
    }
}
  
/* Function to insert a node at the beginning 
   of the Doubly Linked List */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = 
           (struct Node*)malloc(sizeof(struct Node));
  
    /* put in the data  */
    new_node->data = new_data;
  
    /* since we are adding at the begining,
    prev is always NULL */
    new_node->prev = NULL;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);
  
    /* change prev of head node to new node */
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
  
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
  
/* Function to print nodes in a given doubly linked list */
void printList(struct Node* head)
{
    /* if list is empty */
    if (head == NULL)
        cout << "Doubly Linked list empty";
  
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
  
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    /* Create the doubly linked list:
     4<->4<->4<->4<->6<->8<->8<->10<->12<->12 */
    push(&head, 12);
    push(&head, 12);
    push(&head, 10);
    push(&head, 8);
    push(&head, 8);
    push(&head, 6);
    push(&head, 4);
    push(&head, 4);
    push(&head, 4);
    push(&head, 4);
  
    cout << "Original Doubly linked list:n";
    printList(head);
  
    /* remove duplicate nodes */
    removeDuplicates(&head);
  
    cout << " Doubly linked list after"
             " removing duplicates:n";
    printList(head);
  
    return 0;
}

Java

/* Java implementation to remove duplicates from a  
   sorted doubly linked list */
public class removeDuplicatesFromSortedList {
  
    /* function to remove duplicates from a  
   sorted doubly linked list */
    public static void removeDuplicates(Node head) 
    
        /* if list is empty */
        if (head== null
            return
    
        Node current = head; 
        while (current.next != null
        
            /* Compare current node with next node */
            if (current.data == current.next.data) 
                /* delete the node pointed to by 
              ' current->next' */
                deleteNode(head, current.next); 
    
            /* else simply move to the next node */
            else
                current = current.next; 
        }  
    
        /* traverse the list till the last node */
        while (current.next != null
        
    
            /* Compare current node with next node */
            if (current.data == current.next.data) 
            /* delete the node pointed to by 
              'current->next' */
                deleteNode(head, current.next); 
    
            /* else simply move to the next node */
            else
                current = current.next; 
        
    
  
  
    /* Function to delete a node in a Doubly Linked List. 
    head_ref --> pointer to head node pointer. 
    del  -->  pointer to node to be deleted. */
    public static void deleteNode(Node head, Node del)
    {
         /* base case */
        if(head==null || del==null)
        {
            return ;
        }
        /* If node to be deleted is head node */
        if(head==del)
        {
            head=del.next;
        }
        /* Change next only if node to be deleted  
        is NOT the last node */
        if(del.next!=null)
        {
            del.next.prev=del.prev;
        }
        /* Change prev only if node to be deleted  
       is NOT the first node */
        if (del.prev != null
            del.prev.next = del.next; 
  
    }
  
  
    /* Function to insert a node at the beginning  
    of the Doubly Linked List */
    public static Node push(Node head, int data)
    {
        /* allocate node */
        Node newNode=new Node(data);
        /* since we are adding at the begining, 
        prev is always NULL */
        newNode.prev=null;
        /* link the old list off the new node */
        newNode.next =head; 
        /* change prev of head node to new node */
        if(head!=null)
        {
            head.prev=newNode;
        }
        head=newNode;
        return head;
    }
  
    /* Function to print nodes in a given doubly linked list */
    public static void printList(Node head)
    {
        if (head == null
            System.out.println("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, 8); 
        head=push(head, 8); 
        head=push(head, 6); 
        head=push(head, 4); 
        head=push(head, 4); 
        head=push(head, 4); 
        head=push(head, 4);
  
        System.out.println("Original Doubly LinkedList");
        printList(head); 
  
        /* remove duplicate nodes */
        removeDuplicates(head); 
        System.out.println(" Doubly linked list after removing duplicates:");
        printList(head);
    }
}
class Node
{
    int data;
    Node next,prev;
  
    Node(int data)
    {
        this.data=data;
        next=null;
        prev=null;
    }
}
//This code is contributed by Gaurav Tiwari

C#

/* C# implementation to remove duplicates from a 
sorted doubly linked list */
using System; 
  
public class removeDuplicatesFromSortedList 
  
    /* function to remove duplicates from a 
    sorted doubly linked list */
    public static void removeDuplicates(Node head) 
    
        /* if list is empty */
        if (head == null
            return
      
        Node current = head; 
        while (current.next != null
        
            /* Compare current node with next node */
            if (current.data == current.next.data) 
              
                /* delete the node pointed to by 
            ' current->next' */
                deleteNode(head, current.next); 
      
            /* else simply move to the next node */
            else
                current = current.next; 
        
      
        /* traverse the list till the last node */
        while (current.next != null
        
      
            /* Compare current node with next node */
            if (current.data == current.next.data) 
              
            /* delete the node pointed to by 
            'current->next' */
                deleteNode(head, current.next); 
      
            /* else simply move to the next node */
            else
                current = current.next; 
        
    
  
  
    /* Function to delete a node in a Doubly Linked List. 
    head_ref --> pointer to head node pointer. 
    del --> pointer to node to be deleted. */
    public static void deleteNode(Node head, Node del) 
    
        /* base case */
        if(head == null || del == null
        
            return
        
          
        /* If node to be deleted is head node */
        if(head == del) 
        
            head = del.next; 
        
          
        /* Change next only if node to be deleted 
        is NOT the last node */
        if(del.next != null
        
            del.next.prev = del.prev; 
        
          
        /* Change prev only if node to be deleted 
        is NOT the first node */
        if (del.prev != null
            del.prev.next = del.next; 
  
    
  
  
    /* Function to insert a node at the beginning 
    of the Doubly Linked List */
    public static Node push(Node head, int data) 
    
        /* allocate node */
        Node newNode = new Node(data); 
          
        /* since we are adding at the begining, 
        prev is always NULL */
        newNode.prev = null
          
        /* link the old list off the new node */
        newNode.next = head; 
          
        /* change prev of head node to new node */
        if(head != null
        
            head.prev = newNode; 
        
        head = newNode; 
        return head; 
    
  
    /* Function to print nodes in a given doubly linked list */
    public static void printList(Node head) 
    
        if (head == null
            Console.WriteLine("Doubly Linked list empty"); 
          
        while (head != null
        
            Console.Write(head.data + " ") ; 
            head = head.next; 
        
    
  
    // Driver code
    public static void Main(String []args) 
    
        Node head = null
        head = push(head, 12); 
        head = push(head, 12); 
        head = push(head, 10); 
        head = push(head, 8); 
        head = push(head, 8); 
        head = push(head, 6); 
        head = push(head, 4); 
        head = push(head, 4); 
        head = push(head, 4); 
        head = push(head, 4); 
  
        Console.WriteLine("Original Doubly LinkedList"); 
        printList(head); 
  
        /* remove duplicate nodes */
        removeDuplicates(head); 
        Console.WriteLine(" Doubly linked list after"
                            "removing duplicates:"); 
        printList(head); 
    
  
public class Node 
    public int data; 
    public Node next,prev; 
  
    public Node(int data) 
    
        this.data = data; 
        next = null
        prev = null
    
  
// This code is contributed by 29AjayKumar.


Output:

Original Doubly linked list:
4 4 4 4 6 8 8 10 12 12
Doubly linked list after removing duplicates:
4 6 8 10 12

Time Complexity: O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter