Mod 4 Homeork Enhanced DoublyLinkedList

Starter Code:

# Do not modify this class class Node: 'Node object to be used in DoublyLinkedList' def __init__(self, item, _next=None, _prev=None): 'initializes new node objects' self.item = item self._next = _next self._prev = _prev

def __repr__(self): 'String representation of Node' return f"Node({self.item})"

class DoublyLinkedList: def __init__(self, items=None): 'Construct a new DLL object' self._head = None self._tail = None self._len = 0 self._nodes = dict() # dictionary of item:node pairs

# initialize list w/ items if specified if items is not None: for item in items: self.add_last(item)

def __len__(self): 'returns number of nodes in DLL' return self._len

# TODO: Modify the 4 methods below to keep `self._nodes` up-to-date def add_first(self, item): 'adds item to front of dll' # add new node as head self._head = Node(item, _next=self._head, _prev=None) self._len += 1 # if that was the first node if len(self) == 1: self._tail = self._head

# otherwise, redirect old heads ._tail pointer else: self._head._next._prev = self._head

def add_last(self, item): 'adds item to end of dll' # add new node as head self._tail = Node(item, _next=None, _prev=self._tail) self._len += 1 # if that was the first node if len(self) == 1: self._head = self._tail

# otherwise, redirect old heads ._tail pointer else: self._tail._prev._next = self._tail

def remove_first(self): 'removes and returns first item' if len(self) == 0: raise RuntimeError("cannot remove from empty dll")

# extract item for later item = self._head.item

# move up head pointer self._head = self._head._next self._len -= 1

# was that the last node? if len(self) == 0: self._tail = None

else: self._head._prev = None

return item def remove_last(self): 'removes and returns last item' if len(self) == 0: raise RuntimeError("cannot remove from empty dll")

# extract item for later item = self._tail.item

# move up tail pointer self._tail = self._tail._prev self._len -= 1

# was that the last node? if len(self) == 0: self._head = None

else: self._tail._next = None

return item # TODO: Add a docstring and implement def __contains__(self, item): raise NotImplementedError

# TODO: Add a docstring and implement def neighbors(self, item): raise NotImplementedError

# TODO: Add a docstring and implement def remove_node(self, item): raise NotImplementedError

Mod 4 Homework - Enhanced DoublyLinkedList Doubly Linked Lists (DLLs) support O(1) addition and removal from either end, making them a great choice for queues or deques. A downside of DLLs (and other linked data structures) is that it takes linear time (O(n)) to access nodes in the middle - in a traditional DLL, we have to start at the beginning and continually call node._next until we get to the node we're looking for. Here, we'll enhance a DLL with a dictionary of item:node pairs to give us O(1) access to interior nodes. This will speed up membership testing, node insertion at arbitrary locations, and removal of arbitrary nodes to O(1). This is a common design pattern we'll see with other linked data structures like heaps and graphs. Some downsides of this approach to keep in mind: - Dictionary keys must be unique, so this will only work if node items are unique. - Storing and maintaining the dictionary will not asymptotically worsen our O(1) running times or O(n) memory usage, but it will negatively impact both. Figure 1: (a) In a standard DLL, we can only access the head and tail nodes in O(1). (b) By using a dictionary of item:node pairs, we can immediately jump to any node, as long as we know which item we are interested in. 1) Add a dictionary DoublyLinkedList.py provides basic Node and DoublyLinkedList classes that supports typical DLL operations. Modify these methods to keep the nodes dictionary up to date with item:node pairs as you add and remove from the DLL so you can access any node in O(1). 2) Implement ___ contains__(item) _nodes is a private attribute, and thus should not be called explicilty in your tests. Instead, use _nodes to >dll= DoublyLinkedList (range (5)) 3 in dll \# O(1), even though 3 is in the middle True 5 in dll \# Note the use of 'in' to call the dunder method __contains__() False Write a unittest that verifies contains works as expected as you add and remove nodes. 3) Implement neighbors (item) Add a method neighbors (item) to your DoublyLinkedList class that returns the items immediately before and after the node with item: dll= DoublyLinkedList(range (5)) dll.neighbors(3) (2,4) dll.neighbors(0) \# Edge case - head (None, 1) dll.neighbors(4) \# Edge case - tail (3, None) Add a method neighbors (item) to your DoublyLinkedList class that returns the items immediately before and after the node with item: >dl1= DoublyLinkedList(range (5)) >dll.neighbors(3) (2,4) >dll.neighbors(0) \# Edge case - head (None, 1) dll.neighbors(4) \# Edge case - tail (3, None) - Should be O(1) - When called on the item stored in the head/tail, return None as the previousext item, as shown above - Raise a RuntimeError if someone searches for an item not in the DLL Include unittests for the above behavior (except the running time). 4) Implement remove_node (item) Add a method that removes the node containing an item from your DLL. - O(1) - Make sure to "stitch together" the adjacent nodes - Edge cases you should be able to handle: - Raise a RuntimeError if someone tries to remove an item not in the DLL - Removing the head - Removing the tail Include unittests for the above behavior (except the running time)