Question

Write a function that counts the number of times a given integer occurs in a Linked List. What is the time complexity of your algorithm? Justify your answer in python

Answer 1

CODE:

#node structure
class Node(object):
   next=None
   def __init__(self,data):
       self.data=data

class Linked_List(object):
   def __init__(self):
       self.head=None

    #inserting node in the begning
   def push_beg(self,data):
       newNode=Node(data)
      
       #if head is null
       if self.head is None:
           self.head=newNode
       else:
            #if head is not null
           newNode.next=self.head
           self.head=newNode
      
   #getting of count of item
   def getCount(self,data):
        temp2=self.head
        count=0
        #iterate unless node is null
        while(temp2 is not None):
            #if item matches the item, increment count by 1
            if temp2.data==data:
                count+=1
            temp2=temp2.next
       #returns the total count
        return count  
      
list=Linked_List()

#inserting values in Linked_List
list.push_beg(4)
list.push_beg(5)
list.push_beg(3)
list.push_beg(4)
list.push_beg(1)

#input of item to be searched
n = int(input("Enter number to be searched and counted: "))
#calling method to be searched
print("Count of Item is ",list.getCount(n))

SCREENSHOT:

OUTPUT