This article will find the number of occurrences of an element in a linked list using Recursion. Specifically, we will be taking a singly linked list, which means that every node will have data and reference the next node.

Let’s go ahead and see how to find the total count of a given element.

Number of Occurrences of an Element in the Linked List using Recursion

The recursive countNumberOfOccurrences method takes the current node of the linked list and the target element. Initially, the head of the linked list will be passed as the current node. The idea is to get to the end of the linked list first and then return the count by comparing the current node’s value with the target element.

The base case checks if the head is NULL, i.e., the end of the linked list. If it is, then we return 0 as the count.
Otherwise, we recursively call the countNumberOfOccurrences method with the next node and the target element. Then, we check if the value of the current node is equal to the given one. If it is, we increment the count by one. Otherwise, we return the same count.

Implementation

The implementation of the above approach is below.

#node for the linked list
class Node:
  def __init__(self, value=None):
    self.value = value 
    self.next = None #reference to the next node

#implementation of linked list
class LinkedList:
  def __init__(self):
    self.head = None
    self.length = 0 #total number of elements in the linked list

  #adds a node at the end of the linked list
  def insert(self, value):
    node = Node(value) #create a node
    if self.head == None: #if list is empty insert a node at the start
      self.head = node
    else:
      temp = self.head
      #iterate through the list till last node is found
      while temp.next: 
        temp = temp.next 
      
      temp.next = node #adding a new node
      self.length += 1 #increment the length

  #traverse the complete list and print the node value
  def traverse(self):
    temp = self.head
    while temp:
      print(temp.value, end="\t")
      temp = temp.next
    print("")

#finds the total number of times an element exists in the linked list
def countNumberOfOccurrences(current_node, element):
  if current_node == None:
    return 0
  count = countNumberOfOccurrences(current_node.next, element)
  if current_node.value == element: #if the current node's value is equal to the given value, then increase the count by one
    return count + 1
  else:
    return count


ll = LinkedList() #create list

#insert values
ll.insert(1)
ll.insert(5)
ll.insert(1)
ll.insert(0)
ll.insert(5)
ll.insert(1)

print("The given Linked list:")
ll.traverse()

n = 1
count = countNumberOfOccurrences(ll.head, n)
print(f"Count of an element {n} is: {count}")

n = 5
count = countNumberOfOccurrences(ll.head, n)
print(f"Count of an element {n} is: {count}")

n = 3
count = countNumberOfOccurrences(ll.head, n)
print(f"Count of an element {n} is: {count}")

Output

The given Linked list:
1	5	1	0	5	1	
Count of an element 1 is: 3
Count of an element 5 is: 2
Count of an element 3 is: 0