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.

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. 

Java Programming:

[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20count%20occurrences%20in%20a%20linked%20list%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%0A%20%20%20%20%2F*%20Linked%20list%20Node*%2F%0A%20%20%20%20class%20Node%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%3B%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7Bdata%20%3D%20d%3B%20next%20%3D%20null%3B%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Inserts%20a%20new%20Node%20at%20front%20of%20the%20list.%20*%2F%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Put%20in%20the%20data*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%203.%20Make%20next%20of%20new%20Node%20as%20head%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Counts%20the%20no.%20of%20occurences%20of%20a%20node%0A%20%20%20%20(search_for)%20in%20a%20linked%20list%20(head)*%2F%0A%20%20%20%20int%20count(int%20search_for)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20current%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20int%20count%20%3D%200%3B%0A%20%20%20%20%20%20%20%20while%20(current%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(current.data%20%3D%3D%20search_for)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20count%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Drier%20function%20to%20test%20the%20above%20methods%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%20%20%20%20%20%201-%3E2-%3E1-%3E3-%3E1%20%20*%2F%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20llist.push(2)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20llist.push(3)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*Checking%20count%20function*%2F%0A%20%20%20%20%20%20%20%20System.out.println(%22Count%20of%201%20is%20%22%2Bllist.count(1))%3B%0A%20%20%20%20%7D%0A%7D%0A%2F%2F%20This%20code%20is%20contributed%20by%20Rajat%20Mishra%0A” message=”” highlight=”” provider=”manual”/]

Output:

count of 1 is 3

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

[ad type=”banner”]