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.
Python Programming:
# 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 occurances of a node
# (seach_for) in a linkded 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)
Output:
count of 1 is 3
Time Complexity: O(n)
Auxiliary Space: O(1)
[ad type=”banner”]