Remove duplicates from a sorted doubly linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

Given a sorted doubly linked list that contains duplicates elements. Our task is to remove the duplicates from the linked list.

Problem Statement Understanding

In this problem, we will be given a sorted doubly linked list containing some element occurring multiple times. We have to remove these duplicate occurrences of the elements.

Let’s try to understand the problem statement with the help of examples by referring the best online coding classes.

Let’s say the given linked list is:

  • According to the problem statement, we have to remove all the duplicate occurrences from the list.
  • In the given linked list, we can see that 5 and 9 are present multiple times. So, we have to remove duplicates of 5 and 9 present in the linked list.
  • After removing duplicates of 5 and 9 from the list, the final linked list which we will have is:

Let’s see if the given linked list is: head → 1 ←→ 3 ←→ 3 ←→ 3 ←→ 4 ←→ 5 ←→ 5

  • In this given linked list, 3 and 5 are present multiple times. So, we will remove duplicates of 3 and 5 present in the linked list. Our final linked list after removal of duplicates of 3 and 5 will be: head → 1 ←→ 3 ←→ 4 ←→ 5.

Now, I think from the above examples, it is clear what we have to do in the problem. So let’s see how we can approach it.

Before jumping directly into the approach section, first try to think how you can approach it. If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

Our approach will be simple:

  • We start traversing through the list and will check if the current→data is equal to the current→next→data or not:
    • If current→data is not equal to the current→next→data then we will move forward because it is possible only when there is a single node of the current→data in the linked list.
    • But if the current→data is equal to the current→next→data, we will delete all node's starting from the current→next up to the node having data same as current→data.
  • In the end, our linked list will be free from duplicate elements.

Algorithm

  • Initialize a pointer named current with head.
  • Start traversing through the linked list using current and do these steps until you reach NULL.
    • If the current node’s data is equal to the current→ next→ data, there are duplicates in the linked list, so we have to delete all the duplicates of current→ data.
    • If the current node’s data is not equal to the current→ next→ data, then move forward by assigning current = current→ next.

Dry Run

Code Implementation

#include 
using namespace std;

class DLLNode{
public:
    int data;
    DLLNode* next;
    DLLNode* prv;
    DLLNode(int data){
        this->data = data;
        this->next = NULL;
        this->prv = NULL;
    }
};

DLLNode* deleteNodes(DLLNode* head){
    //  initialize the starting and ending node  
    //  which we have to delete
    DLLNode *first = head, *last = head;
    while(last!=NULL && last->next!=NULL && last->data == last->next->data){
        last = last->next; // move last node to its correct position
    }

    DLLNode* temp = last->next;
    last->next = NULL;
    first->prv = NULL;
    delete first;
    return temp;
}

void removeDuplicates(DLLNode* head){
    if(head==NULL){
        return;
    }

    DLLNode *curr = head;
    while(curr->next != NULL){
        if(curr->data != curr->next->data){
            curr = curr->next;
        }else{
           DLLNode* temp = deleteNodes(curr->next);
           curr->next = temp;
           if(temp!=NULL){
           temp->prv = curr;
           }
        }
    }
}

void push(DLLNode** head_ref, int new_data){
    DLLNode* new_node = new DLLNode(new_data);
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main(){

    DLLNode* head = NULL;
    push(&head, 9);
    push(&head, 9);
    push(&head, 9);
    push(&head, 6);
    push(&head, 5);
    push(&head, 5);
    push(&head, 1);
    cout<<"Original Linked List: "<next)
        cout << temp->data << " ";
    cout<next)
        cout << temp->data << " ";
 
    return 0;
}

Output

Original Linked List:
1 5 5 6 9 9 9
Linked List after removing duplicates from a sorted doubly:
1 5 6 9

Time complexity: O(N), Since we have traversed through the list only once.

So, In this blog, we have learned How to remove duplicates from the sorted doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post How to Get First or Last entry from Java LinkedHashMap
Next post Binary search on Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *