from typing import Any

class Node: """A node in singly-linked list"""

def __init__(self, node_data: Any) -> None: """Initialize this node with "payload" node_data. The node's link is initialized with the end-of-list marker (None). """ self._data = node_data self._next = None

def get_data(self) -> Any: """Return this node's payload.""" return self._data

def set_data(self, node_data: Any) -> None: """Replace this node's payload with node_data.""" self._data = node_data

data = property(get_data, set_data)

# Using 'Node' as a type annotation is the PEP 484 hack for handling # forward references. Starting with Python 3.10, we should be able to # use Node as a type annotation within the class.

def get_next(self) -> 'Node': """Return the reference (pointer) to the node that follows this node, or None if this node is at the end of a list. """ return self._next

def set_next(self, node_next: 'Node') -> None: """Append the node referred (pointed) to by node_next to this node.""" self._next = node_next

next = property(get_next, set_next)

def __str__(self) -> str: """Return a string representation of this node's payload.""" return str(self._data)

class LinkedDeque: """An implementation of a deque (double-ended queue).

The methods for adding items to the front or rear of a deque are O(1). The method for removing an item from the front of a deque is O(1). Unlike the deque class in the Python standard library, the method for removing an item from the rear of a deque is O(n). """ # The data structure underlying this implementation of ADT Deque is a # circular singly-linked list. # # A LinkedDeque object has two instance variables: # # _rear refers to the node at the rear of the deque; # i.e., the last (tail) node in the linked list. # # _size is the the number of items in the deque; # i.e., the number of nodes in the linked list.

def __init__(self, iterable=None) -> None: """Initialize this LinkedDeque with the contents of iterable.

Items are added to the rear of the deque in the order they are returned by the iterable. If iterable isn't provided, the new deque is empty.

>>> dq = LinkedDeque() >>> str(dq) 'None'

>>> dq = LinkedDeque([10, 20, 30]) >>> str(dq) '10 -> 20 -> 30'

>>> dq = LinkedDeque() # Another way to create the same deque. >>> dq.add_rear(10) >>> dq.add_rear(20) >>> dq.add_rear(30) >>> str(dq) '10 -> 20 -> 30' """ self._rear = None self._size = 0 if iterable is not None: for elem in iterable: # add_rear will update _rear, increment _size self.add_rear(elem)

def __str__(self) -> str: """Return a string representation of this deque, in the format: 'value_1 -> value_2 -> value_3 ... -> value_n'

value_1 is the value at the FRONT of the deque. value_n is the value at the REAR of the deque.

>>> dq = LinkedDeque([10, 20, 30]) >>> str(dq) '10 -> 20 -> 30'

>>> dq = LinkedDeque() >>> str(dq) 'None'

>>> dq.add_rear(10) >>> str(dq) '10' >>> dq.add_rear(20) >>> str(dq) '10 -> 20' >>> dq.add_rear(30) >>> str(dq) '10 -> 20 -> 30' """ if self._rear is None: return 'None'

# Grab the reference to the front node. node = self._rear.next

# Traverse the deque from the front node to the node immediately before # the rear node, collecting the data in the nodes as a list of strings. items = [] while node is not self._rear: items.append(str(node.data)) node = node.next

# Now get the data from the node at the rear of the deque. items.append(str(node.data))

# Concatenate the strings in items, with each pair separated by " -> " return " -> ".join(items)

def __repr__(self) -> str: """Return a string representation of this deque.

>>> dq = LinkedDeque([10, 20, 30]) >>> repr(dq) 'LinkedDeque([10, 20, 30])' >>> dq LinkedDeque([10, 20, 30])

>>> dq = LinkedDeque() # or, dq = LinkedDeque([]) >>> dq LinkedDeque([]) """ raise NotImplementedError("__repr__ hasn't been implemented.")

def __len__(self) -> int: """Return the number of items in this deque.

>>> dq = LinkedDeque([10, 20, 30]) >>> len(dq) 3 """ raise NotImplementedError("__len__ hasn't been implemented.")

def add_rear(self, item: Any) -> None: """Add item at the rear of this deque.

If the deque is used as a queue, add_rear enqueues item at the rear of the queue.

>>> dq = LinkedDeque() >>> dq.add_rear(10) >>> dq.add_rear(20) >>> dq.add_rear(30) >>> str(dq) '10 -> 20 -> 30' # 10 (the first item added) is at the front of the deque, # 30 (the most recent item added) is at the rear. """ raise NotImplementedError("add_rear hasn't been implemented.")

