Find the Number of Occurrences of an Element in a Linked List without using Recursion

A singly linked list is a linked list that contains a sequence of nodes, where each node has data and a reference to the next node. Today, we will explain how to find the number of occurrences of an element in the singly linked list.

Count  of Occurrences of an Element in a Linked List without using Recursion

We are going to use the iterative (non-recursive) approach to solve this problem. The steps of finding the frequency of a given element are given below.

  • The method takes the head of the linked list and the target element. We create a temp variable to traverse the linked list. Initially, it is equal to the head of the linked list. We also initialize the count variable with a zero value.
  • We start iterating over the linked list using a while loop. We continue till we reach the end of the linked list, i.e., temp is NULL. In each iteration, we compare the current node’s value with the given one. If both are equal, we increment the count by one.
  • Finally, we return the count variable as our final answer.

Implementation

The code of the above approach is as follows:

#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(head, element):
  temp = head
  count = 0
  while temp:
    if temp.value == element:  #if the current node's value is equal to the given value, then increase the count by one
      count += 1
    temp = temp.next #advance the linked list
  return count

ll = LinkedList()

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

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

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

n = 1
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	2	2	0	2	1	
Count of an element 2 is: 3
Count of an element 1 is: 2
Count of an element 3 is: 0

 

Back to: Data Structure > Data Structure - Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *