.png)
Count Occurrences in a Linked List
Problem Statement
Given a singly linked list and a value X, your task is to count how many times X occurs in the linked list.
Understanding the Problem
You are required to:
- Traverse the linked list
- Compare each node’s data with the given value X
- Count the total number of matches
Example
Input Linked List
1 → 2 → 1 → 3 → 1 → 4 → NULL
X = 1
Output
3
Explanation:
The value 1 appears three times in the linked list.
Important Edge Cases
- Linked list is empty
- Value X does not exist in the list
- Linked list has only one node
- All nodes contain the same value
Approach 1: Iterative Traversal (Most Common & Recommended)
Idea
Traverse the linked list node by node, compare each node’s data with X, and increment a counter whenever a match is found.
This is the simplest and most efficient approach.
Algorithm
- Initialize count = 0
- Start traversal from head
- If current.data == X, increment count
- Move to the next node
- Continue until NULL
- Return count
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Implementation –
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
// Function to count occurrences (Iterative)
int countOccurrences(struct Node* head, int x) {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
if (temp->data == x)
count++;
temp = temp->next;
}
return count;
}
// Function to insert node at end
struct Node* insert(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
int main() {
struct Node* head = NULL;
// Creating: 1 → 2 → 1 → 3 → 1 → 4
int arr[] = {1,2,1,3,1,4};
int n = 6;
for(int i = 0; i < n; i++)
head = insert(head, arr[i]);
int x = 1;
printf("Count of %d: %d\n", x, countOccurrences(head, x));
return 0;
}Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CountOccurrences {
static int countOccurrences(Node head, int x) {
int count = 0;
Node temp = head;
while (temp != null) {
if (temp.data == x)
count++;
temp = temp.next;
}
return count;
}
}
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def count_occurrences(head, x):
count = 0
temp = head
while temp:
if temp.data == x:
count += 1
temp = temp.next
return countOutput-
Count of 1: 3Approach 2: Recursive Method
Idea
Use recursion to:
- Check the current node
- Recursively count occurrences in the remaining list
This approach is elegant but less efficient due to function call overhead.
Recursive Relation
count(head, x) =
1 + count(head.next, x) if head.data == x
count(head.next, x) otherwise
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n) (recursive call stack)
Implementation –
C Implementation (Recursive)
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
// Recursive function
int countOccurrencesRecursive(struct Node* head, int x) {
if (head == NULL)
return 0;
if (head->data == x)
return 1 + countOccurrencesRecursive(head->next, x);
return countOccurrencesRecursive(head->next, x);
}
// Insert function
struct Node* insert(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
int main() {
struct Node* head = NULL;
// Creating: 1 → 2 → 1 → 3 → 1 → 4
int arr[] = {1,2,1,3,1,4};
int n = 6;
for(int i = 0; i < n; i++)
head = insert(head, arr[i]);
int x = 1;
printf("Count of %d: %d\n", x, countOccurrencesRecursive(head, x));
return 0;
}
Java Implementation (Recursive)
static int countOccurrencesRecursive(Node head, int x) {
if (head == null)
return 0;
if (head.data == x)
return 1 + countOccurrencesRecursive(head.next, x);
return countOccurrencesRecursive(head.next, x);
}
Python Implementation (Recursive)
def count_occurrences_recursive(head, x):
if head is None:
return 0
if head.data == x:
return 1 + count_occurrences_recursive(head.next, x)
return count_occurrences_recursive(head.next, x)
Output-
Count of 1: 3Approach 3: Using Hashing (Extra Space Approach)
Idea
Store the frequency of each element using a hash map during traversal.
Then return the count of X.
. This approach is not optimal for this problem but useful for learning.
When Is This Useful?
- When multiple frequency queries are required
- When list values repeat frequently
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n)
Implementation –
Java Implementation (Using HashMap)
import java.util.HashMap;
static int countOccurrencesHash(Node head, int x) {
HashMap map = new HashMap<>();
Node temp = head;
while (temp != null) {
map.put(temp.data, map.getOrDefault(temp.data, 0) + 1);
temp = temp.next;
}
return map.getOrDefault(x, 0);
}
Python Implementation (Using Dictionary)
def count_occurrences_hash(head, x):
freq = {}
temp = head
while temp:
freq[temp.data] = freq.get(temp.data, 0) + 1
temp = temp.next
return freq.get(x, 0)C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
#define MAX 100 // assuming values are between 0–99
struct Node {
int data;
struct Node* next;
};
// Function to count using hashing
int countOccurrencesHash(struct Node* head, int x) {
int freq[MAX] = {0}; // initialize all frequencies to 0
struct Node* temp = head;
while (temp != NULL) {
freq[temp->data]++; // increment frequency
temp = temp->next;
}
return freq[x];
}
// Insert function
struct Node* insert(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
int main() {
struct Node* head = NULL;
// Creating: 1 → 2 → 1 → 3 → 1 → 4
int arr[] = {1,2,1,3,1,4};
int n = 6;
for(int i = 0; i < n; i++)
head = insert(head, arr[i]);
int x = 1;
printf("Count of %d: %d\n", x, countOccurrencesHash(head, x));
return 0;
}Output-
Count of 1: 3Comparison of All Approaches
| Approach | Time | Space | Traversal | Recommended |
|---|---|---|---|---|
| Iterative | O(n) | O(1) | 1 | Yes |
| Recursive | O(n) | O(n) | 1 | Limited |
| Hashing | O(n) | O(n) | 1 | No |
Common Mistakes Students Make
- Forgetting to initialize counter
- Missing NULL condition
- Incorrect recursion base case
- Using extra space unnecessarily
- Confusing node count with value count
Interview Perspective
- Interviewers expect iterative traversal
- Recursive approach is good for discussion
- Hashing approach should be avoided unless asked
Variations to Practice
- Count occurrences of all elements
- Count frequency in sorted linked list
- Find the most frequent element
- Remove nodes with a given frequency
- Count occurrences in circular linked list
Summary
- Counting occurrences is a basic but essential linked list problem
- Iterative approach is optimal
- Recursion builds conceptual depth
- Understanding this problem strengthens traversal logic
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
