Example: >>> x=SortedLinkedList() >>> x.add(4.5) >>> x.add(-3) >>> x.add(0) >>> x.add(5) >>> x.add(-9) >>> x.add(12.7) >>> x.add(-3.5) >>> x.add(2) >>> x.add(4) >>> x.add(1) >>> x.add(3) >>> x.add(2) >>> x Head:Node(-9) Tail:Node(12.7) List:-9 -> -3.5 -> -3 -> 0 -> 1 -> 2 -> 2 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> sublst1, sublst2 = x.split() >>> sublst1 Head:Node(-9) Tail:Node(2) List:-9 -> -3.5 -> -3 -> 0 -> 1 -> 2 >>> sublst2 Head:Node(2) Tail:Node(12.7) List:2 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> x.add(2) >>> x.add(2) >>> x.add(2) >>> x.add(3) >>> x.add(3) >>> x.add(-12) >>> x Head:Node(-12) Tail:Node(12.7) List:-12 -> -9 -> -3.5 -> -3 -> 0 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> x.add(-3) >>> x Head:Node(-12) Tail:Node(12.7) List:-12 -> -9 -> -3.5 -> -3 -> -3 -> 0 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> sublst1, sublst2 = x.split() >>> sublst1 Head:Node(-12) Tail:Node(2) List:-12 -> -9 -> -3.5 -> -3 -> -3 -> 0 -> 1 -> 2 -> 2 -> 2 >>> sublst2 Head:Node(2) Tail:Node(12.7) List:2 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> sublst1.removeDuplicates() >>> sublst2.removeDuplicates() >>> sublst1 Head:Node(-12) Tail:Node(2)

List:-12 -> -9 -> -3.5 -> -3 -> 0 -> 1 -> 2 >>> sublst2 Head:Node(2) Tail:Node(12.7) List:2 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> x Head:Node(-12) Tail:Node(12.7) List:-12 -> -9 -> -3.5 -> -3 -> -3 -> 0 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4.5 -> 5 -> 12.7 >>> x.removeDuplicates() >>> x Head:Node(-12) Tail:Node(12.7) List:-12 -> -9 -> -3.5 -> -3 -> 0 -> 1 -> 2 -> 3 -> 4 -> 4.5 -> 5 -> 12.7

The SortedLinkedList class (10 points) In our Hands On - Linked List I and II lecture from Module 5, we worked on the implementation of a Singly Linked List. That data structure keeps the elements of the linked list unsorted. Based on the LinkedList class code completed during the video-lecture, implement the data structure SortedLinkedList with the following methods: REMINDER: You are not allowed to use break or continue statements, swap data between nodes or to copy data from the linked lists into another structure such as a Python list or using any Python built-in copy methods. add(self, item) (3 points) adds a new Node with value = item to the list making sure that the ascending order is preserved. It needs the item and returns nothing but modifies the linked list. The items in the list might not be unique, but you can assume every value will be numerical (int and float). - You are not allowed to traverse the linked list more than once (only one loop required). Preconditions item: int/float > numerical value Returns: None Examples: split(self) (3 points) Divides the original list in half, returning two new instances of SortedLinkedList, one with the first half, and another one with the second half. If the number of nodes is odd, the extra node should go in the first half. It does not mutate the original list. Method returns None if the original list is empty. Preconditions Returns: None > if the original list is empty SortedLinkedList, SortedLinkedList two linked list objects removeDuplicates(self) (2 points) Removes any duplicate nodes from the list, so it modifies the original list. This method must traverse the list only once. Values such as 2 and 2.0 are considered duplicates. Preconditions Returns: None