**Homework 10: Linked Lists** **Reed CSCI 121 Fall 2022**   *complete the exercises by 9am on 11/22* **Note the due date for this assignment.** In the problems below you are asked to develop a series of linked list methods and also classes of objects that use lists of linked nodes as their underlying representation. You should 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 will ask you to extend the class definition with a new method. In others, we will ask you to devise a class from scratch, but you can use our code to make your methods for that new class. For these new classes, our testing code will be examining the structure of the linked list of nodes your code makes. You need to follow our instructions carefully, naming the instance variables the way we prescribe them so that our tests can examine the objects' underlying linked structure. --- (##) `[HW10 P1]` 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. ~~~ python >>> ll = LinkedList() >>> ll.append(7) >>> ll.append(10) >>> ll.append(1) >>> ll.display() <7, 10, 1> >>> ll.sum() 18 ~~~ (##) `[HW10 P2]` 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. ~~~ python >>> ll = LinkedList() >>> ll.append(7) >>> ll.append(10) >>> ll.append(1) >>> ll.append(7) >>> ll.display() <7, 10, 1, 7> >>> ll.count(10) 1 >>> ll.count(7) 2 >>> ll.count(6) 0 ~~~ (##) `[HW10 P3]` apply Add a method called `apply` to the `LinkedList` class that takes a function as its argument. It should modify each of the values in the nodes with the value of that function applied to it. ~~~ python >>> ll = LinkedList() >>> ll.append(7) >>> ll.append(10) >>> ll.append(1) >>> ll.display() <7, 10, 1> >>> ll.apply(lambda x: x*x) >>> ll.display() <49, 100, 1> >>> ll.apply(lambda x: x+1) >>> ll.display() <50, 101, 2> ~~~ (##) `[HW10 P4]` sorted list Within the same file, add a new class definition `Sorted` that inherits from `LinkedList`. It should instead maintain the items that are appended in sorted order. To do this, you'll want to override the `append` method of `LinkedList` objects by writing a new `append` method under the class `Sorted`. It should insert nodes into the list in the order of their keys. The first node should hold the smallest item, and the subsequent nodes should be at least as large, or larger than this first item. Moving down the nodes from the first to the last, the values should be in sorted order. You need not change or add any other methods to this class. ~~~ python >>> ll = Sorted() >>> ll.append(7) >>> ll.append(10) >>> ll.append(1) >>> ll.display() <1, 7, 10> ~~~ (##) `[HW10 P5]` delete all Add a new method `deleteAll` to class `LinkedList` that takes a value and modifies the linked list so that all nodes with that value are removed. If no nodes have that value, the list should not be changed. ~~~ python >>> ll = LinkedList() >>> ll.append(7) >>> ll.append(10) >>> ll.append(7) >>> ll.append(1) >>> ll.display() <7, 10, 7, 1> >>> ll.deleteAll(7) >>> ll.display() <10, 1> >>> ll.deleteAll(1) >>> ll.display() <10> ~~~ (##) `[HW10 P6]` Queue There is a common collection for organizing a sequence of items called a `Queue`. The two main methods of queues are `enqueue` which places an item onto the queue, and `dequeue` which removes an item from the queue. A `dequeue` always removes the *least recently added* item from the queue. A queue can be thought of as a line of items, where a new item gets added to the back of the line with `enqueue`, and where `dequeue` removes the item from the front. The front item is often called the "head" item of the queue. Create a new `Queue` class. Write it's code so that it stores its elements using a linked list. We've [*provided a template of the code at this link*](Queue.py) that you can complete by replacing each of the `pass` lines with a method's code. In addition to `__init__`, which makes an empty `Queue`, it should also have the methods `enqueue`, `dequeue`, and `head`. Write the code so that it maintains two instance variables `first` and `last`. When the queue is empty, both its `self.first` and `self.last` should be `None`. When the queue has several items, `self.first` should contain the node with the value that's been sitting in the queue the longest. This would be the value that was least recently added, the head item. The next node after `self.first` should contain the value that was added after the "head", and so on, all the way to the node at the end, which should contain the value most recently added. The variable `self.last` should be that last node in the list. When a value is added to the queue with `enqueue`, a new node should be placed at the end of the list, and `self.last` should be changed to refer to that new node. When a value is removed with `dequeue` the node referenced by `self.first` should be removed and `self.first` should change to the next node in the linked list. The `dequeue` method should return the value that was held in that removed node. The `head` method should return the head value, but not remove it from the queue. If the queue is empty, the `head` method should return `None`. When a queue has only one item, `self.first` and `self.last` will be referring to the same node in the linked list. ~~~ python >>> q = Queue() >>> q.enqueue(7) >>> q.enqueue(10) >>> q.enqueue(1) >>> q.head() 7 >>> q.dequeue() 7 >>> q.head() 10 >>> q.enqueue(8) >>> q.dequeue() 10 >>> q.head() 1 ~~~ (##) `[HW10 P7]` doubly-linked Let's now devise a new linked list class with a different node type, one that provides a "doubly-linked" list which we describe below. We'll name the new class 'DLinkedList' and its node class 'DLLNode'. In a doubly-linked list, nodes have a link to both the *previous* and the next node in their structure. That means that each 'DLLNode' should have a `value`, a `next`, and a `prev`. The use of `value` and `next` are as before for singly-linked lists. As before, a node's `next` refers to the node that follows it in the linked structure. In addition, a node's `prev` refers to the node that *precedes it* in the linked structure. When a node is the last in the linked list, its `next` should be `None`. If a node is the first in the linked list, its `prev` should be `None`. For any node that is neither the first or the last, its `next` node should have it as `prev`. Its `prev` node should have it as `next`. That is to say, for any node `n` sitting somewhere in the middle of a doubly-linked list ~~~ python n.next.prev == n ~~~ and ~~~ python n.prev.next == n ~~~ Rewrite the code for the *original* `LinkedList.py` source we provided. Call it `DLinkedList.py` and name its classes `DLLNode` and `DLinkedList`. Its `DLLNode` class should build doubly-linked nodes that contain both `next` and `prev` attributes. A `DLinkedList` object should have two attributes: `first` and `last`. When the list is empty, these should both be set to `None`. When the list has length one, that one node should be both the `first` and the `last`. When the list is longer, `first` should refer to that list's first node and `last` should refer to that list's last node. Write the `append`, `insert`, and `delete` methods of `DLinkedList` so that they modify both `next` and `prev` when nodes are linked and unlinked with these methods. They should also modify the `first` and `last` references in cases where those parts of the list structure change. Note that the other methods we wrote for `LinkedList` will not need to be changed for `DLinkedList`. They will still work since they only inspect the nodes in the list (they don't modify them) and rely only on the `next` attribute of nodes and the `first` attribute of lists.