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:
  • value: Valu stored in a Node
  • next: Reference to the following Node (May b None)
• init(self, value: T, next: Node = None) -> None:
  • This function initializes a nod with a given value and next reference, pointing to the next Node in the list.
  • self.valu - the value of the Node.
  • self.next - the next Node in the list, dfault value is None
• repr(self) -> str:
  • A nod is represented in string form as value.
• str(self) -> str:
  • A nod is represented in string form as value. Use str(node) to make it a string.
• eq(self, other: Node) -> bool:
  • This function compars two Nodes.
  • other - the right-hand operand of th ==
  • Returns ither True or False

class SinglyLinkedList:

Do not modify the following attributs/methods

• Attributes:
  • head: The first Nod in the linked list (May be None)
• init(self) -> None:
  • This function initializs a SinglyLinkedList
• repr(self) -> str:
  • A string representation of th list.
  • For this to work, you must hav completed to_string
• eq(self, other: SLL) -> bool:
  • This function compars two SinglyLinkLists.
  • other - the right-hand operand of th ==
  • Rturns either True or False

You must implement the following functions in solution.py. Take not of the specified return values, input parameters, and time complexity requirments. Do not chang the function signatures.

***Down below are the incomplete functions that need to modify!***

• to_string(self) -> str:

  • Generat and return a string representation of the list

  • The values should be separated by a --> (a space followed by two hyphens, a greater than symbol, and then another spac)

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

  • Return the string "None" if there are no nodes in th list.

  • You are allowd to use strings in this function.

  • Time complexity: O(n), assuming string concatenation mthod is O(1)

    • BONUS: +2 points of extra credit if you can gt the function O(n) without this assumption. See this link (refers to Java, but the same idea applies in Python) for more information as to why string concatenation is, in general, NOT O(1)

• length(self) -> str:

  • Determines the number of nods in the list

  • If the list is empty, it has a lngth of 0.

  • Time complxity: O(n)

• sum_list(self) -> T:

  • Calculats and returns the sum of the values in the list, assuming all values in the list are of the same type T

  • If the list is mpty, return None.

  • Note that this must work with any type T, whther T is an integer, a string, etc. How can you get the starting value of the correct type for your summation?

  • Tim complexity: O(n), assuming addition operation is O(1)

• push(self, value: T) -> None:

  • Insrt the given value into the linked list

  • The value should b inserted at the end of the list

  • Tim complexity: O(n)

• remove(self, value: T) -> bool:

  • Remov the first node in the list with the given value

  • If the valu doesnt exist, do not change the linked list

  • Returns a bool indicating if anything was successfully dleted

  • Tim complexity: O(n)

• remove_all(self, value: T) -> bool:

  • Remov all nodes in the list with the given value

  • If the valu doesnt exist, do not change the linked list

  • Rturns a bool indicating if anything was successfully deleted

  • Tim complexity: O(n)

• search(self, value: T) -> bool:

  • Looks for valu in the list

  • Rturns True if the value is in the list and False if it is not in the list

  • Tim complexity: O(n)

• count(self, value: T) -> int:

  • Counts and rturns how many times the given value occurs in the list

  • Tim complexity: O(n)

In this application problem, you are a data scientist working in a lab that monitors th output of a seismometer. Seismometers detect movement of the Earth's surface, detcting events such as earthquakes. Your seismometer reads its signal and outputs the data into a linked list. In your specific case, outputs that are perfect squares indicat a data point of interest to your manager. For whatever rason, when the data reads a perfect square, the software crashes! You need to figure out, based on historical data, what the longest time between crashes has been, as this information will hlp with the repair of the software your teammate is working on.

To do this, you will implement on function:

• max_crash_dist(data: SLL)-> int
  • Given a linked list data, dtermine the maximum distance between two perfect square numbers with non in between.
  • Return the max distanc between two perfect squares, or 0 if two or more don't exist.
  • You may not use any additional data structures other than linked lists in this function - this includes no python lists, dictionaries, and sets!
  • Tim complexity: O(n)
    • Note a tim complexity of O(np), where n is the number of elements in the list and p is the number or perfect squares in the list, is not allowed. You must solve the problem in one pass through th list.

This is the part that does not need to modify

Here is the part that needs to modify! (The question)

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 `Node` type class SLLNode: """ Node implementation Do not modify. """ __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) + ' )' def __repr__(self) -> str: """ Overloads `repr()` method for use in debugging return: string """ return '(Node: ' + str(self.val) + ' ) def __eq__(self, other: Node) -> bool: """ Overloads `==` operator to compare nodes :param other: right 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 """ self.head = None def __repr__(self) -> str: """ Represents an SLL as a string DO NOT MODIFY THIS FUNCTION """ return self.to_string() def __eq__(self, other: SLL) -> bool: """ Overloads `==` operator to compare SLLs :param other: right hand operand of `==` :return: `True` if 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 :return: number of nodes in list """ def sum_list(self) -> T: """ Sums the values in the list :return: 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 """ def remove(self, value: T) -> bool: """ Removes the first node containing `value` from the SLL :param value: value to remove :return: bool 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` if found, else `False` """ def count(self, value: T) -> int: """ Returns the number of occurrences of `value` in this list :param value: value to count :return: number of time the value occurred """ def 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, 0 if two or more perfect squares do not exist """