Singly Linked List Exercise (In Python)

• All of your functions must be iterative!
• Do not use additional data structures!
• No hardcoding test cases!

Specifications

class Node:

Do not modify this class

• Attributs:

  • valu: Valu stord in a Nod

  • nxt: Rfrnc to th following Nod (May b Non)

• init(slf, valu: T, nxt: Nod = Non) -> Non:

  • This function initializs a nod with a givn valu and nxt rfrnc, pointing to th nxt Nod in th list.

  • slf.valu - th valu of th Nod.

  • slf.nxt - th nxt Nod in th list, dfault valu is Non

• rpr(slf) -> str:

  • A nod is rprsntd in string form as valu.

• str(slf) -> str:

  • A nod is rprsntd in string form as valu. Us str(nod) to mak it a string.

• q(slf, othr: Nod) -> bool:

  • This function compars two Nods.

  • othr - th right-hand oprand of th ==

  • Rturns ithr Tru or Fals

class SinglyLinkdList:

Do not modify th following attributs/mthods

• Attributs:

  • had: Th first Nod in th linkd list (May b Non)

• init(slf) -> Non:

  • This function initializs a SinglyLinkdList

• rpr(slf) -> str:

  • A string rprsntation of th list.

  • For this to work, you must hav compltd to_string

• q(slf, othr: SLL) -> bool:

  • This function compars two SinglyLinkLists.

  • othr - th right-hand oprand of th ==

  • Rturns ithr Tru or Fals

You must implmnt th following functions in solution.py. Tak not of th spcifid rturn valus, input paramtrs, and tim complxity rquirmnts. Do not chang th function signaturs.

• to_string(slf) -> str:

  • Gnrat and rturn a string rprsntation of th list

  • Th valus should b sparatd by a --> (a spac followd by two hyphns, a gratr than symbol, and thn anothr spac)

    • Mak sur to avoid a training " --> "!

  • Rturn th string "Non" if thr ar no nods in th list.

  • You ar allowd to us strings in this function.

  • Tim complxity: O(n), assuming string concatnation mthod is O(1

• lngth(slf) -> str:

  • Dtrmins th numbr of nods in th list

  • If th list is mpty, it has a lngth of 0.

  • Tim complxity: O(n)

• sum_list(slf) -> T:

  • Calculats and rturns th sum of th valus in th list, assuming all valus in th list ar of th sam typ T

  • If th list is mpty, rturn Non.

  • Not that this must work with any typ T, whthr T is an intgr, a string, tc. How can you gt th starting valu of th corrct typ for your summation?

  • Tim complxity: O(n), assuming addition opration is O(1)

• push(slf, valu: T) -> Non:

  • Insrt th givn valu into th linkd list

  • Th valu should b insrtd at th nd of th list

  • Tim complxity: O(n)

• rmov(slf, valu: T) -> bool:

  • Rmov th first nod in th list with th givn valu

  • If th valu dosnt xist, do not chang th linkd list

  • Rturns a bool indicating if anything was succssfully dltd

  • Tim complxity: O(n)

• rmov_all(slf, valu: T) -> bool:

  • Rmov all nods in th list with th givn valu

  • If th valu dosnt xist, do not chang th linkd list

  • Rturns a bool indicating if anything was succssfully dltd

  • Tim complxity: O(n)

• sarch(slf, valu: T) -> bool:

  • Looks for valu in th list

  • Rturns Tru if th valu is in th list and Fals if it is not in th list

  • Tim complxity: O(n)

• count(slf, valu: T) -> int:

  • Counts and rturns how many tims th givn valu occurs in th list

  • Tim complxity: O(n)

In this application problm, you ar a data scintist working in a lab that monitors th output of a sismomtr. Sismomtrs dtct movmnt of th arth's surfac, dtcting vnts such as arthquaks. Your sismomtr rads its signal and outputs th data into a linkd list. In your spcific cas, outputs that ar prfct squars indicat a data point of intrst to your managr. For whatvr rason, whn th data rads a prfct squar, th softwar crashs! You nd to figur out, basd on historical data, what th longst tim btwn crashs has bn, as this information will hlp with th rpair of th softwar your tammat is working on.

To do this, you will implmnt on function:

• max_crash_dist(data: SLL)-> int

  • Givn a linkd list data, dtrmin th maximum distanc btwn two prfct squar numbrs with non in btwn.

  • Rturn th max distanc btwn two prfct squars, or 0 if two or mor don't xist.

  • You may not us any additional data structurs othr than linkd lists in this function - this includs no python lists, dictionaris, and sts!

  • Tim complxity: O(n)

Not a tim complxity of O(np), whr n is th numbr of lmnts in th list and p is th numbr or prfct squars in th list, is not allowd. You must solv th problm in on pass through th list.

(I have attached the source code with images)

from typing import TypeVar # For use in type hinting # Type Declarations T = TypeVar('T) # generic type SLL = TypeVar('SLL) #forward declared Node = TypeVar('Node') #forward declare "Modetype class SLLNode: Node implementation Do not modily. slots__ = [val', 'next'] def_init__(self, value: T, next: Node = None) -> None: Initialize an SLL Node param value: value held by node param next: reference to the next node in the SLL return: None self.val = value self next = next def_str_(self) -> str. Overloads 'str() method to casts nodes to strings return:string return (Node:' + str(self.val) + 'Y def _repr_(selt) -> str: Overloads 'repr() method for use in debugging retur:string return 'Node: ' + str(self.val) +') def _eq_(self, other: Node) -> bool: Overloads =='operator to compare nodes param other night operand of '--' return: bool return self.val == other val if other is not None else False class SinglyLinkedList: Implementation of an SLL slots__ = ['head') def_init__(self) -> None: Initializes an SLL return: None DO NOT MODIFY THIS FUNCTION selt head = None det_repr_(self) > str Represents an SLL as a string DO NOT MODIFY THIS FUNCTION return self.to_string() det _eq_(self, other: SLL) -> bool: Overloads '' operator to compare SLLS param other right hand operand of return: 'True' i' equal, else 'False DO NOT MODIFY THIS FUNCTION comp = lambda n1, n2: n1 == n2 and (comp(n1.next, n2.next) if (n1 and n2) else True) return comp(self head, other head) ===== Modify below === def to_string(self) -> str. Converts an SLL to a string return:string representation of the linked list def length(self) -> int: Determines number of nodes in the list :retur: number of nodes in list def sum_list(self) ->T: Sums the values in the list :retur: sum of values in list def push(self, value: T)-> None: Pushes a SLLNode to the end of the list param value: value to push to the list return: None w def remove(self, value: T) -> bool: Removes the first node containing 'value' from the SLL param value: value to remove returnbool whether or not deleted def remove_all(self, value: T) -> bool: Removes all instances of a node containing 'value' from the SLL param value: value to remove return; bool whether any were deleted def search(self, value: T) -> bool: Searches the SLL for a node containing 'value' param value: value to search for return: 'True' f found, else False def count(self, value: T)->int: Returns the number of occurrences of value in this list param value: value to count retur: number of time the value occurred det max_crash_dist(data: SLL) -> int: Figure out the furthest distance between two perfect square numbers, with none in between :return: int with the distance between, o if two or more perfect squares do not exist