Write a function that counts the number of times a given int occurs in a Linked List

Given a singly linked list and a key, count number of occurrences of given key in linked list. For example, if given linked list is 1->2->1->2->1->3->1 and given key is 1, then output should be 4.

Method 1- Without Recursion
Algorithm:

1. Initialize count as zero.
2. Loop through each element of linked list:
     a) If element data is equal to the passed number then
        increment the count.
3. Return count.

Implementation:

C++

// C++ program to count occurrences in a linked list  
#include <bits/stdc++.h> 
using namespace std; 
  
/* Link list node */
class Node  
{  
    public: 
    int data;  
    Node* next;  
};  
  
/* Given a reference (pointer to pointer) to the head  
of a list and an int, push a new node on the front  
of the list. */
void push(Node** head_ref, int new_data)  
{  
    /* allocate node */
    Node* new_node = new Node(); 
  
    /* put in the data */
    new_node->data = new_data;  
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);  
  
    /* move the head to point to the new node */
    (*head_ref) = new_node;  
}  
  
/* Counts the no. of occurences of a node  
(search_for) in a linked list (head)*/
int count(Node* head, int search_for)  
{  
    Node* current = head;  
    int count = 0;  
    while (current != NULL)  
    {  
        if (current->data == search_for)  
        count++;  
        current = current->next;  
    }  
    return count;  
}  
  
/* Drier program to test count function*/
int main()  
{  
    /* Start with the empty list */
    Node* head = NULL;  
  
    /* Use push() to construct below list  
    1->2->1->3->1 */
    push(&head, 1);  
    push(&head, 3);  
    push(&head, 1);  
    push(&head, 2);  
    push(&head, 1);  
  
    /* Check the count function */
    cout<<"count of 1 is "<<count(head, 1);  
    return 0;  
}  
  
//This is code is contributed by rathbhupendra 

C

// C program to count occurrences in a linked list 
#include<stdio.h> 
#include<stdlib.h> 
  
/* Link list node */
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 
  
/* Given a reference (pointer to pointer) to the head 
  of a list and an int, push a new node on the front 
  of the list. */
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node = 
            (struct Node*) malloc(sizeof(struct Node)); 
  
    /* put in the data  */
    new_node->data  = new_data; 
  
    /* link the old list off the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node; 
} 
  
/* Counts the no. of occurences of a node 
   (search_for) in a linked list (head)*/
int count(struct Node* head, int search_for) 
{ 
    struct Node* current = head; 
    int count = 0; 
    while (current != NULL) 
    { 
        if (current->data == search_for) 
           count++; 
        current = current->next; 
    } 
    return count; 
} 
  
/* Drier program to test count function*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
  
    /* Use push() to construct below list 
     1->2->1->3->1  */
    push(&head, 1); 
    push(&head, 3); 
    push(&head, 1); 
    push(&head, 2); 
    push(&head, 1); 
  
    /* Check the count function */
    printf("count of 1 is %d", count(head, 1)); 
    return 0; 
} 

Java

// Java program to count occurrences in a linked list 
class LinkedList 
{ 
    Node head;  // head of list 
  
    /* Linked list Node*/
    class Node 
    { 
        int data; 
        Node next; 
        Node(int d) {data = d; next = null; } 
    } 
  
    /* Inserts a new Node at front of the list. */
    public void push(int new_data) 
    { 
        /* 1 & 2: Allocate the Node & 
                  Put in the data*/
        Node new_node = new Node(new_data); 
  
        /* 3. Make next of new Node as head */
        new_node.next = head; 
  
        /* 4. Move the head to point to new Node */
        head = new_node; 
    } 
  
    /* Counts the no. of occurences of a node 
    (search_for) in a linked list (head)*/
    int count(int search_for) 
    { 
        Node current = head; 
        int count = 0; 
        while (current != null) 
        { 
            if (current.data == search_for) 
                count++; 
            current = current.next; 
        } 
        return count; 
    } 
  
    /* Drier function to test the above methods */
    public static void main(String args[]) 
    { 
        LinkedList llist = new LinkedList(); 
  
        /* Use push() to construct below list 
          1->2->1->3->1  */
        llist.push(1); 
        llist.push(2); 
        llist.push(1); 
        llist.push(3); 
        llist.push(1); 
  
        /*Checking count function*/
        System.out.println("Count of 1 is "+llist.count(1)); 
    } 
} 
// This code is contributed by Rajat Mishra 

