Count duplicates in circular linked list

SHIKHAR SONI
Last Updated: May 13, 2022

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) 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};
  Node *head = new Node(data[0]);
  Node *temp = head;
  
  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;
  Node *loop_var = head;
  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;
  }
  while(loop_var != head);
  
  // 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.

Frequently Asked Questions

1. What are the advantages of learning about circular linked lists?

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.

2. 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, set data structure takes O(log(n)) for retrieving and inserting an element.

3. 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).

Key Takeaways

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.

Learn more about vector and other data structures in C++ STL from the following link: here and Happy learning!

 

Was this article helpful ?
0 upvotes