1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in C++
4.
4.1.
4.2.
Difference between unordered_set and set in C++?
4.3.
Is unordered_set always better than set?
5.
Conclusion
Last Updated: Mar 27, 2024

# Count Duplicates in Circular Linked List

SHIKHAR SONI
0 upvote

## Introduction

The following article aims to familiarise you with using a circular linked list (if this is a new topic for you, refer to the article here) data structure and practice its use in real questions to build and strengthen your concepts. The following question explores how we can traverse a circular linked list and find the count of duplicate elements using a hash set.

## Problem Statement

Count the number of duplicate elements in a circular linked list, i.e., elements that have already occurred before, and print the count as the final result.

For example,

Input 1: [1, 2, 3, 1, 2]

In the above input [1, 2, 3, 1 <-, 2 <-], the numbers marked by arrows are duplicates.

Output 1: 2

Input 2: [5, 5, 5, 5]

In the above input [5, 5 <-, 5 <-, 5 <-], similar to input 1, arrows mark the duplicate elements.

Output 2: 3

## Approach

In the below code, our purpose is to count the number of duplicates, and we achieve this by using a hash set. The use of a hash set (unordered_set in C++ STL) is generally preferred because of its O(1) retrieval and insertion time on average.

The algorithm requires us to traverse through the circular linked list once and check if that element is present in the hash set for each iteration. If the element exists in the hash set, then itâ€™s a duplicate, and we increase the duplicate count; otherwise, we insert the element into the hash set as it hadnâ€™t occurred before.

After having traversed through all the elements of the hash set, we end up with the count of the duplicate elements in the circular linked list, and we print that as the final result.

### Code in C++

``````#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
class Node{
public:
int val;
Node *next;
Node(int x){
val = x;
next = NULL;
}
};
int main(){

// let us store all the content in the below vector into the circular linked list
vector<int> data = {10, 1, 1, 7, 5, 5, 5};

for(int i = 1; i < data.size(); i++){
temp->next = new Node(data[i]);
temp = temp->next;
}
temp->next = head; // the end element points back to the head, making it a circular linked list

//from here on we have the logic for counting the duplicates
int duplicates = 0;
unordered_set<int> s;
do{
if(s.find(loop_var->val) != s.end()){
// if a previous occurence is found
duplicates += 1;
}
else{
s.insert(loop_var->val);
}
loop_var = loop_var->next;
}

// print the total duplicates
// [10, 1, 1 <-, 7, 5, 5 <-, 5 <-]
// I have put arrows next to the duplicates and we expect an output of 3 for the given input
cout << duplicates << endl;
}``````

Output:

``3``

Time Complexity

The time complexity is O(N), as we traverse each element of the list once, and the retrieval from the unordered_set is O(1) on average for random data. (Do note, however, that unordered_set can have O(N) retrieval and insertion in a worst-case under particular inputs.)

Space Complexity

The space complexity is O(N) because of the unordered_set data structure, where we store elements to check for their earlier occurrence in the circular linked list.

It can implement circular linked list queues and various advanced data structures such as Fibonacci heaps. They can also be helpful in multiple other situations repeatedly requiring iteration over the same data.

### Difference between unordered_set and set in C++?

The set data structure is usually implemented using a red-black tree (read more about it here). The unordered_set, however, is implemented using a hash table and hence offers an average O(1) retrieval and insertion. In contrast,a set data structure takes O(log(n)) for retrieving and inserting an element.

### Is unordered_set always better than set?

No, the unordered_set will usually work well with random data and give O(1) retrieval and insertion on average. Still, in case of excessive collisions (which can be the case for some specific inputs, depending on the hash function), our retrieval and insertion may become O(N).

## Conclusion

The article helps you understand and implement your knowledge of circular linked lists and C++ STL. I also recommend checking the program for multiple inputs to understand the process better if you still have some doubts.

In the code, you may have noticed my use of a do-while loop instead of a while loop. I encourage you to try the same problem with a while loop, observe the difference in implementation, and decide if itâ€™s better and easier to use a do-while loop in the case of circular linked lists.