/div>

Python

# Python program to count the number of time a given 
# int occurs in a linked list 
  
# Node class  
class Node: 
  
    # Constructor to initialize the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
class LinkedList: 
  
    # Function to initialize head 
    def __init__(self): 
        self.head = None
  
    # Counts the no . of occurrences of a node 
    # (search_for) in a linked list (head) 
    def count(self, search_for): 
        current = self.head 
        count = 0
        while(current is not None): 
            if current.data == search_for: 
                count += 1
            current = current.next
        return count 
  
    # Function to insert a new node at the beginning 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 
  
    # Utility function to print the linked LinkedList 
    def printList(self): 
        temp = self.head 
        while(temp): 
            print temp.data, 
            temp = temp.next
  
  
# Driver program 
llist = LinkedList() 
llist.push(1) 
llist.push(3) 
llist.push(1) 
llist.push(2) 
llist.push(1) 
  
# Check for the count function 
print "count of 1 is %d" %(llist.count(1)) 
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007) 

C#

// C# program to count occurrences in a linked list  
using System; 
class LinkedList  
{  
    Node head; // head of list  
  
    /* Linked list Node*/
    public class Node  
    {  
        public int data;  
        public Node next;  
        public Node(int d) {data = d; next = null; }  
    }  
  
    /* Inserts a new Node at front of the list. */
    public void push(int new_data)  
    {  
        /* 1 & 2: Allocate the Node &  
                Put in the data*/
        Node new_node = new Node(new_data);  
  
        /* 3. Make next of new Node as head */
        new_node.next = head;  
  
        /* 4. Move the head to point to new Node */
        head = new_node;  
    }  
  
    /* Counts the no. of occurrences of a node  
    (search_for) in a linked list (head)*/
    int count(int search_for)  
    {  
        Node current = head;  
        int count = 0;  
        while (current != null)  
        {  
            if (current.data == search_for)  
                count++;  
            current = current.next;  
        }  
        return count;  
    }  
  
    /* Drier function to test the above methods */
    public static void Main(String []args)  
    {  
        LinkedList llist = new LinkedList();  
  
        /* Use push() to construct below list  
        1->2->1->3->1 */
        llist.push(1);  
        llist.push(2);  
        llist.push(1);  
        llist.push(3);  
        llist.push(1);  
  
        /*Checking count function*/
        Console.WriteLine("Count of 1 is "+llist.count(1));  
    }  
}  
// This code is contributed by Arnab Kundu 

Output:

count of 1 is 3

Time Complexity: O(n)
Auxiliary Space: O(1)

Method 2- With Recursion
This method is contributed by MY_DOOM.
Algorithm:

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

Implementation:

C++

// C++ program to count occurrences in 
// a linked list using recursion 
#include <bits/stdc++.h> 
using namespace std; 
  
/* Link list node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
// global variable for counting frequeancy of  
// given element k 
int frequency = 0; 
  
/* Given a reference (pointer to pointer) to the head 
of a list and an int, push a new node on the front 
of the list. */
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list off the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
  
/* Counts the no. of occurences of a node 
(search_for) in a linked list (head)*/
int count(struct Node* head, int key) 
{ 
    if (head == NULL) 
        return frequency; 
    if (head->data == key) 
        frequency++; 
    return count(head->next, key); 
} 
  
/* Driver program to test count function*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
   
    /* Use push() to construct below list 
     1->2->1->3->1  */
    push(&head, 1); 
    push(&head, 3); 
    push(&head, 1); 
    push(&head, 2); 
    push(&head, 1); 
   
    /* Check the count function */
    cout<<"count of 1 is " <<count(head, 1); 
    return 0; 
} 

Java

// Java program to count occurrences in  
// a linked list using recursion 
import java.io.*; 
import java.util.*; 
  
// Represents node of a linkedlist 
class Node  
{ 
    int data; 
    Node next; 
    Node(int val) 
    { 
        data = val; 
        next = null; 
    } 
}  
  
class GFG  
{ 
          