def add_front(self, item: Any) -> None: """Add item to the front of this deque.

If the deque is used as a stack, add_front pushes an item on the top of the stack.

>>> dq = LinkedDeque() >>> dq.add_front(10) >>> dq.add_front(20) >>> dq.add_front(30) >>> str(dq) '30 -> 20 -> 10' # 30 (the most recently-added item) is at the front of the deque, # 10 (the first item added) is at the rear. """ raise NotImplementedError("add_front hasn't been implemented.")

def remove_front(self) -> Any: """Remove and return (dequeue) the item at the front of this deque.

Raise IndexError with the message, "remove_front: empty deque" if the deque is empty.

If the deque is used as a queue, remove_front dequeues an item from the front of the queue. If the deque is used as a stack, remove_front pops an item from the top of the stack.

>>> dq = LinkedDeque([10, 20, 30]) >>> dq.remove_front() 10 >>> dq.remove_front() 20 >>> dq.remove_front() 30 """ raise NotImplementedError("remove_front hasn't been implemented.")

def remove_rear(self) -> Any: """Remove and return the item at the rear of this deque.

Raise IndexError with the message, "remove_rear: empty deque" if the deque is empty.

>>> dq = LinkedDeque([10, 20, 30]) >>> dq.remove_rear() 30 >>> dq.remove_rear() 20 >>> dq.remove_rear() 10 """ raise NotImplementedError("remove_rear hasn't been implemented.")

def peek_front(self) -> Any: """Return (but don't remove) the item at the front of this deque.

Raise IndexError with the message, "peek_front: empty deque" if the deque is empty.

>>> dq = LinkedDeque([10, 20, 30]) >>> dq.peek_front() 10 """ raise NotImplementedError("peek_front hasn't been implemented.")

def peek_rear(self) -> Any: """Return (but don't remove) the item at the rear of this deque.

Raise IndexError with the message, "peek_rear: empty deque" if the deque is empty.

>>> dq = LinkedDeque([10, 20, 30]) >>> dq.peek_rear() 30 """ raise NotImplementedError("peek_rear hasn't been implemented.")

