# 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 ` `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 "``<

## C

 `// C program to count occurrences in a linked list ` `#include ` `#include ` ` `  `/* 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
return frequency
increase frequency by 1
```

Implementation:

## C++

 `// C++ program to count occurrences in ` `// a linked list using recursion ` `#include ` `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 "` `<

## 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)
{
return 0;

return 1 + frequency;

// else
return frequency;
}
```

Time Complexity: O(n)