    // global variable for counting frequeancy of  
    // given element k 
    static int frequency = 0;  
  
    /* Given a reference (pointer to pointer) to the head  
    of a list and an int, push a new node on the front  
    of the list. */
  
    static Node push(Node head, int new_data) 
    { 
        // allocate node 
        Node new_node = new Node(new_data); 
  
        // link the old list off the new node 
        new_node.next = head; 
  
        // move the head to point to the new node 
        head = new_node; 
  
        return head; 
    } 
  
    /* Counts the no. of occurences of a node  
    (search_for) in a linked list (head)*/
    static int count(Node head, int key) 
    { 
        if (head == null) 
            return frequency; 
        if (head.data == key) 
            frequency++; 
        return count(head.next, key); 
    } 
  
    // Driver Code 
    public static void main(String args[]) 
    { 
        // Start with the empty list 
        Node head = null; 
          
        /* Use push() to construct below list  
        1->2->1->3->1 */
        head = push(head, 1);  
        head = push(head, 3);  
        head = push(head, 1);  
        head = push(head, 2);  
        head = push(head, 1);  
      
        /* Check the count function */
        System.out.print("count of 1 is " + count(head, 1)); 
    } 
} 
  
// This code is contributed by rachana soma 

Python3

# Python program to count the number of  
# time a given int occurs in a linked list 
# Node class 
class Node: 
      
    # Constructor to initialize the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
class LinkedList: 
      
    # Function to initialize head 
    def __init__(self): 
        self.head = None
        self.counter = 0
          
    # Counts the no . of occurances of a node 
    # (seach_for) in a linkded list (head) 
    def count(self, li, key):      
          
        # Base case  
        if(not li):  
            return self.counter 
          
        # If key is present in  
        # current node, return true  
        if(li.data == key):  
            self.counter = self.counter + 1
          
        # Recur for remaining list  
        return self.count(li.next, key)  
  
    # Function to insert a new node  
    # at the beginning 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 
  
    # Utility function to print the  
    # linked LinkedList 
    def printList(self): 
        temp = self.head 
        while(temp): 
            print (temp.data) 
            temp = temp.next
  
# Driver Code 
llist = LinkedList() 
llist.push(1) 
llist.push(3) 
llist.push(1) 
llist.push(2) 
llist.push(1) 
  
# Check for the count function 
print ("count of 1 is", llist.count(llist.head, 1)) 
  
# This code is contributed by  
# Gaurav Kumar Raghav 

Output:

count of 1 is 3

Below method can be used to avoid Global variable ‘frequency'(counter in case of Python 3 Code).

C++

// method can be used to avoid  
// Global variable 'frequency' 
  
/* Counts the no. of occurences of a node  
(search_for) in a linked list (head)*/
int count(struct Node* head, int key)  
{  
    if (head == NULL)  
        return 0;  
    if (head->data == key)  
        return 1 + count(head->next, key);  
    return count(head->next, key);  
}  

Java

// method can be used to avoid  
// Global variable 'frequency' 
  
/* Counts the no. of occurences of a node  
(search_for) in a linked list (head)*/
int count(Node head, int key) 
{ 
    if (head == null) 
        return 0; 
    if (head.data == key) 
        return 1 + count(head.next, key); 
    return count(head.next, key); 
} 
  
  
// This code is contributed by rachana soma 

Python3

def count(self,temp, key): 
      
    # during the initial call, temp 
    # has the value of head 
      
    # Base case 
    if temp is None: 
        return 0
          
    # if a match is found, we  
    # increment the counter 
    if temp.data == key: 
        return 1 + count(temp.next, key) 
    return count(temp.next, key) 
      
# to call count, use 
# linked_list_name.count(head, key) 

The above method implements head recursion. Below given is the tail recursive implementation for the same. Thanks to Puneet Jain for suggesting this approach :

int count(struct Node* head, int key)
{
    if(head == NULL)
        return 0;
        
   int frequency = count(head->next, key);
   if(head->data == key)
     return 1 + frequency;
    
    // else 
    return frequency;
}

Time Complexity: O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Write a function that counts the number of times a given int occurs in a Linked List

C++

C

Java

Python

C#

C++

Java

Python3

C++

Java

Python3

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books