Assignment 1 - Implementing a Deque Using a Circular Linked List This assignment applies many of the key concepts from the first half of term (specification of abstract data types, using classes to implement ADTs, linked lists). Each method you'll write raguires only a small number of lines of code, but it's important to visualize the linked list operations before you start coding; otherwise, it's easy to end up getting lost in a tangled web of nodes and pointers. Background - Circular Linked Lists Recall that each node in a singly linked list contains a link (pointer, reference) to the next node in the list. In the last node (tail node), an end-of-list value is stored in the link. In Python, this value is None, in C, this value is the NULL pointer. One variation of the linked list is known as the circular linked list. The end-of-list value isn't used; instead, the link in the tail node points to the first node in the list (the head node). We also need a variable that stores the link to the tail node. There's no need for a variable that stores a link to the head node, because the tail node points to the head node. We can visualize a circular singly-linked list this way tail 12 99 37 Assuming that the fields in the nodes are named data and next: tail.data is the value stored in the last node (tail node) that is, 12. tail.next is the link to the first node (head node). tail.next.data is the value stored in the first node, that is, 99 Notice that accessing the last node and the first node are constant time operations. Accessing any other node requires us to traverse the nodes, starting with the tail node. If a circular linked list has one node, that node points to itself. tail 12 1 If the circular linked list is empty, tail contains None. ADT Deque - Design A deque (pronounced "deck") is a generalization of a stack and a queue. The word is short for "double-ended queue". At a minimum, a deque provides operations to insert and retrieve items at both ends of the deque. (Some implementations provide operations to search a deque for a specific item, or insert, retrieve or remove items from anywhere in a deque. We won't consider these operations in this assignment) Earlier, we looked at an implementation of ADT Deque that used Python's built-in list type as the underlying data structure. In this lab, you'll implement a deque using a circular, singly-linked list. The tail node will represent the rear of the deque, while the head node will represent the front of the deque The linked list will be encapsulated in a class named LinkedDeque, which will have two instance variables: _rear refers to the node at the rear of the deque; that is, the last node in the linked list size keeps track of the number of items in the deque, that is, the number of nodes in the linked list The add-rear operation adds an item at the rear of the deque Suppose we create a new LinkedDeque object, then add four integers to the rear: da = new LinkedDeque dq.add_rear(99) dq.add_rear(37) dq.add_rear(12) dq.add_rear(42) We can visualize the deque being built, starting with the new, empty LinkedDeque objeet: rear None da _size 0 After 99 is added to the rear of the deque: rear 99 da Size After 37 is added to the rear of the deque: rear 37 99 da _size After 12 is added to the rear of the deque: for 12 99 37 sce . After 42 is added to the rear of the deque 1. the next link in the new node is updated to point to the node at the front of the deque (i.e., the node containing 99); rear 12 99 37 da size new_node 2. the next link in the node at the rear of the deque is updated to point to the new node; rear 12 99 37 da size ho new_node 3. _rear is updated to point to the new node da sure So, add-rear is an O(l) operation The add-front operation adds an item to the front of the deque. This operation always requires two links to be updated (two assignment statements), so it's a (1) operation Here's a picture of a deque after four integers are added to the front a new LinkedDeque dg - new LinkedDeque() dq.add_front(99) dq. add_front (37) dq.add_front (12) dq. add_front (42) rear 99 12 37 da size (Drawing the pictures that depict the deque after the first, second and third values were added to the front of the initially empty deque is left as an exercise for you. What links are updated as a new node is added? What are the two assignment statements that do this?) The remove-front operation removes (and returns) the item at the front of the deque. It's also a 0(1) operation. The remove-rear operation removes and returns) the item at the rear of the deque. This is an O(n) operation Design Exercise draw diagrams that depict the deque after 99, 37, 12 and 42 gre added to the front of an initially empty dequelone diagram for each value). Your last diagram should look like the one immediately above. draw diagrams that depict the deque after the remove-front operation is repeatedly performed on a deque that initially contains 4 values, until the deque is empty. Use the diagram to determine how many link updates are required when the deque is empty and when the deque has at least one item. Make sure you understand why this operation is 0(1). draw diagrams that depict the deque after the remove-rear operation is repeatedly performed on a deque that initially contains 4 values, until the deque is empty. Use the diagram to determine how many link updates are required when the deque is empty and when the deque has at least one item Make sure you understand why this operation is O(n) ADT Deque - Implementation Download linked_deque.py from the Lab Materials section of the main cul.earn course page. Class LinkedDeque uses a circular linked list of Node objects as the underlying data structure This class has a complete implementation of __init_. You can create a new empty deque this Way da = LinkedDeque() and range objects, are three examples of iterables.) The contents of the iterable are added one-by-one to the rear of the LinkedDeque object, so creating a LinkedDeque this way da = LinkedDeque([99, 37, 12, 42]) is equivalent to this code: da = new LinkedDeque() dq.add_rear(99) dq.add_rear (37) dq.add_rear(12) dq.add_rear(42) Note: _init_calls add_rear, which you have to write, so you won't be able to create a deque from an iterable until that task is finished. The class also has a complete implementation of _str_. Here's an example of the strings produced by this method: >>> dq = new LinkedDeque() >>> dq.add_rear(99) >>> dg.add_rear (37) >>> dq.add_rear(12) >>> dq.add_rear(42) >>> str(da) 99 -> 37 -> 12 - ) 42' Important: the leftmost item in the string is the value at the front of the deque, and the rightmost item in the string is the value at the rear of the deque. You'll have to remember that instance variable_rear refers to the node containing the rightmost item. Also, the link from the rear node to the front node isn't shown in the string representation, "Stub" implementations have been provided for methods _repr len_add_rear add_front, remove_front, remove_rear peek_front and peek_rear If you call any of these methods on a LinkedDeque object. Python will throw a Not ImplementedError exception For each method, read the docstring and replace the raise statement with a correct implementation of the method. If you've prepared a complete set or design diagrams for the add 10 7 / 9 90% I suggest you implement the methods in this order. add_rear. This method should be 0(1). After testing add_rear, verify that you can create a deque by passing __init__ an iterable. . _len__ This method should be O(1). repr_. Notice that_repr__ will return an expression that would create an instance of LinkedDeque that is identical to the object on which_repr_ is called. Hint: feel free to "borrow" the code from __str_, but note that there will be some important differences between the two methods. remove_front. This method should be O(1). At this point, you should be able to use a deque as a FIFO queue (add_rear enqueues an item, remove_front dequeues an item). Test this. peek_front and peek_rear. These methods should be dis add_front. This method should be (1). At this point, you should be able to use a deque as a LIFO stack (add_front pushes an item, remove_front pops an item). Test this. remove_rear. This method should be on). Refer to your design diagrams, and make sure you understand why it can't be 0(1). Programming Style - Code Formatting Before submitting your code, please run it through Wing 101's source reformatter, as described in following paragraphs Wing 101 can easily be reconfigured to reformat your code so that it adheres to some of the formatting conventions described in the official Python coding conventions document, PEP 8. Style Guide for Python Code. To configure reformatting, follow the instructions in Section 3.2 of Installing Python 3.9.1 and Wing 101 7.2.7, which is posted on cul cam. (The instructions apply to both the Windows 10 and macOS versions or Wing 101.) If you prefer, you manually reformat your files even if you've disabled outomatic reformatting This is described in Section 33 Note that you still have to open the Auto-formatting window to configure which PEP & conventions are followed as described in Section 32