Counts the number of times a given element occurs in a Linked List

Counts the number of times a given element occurs in a Linked List

This article will explain how we can count the occurrences of a particular element in a list. Here, we have given a singly linked list and a key, and we need to count the number of occurrences of the key in the linked list.

Example:

                   List is:  1 -> 2 -> 1 -> 2 -> 1 -> 3 -> 1 -> 4            Key: 2

                   Output: 2

Method 1: By using loop

1. Firstly, we will initialize the count as zero.

2. Then, we will traverse the entire linked list via loop

• If element data is equal to the passed number
• Increment the count.

3. Finally, return count.

Source code to implement this method using C programming:

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // counts the number of times a given element occurs in a Linked List
 int count(struct node * start, int key)
 {
     struct node * temp = start;
     int count = 0;
     while (temp != NULL) {
         if (temp -> info == key)
             count++;
         temp = temp -> next;
     }
     return count;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     int key;
     add(1);
     add(2);
     add(1);
     add(3);
     add(1);
     add(4);
     add(2);
     add(2);
     add(0);
     add(1);
     printf("Given Linked List: \n");
     traverse(start);
     printf("Enter the key:");
     scanf("%d",&key);
     int c = count(start,key);
     printf("count is: %d" , c);
     return 0;
 } 

Output:

Time Complexity: O(n)

Auxiliary Space: O(1)

Method 2: By using recursion

Algorithm:

count(head, key); 
if head is NULL    
return frequency if(head -> data==key)   
increase frequency by 1   
count(head -> next, key)

Source code to implement this method using C programming:

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 int freq = 0;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node *)malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // counts the number of times a given element occurs in a Linked List
 int count(struct node * start, int key)
 {
     if(start == NULL)
             return freq;
     if(start -> info == key)
             freq++;
     return count(start -> next, key);
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next != NULL)
                                     {
                         printf("%d -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 // Driver Function
 int main()
 {
     int key;
     add(1);
     add(2);
     add(1);
     add(3);
     add(1);
     add(4);
     add(2);
     add(2);
     add(0);
     add(1);
     printf("Given Linked List: \n");
     traverse(start);
     printf("Enter the key:");
     scanf("%d",&key);
     int c = count(start,key);
     printf("count is: %d" , c);
     return 0;
 } 

Output:

Time Complexity: O(n)

Auxiliary Space: O(1)