Question

​​​​​​This is an assignment that I'm having trouble figuring out in python:

• Modify Node class so it has a field called frequency and initialize it as one.

• Add a search function. If a number is in the list, return its frequency.

• Modify Insert function. Remove push, append, and insertAfter as one function called insert(self, data). If you insert a data that is already in the list, simply increase this node’s frequency. If the number is not in the list, add it to the beginning of the list.

• Modify Delete function. When you delete a node, reduce its frequency. If frequency becomes zero, remove the node from the list.

• Modify Print function to print out all the numbers with their frequency in the list.

The program that we are suppose to modify:

class Node:
def __init__(self,d):
self.data=d;# data in the node
self.next=None #address of next node
"""add a field called frequency here"""
class LinkedList:
def __init__(self):
self.head=None #linked list at the beginning is empty. head is None
  
def print(self):#print every node's data
temp=self.head#let temp points to head
while temp:#As long as temp is not None (the end)
"""modify print, so frequency is also printed out frequency """
print(temp.data,end="")#print data
temp=temp.next # let temp points to the next Node
print()
"""complete the folloing function """   
def insert(self,d):
temp=self.head
"""
travel the list like print, if d is in there break the loop
if yes, increase its freq
if not add it the front of the list like "push"
"""
  
  

"""
def push(self,new_d):#will add new node at the beginning
newNode=Node(new_d) #create a Node
newNode.next=self.head #Let new Node's next to be the original head
self.head=newNode #update head as the New Node
def insertAfter(self,prev_data, new_data):
temp=self.head#let temp be the head
while temp and temp.data!=prev_data:#as long temp is not None and data is not prev_data
temp=temp.next
#if you can get here. One of the condition must be false
if temp==None:#There is no prev_data because you have reached the end
print("The given previous node does not exist")
return
#if you can reach here, temp.data=prev.data
newNode=Node(new_data)#create a new node after Node temp
  
newNode.next=temp.next#make newNode's next as temp's next
temp.next=newNode# make temp's(prev) next as NewNode
def append(self,new_data):# add new_data at the end of the list
newNode=Node(new_data)#create a Node with new_data

if self.head==None:#in case the list is empty
self.head=newNode
return

last=self.head#let last be head
while last.next:#as long last next is not None, continue
last=last.next# let last as its next
#when loop terminates, last.next is None, therefore last points to the last Node
last.next=newNode
"""
def delete(self,key):#delete a Node with data "key"
temp=self.head #let temp be head
if temp is not None:#if list is not empty
if temp.data==key:#if key is at the first Node
"""reduce temp'frequency
if its frequency becomes 0, execute the next three lines"""
self.head=temp.next #let head to head's next
temp=None
return
  
while temp is not None:#if list is not empty
if temp.data==key:#loop ends if key is found
break
prev=temp#prev is node before
temp=temp.next
#Loop ends either temp is None or loop ends because of "break" which means key is found
if temp==None:
return #return because key is not in the list
#when temp.data is same as key
"""reduce temp'frequency
if its frequency becomes 0, execute the next three lines"""
prev.next=temp.next
temp=None
  
  
  
  
  
list=LinkedList()
list.insert(5)
list.insert(9)
list.insert(5)
list.insert(6)
list.insert(6)
list.insert(9)

list.print()
list.delete(5)
list.print()
list.delete(5)
list.print()
list.delete(6)
list.print()
list.delete(6)
list.print()

  

Answer 1

Modified classNode.py file

class Node:
        def __init__(self,d):
                self.data=d;# data in the node
                self.next=None #address of next node
                self.frequency = 1      #frequency of data in the node

class LinkedList:
        def __init__(self):
                self.head=None #linked list at the beginning is empty. head is None
          
        def print(self):#print every node's data
                temp=self.head#let temp points to head
                while temp:#As long as temp is not None (the end)
                        print(f"({temp.data}, {temp.frequency})",end="->")#print data
                        temp=temp.next #let temp points to the next Node
                print(None)#printing None at the end
          
        def insert(self, data):#inserting new node if not present else increasing its frequency
                temp=self.head  #temp points to head node
                while temp:     #As long as temp is not None
                        if temp.data == data:   #break loop if temp node data is given data
                                break
                        temp = temp.next        #temp now points to next node
                if temp:        #if temp is a valid addr and not None
                        temp.frequency += 1     #increase temp node frequency
                else:   #else if node not present
                        temp = Node(data)       #initialise a new Node in temp
                        temp.next = self.head   #point temp.next to head
                        self.head = temp        #now make temp as head node

        def search(self, data): #searches for given data and returns frequency if not present returns 0
                temp = self.head        #initially temp points to head node
                while temp:     #As long as temp is not None
                        if temp.data == data:   #if temp.data matches with given data
                                return temp.frequency   #returning temp.frequency
                        temp = temp.next        #now temp points to next node
                return 0        #if data is not found returning 0 as frequency

        def delete(self, key):  #deletes given key from linkedlist if present reduces frequncy and if frequency becomes 0 deletes that node
                temp = self.head        #initially points to head node
                prev = None     #And previous node is None so declared as None initially
                while temp:     #As long as temp is not None
                        if temp.data == key:    #if temp data matches with given key break
                                break
                        prev = temp     #previous points to temp (current node)
                        temp = temp.next        #temp points to next node
                if temp:        #if temp is not None
                        temp.frequency -= 1     #reduce frequency
                        if temp.frequency == 0: #if frequency becomes 0
                                if temp == self.head:   #if temp is head node
                                        self.head = temp.next   #updating the head node as next node to temp 
                                else:   #else
                                        prev.next = temp.next   #updating next node to previous node as next node to temp
                                del temp #deleting temp node as frequency is 0

#sample test

list=LinkedList()
list.insert(5)
list.insert(9)
list.insert(5)
list.insert(6)
list.insert(6)
list.insert(9)

list.print()
list.delete(5)
list.print()
list.delete(5)
list.print()
list.delete(6)
list.print()
list.delete(6)
list.print()

Screenshot of modified classNode.py file

Output Screenshot

Each and everything is explained clearly in the comment section of the code.

Thank you! Hit like if you like my work.