Remove Duplicates from a Sorted Doubly Linked List

Approach for Solving

We are following the simple approach for solving the problem. The steps to approach the problem is listed below:-

1. We go linearly for the problem statement; to check if a duplicate is found, we call the delete function to remove it or move forward.
2. For solving, we transverse the linked list and will check if curr.data is equal to curr.data.next or not:
3. If we traverse and find curr.data==curr.data.next equal, we have a duplicated element deleted, then we have to call the deleteNode function to delete the duplicate element.
4. If we found curr.data!=curr.data.next, we have no duplicate element. We move to the next nodes of the linked list using curr=curr.next.
5. Now After iterating over the list till we encounter curr.next!=null, then after we have a doubly-linked list if curr.next==null, then after it is free from the duplicate.

Code

public class RemoveDuplicate {
 class Node{
  int data;
  Node next;
  Node prev;
  public Node(int data){
    this.data=data;
  }
}
Node head=null;
Node tail=null;

 // Adding the element to the doubly linked list 
 public void addNode(int data){
  Node newNode=new Node(data);
  if(head==null){
    head=tail=newNode;
    head.prev=null;
    tail.next=null;
  }
  else {
    tail.next=newNode;
    newNode.prev=tail;
    tail=newNode;
    tail.next=null;
  }
}
 // Printing the element present in the Doubly Linked List
 public void print_DLL(){
  Node curr=head;
  if(curr==null){
    System.out.println("List is Empty, Kindly insert data in it");
  }
  while(curr!=null){
    System.out.print(curr.data+" ");
    curr=curr.next;
  }
}

 // Perform the Deletion in the Doubly Linked List for the Duplication
 public void deleteNode(Node head, Node curr){
  // Base Case
  if(head==null||curr==null){
    return;
  }
  //If we have to delete the head node
  if(head==curr){
    head=curr.next;
  }
  // We change the next, when the node to be deleted is not the last node
  if(curr.next!=null){
    curr.next.prev=curr.prev;
  }
  // We change the prev when the node to be deleted is not the head node
  if(curr.prev!=null) {
    curr.prev.next = curr.next;
  }
}
 // Calling function if the duplicate element found in the doubly linked list
 public void removeDuplicate(){
  if(head==null){
    return;
  }
  Node curr=head;
  while(curr.next!=null){
    if(curr.data==curr.next.data){
      deleteNode(head,curr.next);
    }
    else{
      curr=curr.next;
    }
  }
}
 // Driver Code to run the program for Removing the Duplication of the number in a list.
 public static void main(String[] args){
  RemoveDuplicate dll=new RemoveDuplicate();
  dll.addNode(1);
  dll.addNode(5);
  dll.addNode(5);
  dll.addNode(6);
  dll.addNode(9);
  dll.addNode(9);
  dll.addNode(9);
  System.out.println("Doubly Linked List: Containing the data in a sorted manner with duplication ! ");
  dll.print_DLL();
  dll.removeDuplicate();
  System.out.println();
  System.out.println("Doubly Linked List: Containing the data after removing all the duplication !");
  dll.print_DLL();
}
}

You can also try this code with Online C++ Compiler

Run Code

Dry-Run

There are mainly four steps we are following for dealing with the problem:-

1. Creating the Doubly Linked List.
2. Calling the Remove Duplicate function.
3. Calling the DeleteNode if the duplication is found.
4. Printing the modified Doubly Linked List.

Now we take an example and perform the task:

Doubly Linked List are: 1<-> 5<->5<->5<->6<->9<->9<->9

Expected output are: 1<->5<->6<->9

1. Now create a function, addNode for creating the doubly linked list, in which data is passed and the new node is created, if head==null, then insert as the first node with next and prev node address as null, for the next time when we encounter the next node then we have also had to move to next node using another node as the tail. Hence, we make a connection over the list as the previous and next addresses of the nodes.
2. Intaillized head=null and tail=null, both of them initially, and proceeded with step-1.
3. After that, we call a function, Remove duplicate for deletion of the multiple occurring elements in the Linked List.
4. Here we have head=1; then we create another node for iteration over the linked list, curr=1 now, then under the while loop we run when we have curr.next!=null.
5. Now we check for the cure.data!=curr.data.next , 1!=5 then we move the curr=curr.next = 5.
6. Now we check for curr.data==curr.data.next , 5==5 then we call a deleteNode and pass the head and curr.next node, for deletion of the next node, found to be duplicated.
   1. For the deletion Node, we follow the major 4 conditions.
   2. If head==null and curr==null, then return null, as we have nothing to find duplicates of, only a single element.
   3. If the curr and head are equal, we have to delete the first node and move the head from the next node.
   4. Now, if we have not deleted the last node, we change the next of curr.
   5. Now, if we have not deleted the head node, we change the prev of curr.
   6. The above steps should be followed while doing the duplication delete operation.
7. As we see, the step-6 step is called, and the deletion of a node is performed.
8. We repeated steps-4, 5, and 6 till we reached the end of the list.
9. At last, we just printed the modified Linked List.

Complexity

Talking about the Time and Space Complexity of the Problem, if we talk about the Time Complexity we see that we have to move from the start of the Linked List to the end and check for the conditional statement, at every node as curr.data==curr.next.data, which in general going to happen for the Length of the Linked List. So Time Complexity for the Problem is O(N), where N is the length of the Doubly Linked List.

If we think about the Space Complexity, we are doing modifications only on the same Linked List, so we have constant space in O(1) times.

Check out this problem - Duplicate Subtree In Binary Tree

Frequently Asked Questions

What is a doubly Linked List?

Doubly Linked List contains a link element called first and last. Each link is linked with its next link using its next link. Each link is linked with its previous link using its previous link. 

What is Time Complexity and Space Complexity for Removing duplication?

Time Complexity is O(N), and Space Complexity is O(1).

What does Remove duplicate mean?

Delete the element that comes more than once except the element itself, in general taking a unique element only.

What is Sorting?

Order the data in an increasing or decreasing fashion according to some linear relationship among the data items.

Conclusion

In this blog, we discuss the Doubly Linked List and its attachment with the next and previous node; when we encounter duplicates how we will delta when the node data are given in a sorted manner, with a descriptive way of Explanation with optimized Time Complexity of O(N) where N is the length of the Linked List and Space Complexity with the constant space with O(1) time.

Recommended Reading:

• Application of Linked List
• Merge One Linked List into another at an alternate position
• Remove Duplicates from a Sorted Linked List
• Remove Duplicates from an unsorted Linked List
• How to remove duplicates from an unsorted doubly linked list
• Sort the bitonic Doubly Linked List
• Rotate Doubly Linked List by N nodes

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!