class LinkedList: """A linked list implementation of the List ADT. """ # === Private Attributes === # _first: # The first node in the linked list, or None if the list is empty. # _size: # The number of items in this linked list. _first: Optional[_Node] _size: int def __init__(self, items: list) -> None: """Initialize a new linked list containing the given items. The first node in the linked list contains the first item in . """ if items == []: self._first = None else: self._first = _Node(items[0]) curr = self._first for item in items[1:]: curr.next = _Node(item) curr = curr.next def __str__(self) -> str: """Return a string representation of this list in the form '[item1 -> item2 -> ... -> item-n]'. >>> str(LinkedList([1, 2, 3])) '[1 -> 2 -> 3]' >>> str(LinkedList([])) '[]' """ items = [] curr = self._first while curr is not None: items.append(str(curr.item)) curr = curr.next return '[' + ' -> '.join(items) + ']' def insert_after(self, marker: Any, item: Any) -> None: """Insert  after the first time  occurs in this linked list. Precondition:  is in this linked list. >>> lst = LinkedList([1, 3, 2, 6]) >>> lst.insert_after(3, 4) >>> # TODO: (Task 1) Fill in the 'expected' LinkedList below. >>> # This should be in the format returned by __str__ >>> # e.g. '[1 -> 2 -> 3]' >>> expected = '[]' >>>  >>> # TODO: (Task 2) Fill in the 'actual' LinkedList below. >>> # This should be the result of calling insert_after BEFORE >>> # you fixed the bug. >>> actual = '[]' >>> >>> # If you've done Task 1 and Task 3 correctly, the below should work: >>> str(lst) == expected True """  # TODO: (Task 3) Fix the bug in insert_after. # Do NOT use any other LinkedList methods # i.e. use only what we have provided in quiz5.py curr = self._first while curr.item != marker: curr = curr.next insert = _Node(item) curr.next = insert ################################################################################ # Below is the implementation of _Node # Do NOT modify the below in any way. You have no tasks related to _Node. ################################################################################ class _Node: """A node in a linked list. Note that this is considered a "private class", one which is only meant to be used in this module by the LinkedList class, but not by client code. === Attributes === item: The data stored in this node. next: The next node in the list, or None if there are no more nodes. """ item: Any next: Optional[_Node] def __init__(self, item: Any) -> None: """Initialize a new node storing , with no next node. """ self.item = item self.next = None # Initially pointing to nothing if __name__ == '__main__': import doctest doctest.testmod()