Why the given code(Program to remove duplicates from a linked list using hashing) is not displaying any output?

Question

I want to write a program that will remove duplicates from a linked list and print the linked list.

I have used a hashing method to achieve this:

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node{
    int data;
    Node* next;
};

unordered_map<int,int> hashmap;
Node* head = NULL;

void deldups()
{
    Node* h = head;
    Node* prev = NULL;
    Node* curr;
    curr = h;
    
    while (curr != NULL)
    {
        int val = curr->data;
        if (hashmap.find(val) != hashmap.end())
        {
            if (hashmap[val] > 1)
            {
                prev->next = curr->next->next;
                delete(curr);
            }
        }
        else{
            ++hashmap[val];
            prev = curr;
        }
        curr = prev->next;
    }
}

void print()
{
    Node* temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

int main() 
{
    Node* firstnode = new Node();
    head = firstnode;
    firstnode->data = 5;

    Node* secondnode = new Node();
    firstnode->next = secondnode;
    secondnode->data = 6;

    Node* thirdnode = new Node();
    secondnode->next = thirdnode;
    thirdnode->data = 7;

    Node* forthnode = new Node();
    thirdnode->next = forthnode;
    forthnode->data = 5;

    Node* fifthnode = new Node();
    forthnode->next = fifthnode;
    fifthnode->data = 9;
    fifthnode->next = NULL;
    
    deldups();
    print();
    return 0;
}

Code Explanation:

1. Traverse the linked list while ptr is not NULL, check if the given element (h->data) is present in the map (unordered<int,int>).

   NOTE I am using the element as a key in the map and not its value, the value will be used to count its duplicates.

2. if the key is present then we will check its value, and if the value is greater than '1' i.e the element is present more than one time, then remove the node from the linked list.

3. else, add the element key into the hashmap and increment its value by 1.

After running the code, there is no output. Why?

Answer 1

The reason your code does not output anything is because deldups() is getting stuck in an infinite loop (which you would see if you run your code in a debugger, or at least have deldups() output what it is doing).

When hashmap.find() finds a duplicate, curr is not being advanced to the next node following the duplicate, so subsequent iterations are finding the same duplicate again and again. The reason curr is not being advanced is because the expression hashmap[val] > 1 is never true, as hashmap[val] is not being incremented above 1, so you are not removing the duplicate and advancing curr to the next node.

To fix that, you would need to check for > 0 instead of > 1. In which case, you don't actually need to count the duplicates anymore, you just need to know whether they exist, so using std::unordered_map becomes overkill. Using std::set instead would suffice.

After fixing that, this statement is also wrong:

prev->next = curr->next->next;

You are trashing your list by skipping nodes that don't need to be skipped. Also, if curr is the last node in the list, next will be NULL, so accessing next->next will be undefined behavior.

That statement needs to be this instead:

prev->next = curr->next;

With that said, try this:

#include <iostream>
#include <set>

using namespace std;

struct Node{
    int data;
    Node* next;
};

set<int> hashmap;
Node* head = NULL;

void deldups()
{
    Node* prev = NULL;
    Node* curr = head;
    
    while (curr != NULL)
    {
        int val = curr->data;
        if (!hashmap.insert(val).second)
        {
            prev->next = curr->next;
            delete curr;
        }
        else
        {
            prev = curr;
        }
        curr = prev->next;
    }
}

void print()
{
    Node* temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

int main() 
{
    Node* firstnode = new Node();
    head = firstnode;
    firstnode->data = 5;

    Node* secondnode = new Node();
    firstnode->next = secondnode;
    secondnode->data = 6;

    Node* thirdnode = new Node();
    secondnode->next = thirdnode;
    thirdnode->data = 7;

    Node* forthnode = new Node();
    thirdnode->next = forthnode;
    forthnode->data = 5;

    Node* fifthnode = new Node();
    forthnode->next = fifthnode;
    fifthnode->data = 9;
    fifthnode->next = NULL;
    
    deldups();
    print();

    return 0;
}

Online Demo

That being said, you might consider using the standard std::list or std::forward_list container instead of a manual linked-list implemented. Then, you would be able to use the standard std::unique() or std::remove_if() algorithm to remove duplicates.