Learn how to count duplicates in a linked list in C++ with this beginner-friendly guide. Step-by-step explanation, easy-to-understand code, and tips for detecting duplicate nodes efficiently.
Linked lists are one of the fundamental data structures in programming. While they are simple to understand, performing operations like counting duplicates can be tricky for beginners. In this guide, we will explain how to count duplicates in a linked list in an easy-to-understand, step-by-step way.
What is a Linked List?
A linked list is a collection of nodes where each node contains two things:
- Data – The value stored in the node.
- Pointer (Next) – A reference to the next node in the list.
For example, a linked list can look like this:
1 → 2 → 2 → 3 → 3 → 3 → 4
What Are Duplicates in a Linked List?
Duplicates are values that appear more than once in the linked list.
In the example above:
2appears twice → 1 duplicate3appears three times → 2 duplicates
Total duplicates = 3
Step-By-Step Approach to Count Duplicates
Here’s a simple way to count duplicates, perfect for beginners:
- Start with the first node (
curr). - Compare it with all nodes that come after it (
temp). - If a node has the same value as
curr, it’s a duplicate. - Move to the next node and repeat until the end.
Understanding the Key Line: Node* temp = curr->next;
One line often confuses beginners:
Node* temp = curr->next;Here’s what it means:
Node* temp→tempis a pointer that can point to a node.curr->next→ the next node after the current node.- Together →
tempstarts checking from the node aftercurr, not from the beginning. This avoids counting the same value multiple times.
Count Duplicates in a Linked List : C++ Code
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
// Function to count duplicates
int countDuplicates(Node* head) {
int count = 0;
Node* curr = head;
while (curr != NULL) {
Node* temp = curr->next; // Start checking from next node
while (temp != NULL) {
if (curr->data == temp->data) {
count++;
break; // Count only once per value
}
temp = temp->next;
}
curr = curr->next;
}
return count;
}
// Main function
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(2);
head->next->next->next = new Node(3);
head->next->next->next->next = new Node(3);
head->next->next->next->next->next = new Node(3);
head->next->next->next->next->next->next = new Node(4);
cout << "Total duplicate nodes: " << countDuplicates(head) << endl;
return 0;
}
How This Works
currpointer moves node by node.temppointer checks all nodes aftercurr.- If
curr->data == temp->data, we found a duplicate. - Count is updated once per duplicate value.
Time and Space Complexity
- Time Complexity: O(n²) – two nested loops
- Space Complexity: O(1) – no extra memory used
Note: For beginners, this approach is easy to understand. Advanced methods (like using a hash map) can reduce time complexity.
Time Complexity
Answer:
Time Complexity = O(n²)
Why O(n²)? (How we calculate it)
Look at this part of the code:
while (curr != NULL) { // Outer loop
Node* temp = curr->next;
while (temp != NULL) { // Inner loop
if (curr->data == temp->data) {
count++;
break;
}
temp = temp->next;
}
curr = curr->next;
}
Step-by-step thinking
- Let total number of nodes = n
Outer loop (curr)
- Runs for every node
- So it runs n times
Inner loop (temp)
- For each
curr, it checks the remaining nodes - In worst case:
- First time → checks ~ (n-1) nodes
- Second time → checks ~ (n-2) nodes
- …
- Last time → checks 1 node
Total comparisons (worst case)
(n-1) + (n-2) + (n-3) + ... + 1
This adds up to:
n² (approximately)
That’s why Time Complexity = O(n²)
Simple line to remember (for exams/interviews)
Since there are two nested loops, the time complexity is O(n²).
Space Complexity
Answer:
Space Complexity = O(1)
Why O(1)? (How we calculate it)
Let’s see what extra memory we use:
int count;
Node* curr;
Node* temp;
- These are just variables and pointers
- They do not grow with input size
- No arrays, maps, or extra lists are used
What we are NOT using
- No extra linked list
- No hash map
- No array
So memory usage stays constant, no matter how big the linked list is.
Therefore, Space Complexity = O(1)
Final Summary (Perfect for Notes)
| Type | Complexity |
|---|---|
| Time Complexity | O(n²) |
| Space Complexity | O(1) |
Tips for Beginners
- Use two loops to make your logic clear.
- Always check from the next node, not from the head again.
- Use visual examples to understand how
currandtempwork.
Frequently Asked Questions (FAQ)
1. What is a duplicate in a linked list?
A duplicate is a node whose value appears more than once in a linked list. For example, in the list 1 → 2 → 2 → 3, the value 2 is a duplicate because it appears twice.
2. Why do we use Node* temp = curr->next?
This line ensures that we start checking for duplicates from the node after the current one (curr). It avoids re-checking nodes and makes counting accurate.
3. Can we count duplicates in a sorted linked list faster?
Yes! In a sorted linked list, duplicates are always next to each other. So, we can use a single loop to compare each node with the next, which reduces time complexity from O(n²) to O(n).
4. What is the time complexity of this method?
The beginner-friendly method using two nested loops has O(n²) time complexity, where n is the number of nodes in the list.
5. Can we count duplicates without using extra space?
Yes, the method shown in this guide uses O(1) extra space, meaning no additional memory is required apart from the linked list itself.
6. How is this different from using a hash map?
Using a hash map can reduce the time complexity to O(n), but it uses extra memory to store counts. The method in this guide is memory-efficient and easier for beginners to understand.
7. Can this method handle strings or other data types?
Yes, as long as the linked list stores comparable data (like integers, characters, or strings), you can modify the comparison curr->data == temp->data accordingly.