**Homework 9: Linked Lists** **Reed CSCI 121 Spring 2025**   *complete the exercises by 9am on 4/8* In the problems below you are asked to write linked list methods. Work from the starting code for linked lists that we showed you in lecture, [*available for download here.*](LinkedList.py) In some of the problems, we ask you to extend the class definition with a new method. In others, we ask you to write code for a class from scratch. For those, you can use our code to make some of the methods for that new class. Note that our testing code examines the structure of the linked list of nodes your code makes. You need to name attributes the way we do in our sample code so that our tests can examine the objects' underlying linked structure. --- (##) `[Hw9 Ex1]` diagram Consider the following code that works with our `Node` class: ~~~ none >>> from LinkedList import Node >>> a = Node(45) >>> b = Node(19) >>> c = Node(7) >>> d = Node(23) >>> e = Node(38) >>> f = Node(26) >>> g = Node(31) >>> a.next = b >>> b.next = f >>> c.next = b >>> d.next = f >>> e.next = a >>> f.next = g >>> g.next = e ~~~ Draw a diagram of the structure that results from the code lines above. In your picture, draw each `Node` object as a box that contains an integer, its `value`, along with an arrow pointing to its `next` node. You need not show the references for variables `a` through `g` since nodes can be identified by their value. Now, using as few lines of code as is necessary, change the link structure so that the nodes form a (valid) linked list with `c` as the first node in the list and `a` as the last node. The values of the nodes in the linked list should be in increasing order from first to last. The code should only change `next` attributes of some nodes. It should not change any of `value` attributes. Submit (a photo of) the diagram on Gradescope, and submit the lines of code on Gradescope. They will not be autograded. (##) `[Hw9 Ex2]` sum Add a method called `sum` to the the `LinkedList` class that computes and returns the sum of all the values held in the nodes of the linked list. ~~~ none >>> ll = LinkedList() >>> ll.append(7) >>> ll.append(10) >>> ll.append(1) >>> ll <7, 10, 1> >>> ll.sum() 18 ~~~ (##) `[Hw9 Ex3]` count Add a method called `count` to the `LinkedList` class that takes a value and returns how many times that value appears in the nodes of the linked list. ~~~ none >>> ll = LinkedList() >>> ll.append(7) >>> ll.append(10) >>> ll.append(1) >>> ll.append(7) >>> ll <7, 10, 1, 7> >>> ll.count(10) 1 >>> ll.count(7) 2 >>> ll.count(6) 0 ~~~ (##) `[Hw9 Ex4]` repeat Add a method `repeat` to the class `LinkedList`. It should modify the linked list by doubling its number of nodes. Each value in the original list should be repeated in succession in the modified list. ~~~ none >>> lst = LinkedList() >>> lst.append(7) >>> lst.append(10) >>> lst.append(7) >>> lst.append(1) >>> lst <7, 10, 7, 1> >>> lst.repeat() >>> lst <7, 7, 10, 10, 7, 7, 1, 1> ~~~ Your code for `repeat` should keep the original nodes of the linked list and insert new nodes for each of the repeats. Each new node should immediately follow the original node whose value it repeats. This means that, in the "7, 7, 10..." sequence just above, the first 7 is held by an original node, the second 7 is held by a new node, the first 10 is held by an original node, the second 10 is held by a new node, and so on. (##) `[Hw9 Ex5]` Sorted Write a different class named `Sorted` that has the same `__init__`, `asString`, and `delete` methods as `LinkedList`. Rather than it supporting `prepend` and `append`, it should instead have an `insert` method. To do this work, just write the code for `Node` and `Sorted` in a new file, and cut and paste the code for the three methods it borrows from `LinkedList`. Also include the two lines that define `__repr__` and `__str__`. Then write your code for the `insert` method. The `insert` method should place new nodes into the linked list in the order of their values. The first node should hold the smallest value, and the subsequent nodes should be at least as large, or larger, than this first value. And so on. Moving down the nodes from the first to the last, the values should be in sorted order. ~~~ none >>> ll = Sorted() >>> ll.insert(7) >>> ll.insert(10) >>> ll.insert(1) >>> ll <1, 7, 10> >>> ll.insert(7) >>> ll <1, 7, 7, 10> ~~~ Your `insert` method should never modify `value` attributes of nodes once they have been created. Instead, it should link new nodes into the list structure in a way that maintains its sorted order. (##) `[Hw9 Ex6]` rotate left Add a method called `rotateLeft` to our `LinkedList` class. It takes a non-negative integer, let's call it `n`. It should restructure the list so that the first `n` nodes are moved to the back of the list, moving the other nodes to the front. If `n` is 0 or is at least as large as the length of the list, there should be no change to the list. ~~~ none >>> lst = LinkedList() >>> lst.append(7) >>> lst.append(10) >>> lst.append(1) >>> lst.append(6) >>> lst.append(3) >>> lst <7, 10, 1, 6, 3> >>> lst.rotateLeft(3) >>> lst <6, 3, 7, 10, 1> >>> lst.rotateLeft(5) >>> lst <6, 3, 7, 10, 1> >>> lst.rotateLeft(1) >>> lst <3, 7, 10, 1, 6> ~~~ Your code should restructure the links of the nodes. No new node objects should be created by the method.