Starter Code The following methods are implemented for you. Everything but str should look familiar. str is provided to give you an example of a recursive function applied to a LinkedList. init len add first remove_first str O(n^2) returns a string representation of the LL: >>> LL = LinkedList() >>> for i in range (4): LL.add_first(i) >>> str (LL) 3-2-1-0 this is slow! You will probably fail your test cases if you try to use str() to implement any functionality below. Deliverables Use recursion to add the attributes described below. Magic Methods in O(n) returns a boolean describing whether an item is in the LinkedList: >>> LL = LinkedList() >>> for i in range (4): LL.add_first(i) >>> 3 in LL True >>> 4 in LL False Non-Magic Methods add last O(n) adds item to end of LinkedList >>> LL = LinkedList() >>> for i in range (4): LL.add_last(i) >>> str (LL) 0-1-2-3 Submitting At a minimum, submit the following files: Linkedlist.py Students must submit to Mimir individually by the due date (typically, Sunday

Here is the example code. Just need to implement in and add_last for its functionality by using recursion.

11:59 pm EST) to receive credit. Grading 50 - in 25 - uses recursion 25 - functionality 50 - add_last 25 - uses recursion 25 - functionality 1 class Node: 2 def __init__(self, _item, _next=None): 3 self._item = _item 4 self._next = _next 5 6\" class LinkedList: 7 def __init__(self): 8 self._head = None 9 self._len = 0 10 11 def add_first(self, item): 12 13 self._head = Node (item) if (len(self) == 0) else Node (item, self._head) 14 15 self._len += 1 16 17 def remove_first(self): 18 if len(self) == 0: raise RuntimeError(\"attempt to remove_first from empty LL\") 19 20 item = self._head. _item 21 self._head = self._head._next 22 self._len -= 1 23 return item 24 25 def add_last(self, item): 26 27 self._head 28 self._len += 1 29 return item 30 31- def -_len__(self): 32 return self._len 33 def __str__(self): 35 if len(self) == 0: return !! 36 37 list_of_strings = [] 38 self._str(self._head, list_of_strings) 39 return \".join(list_of_strings) 40 41 def _str(self, node, list_of_strings) : 42 if node. _next is None: 43 list_of_strings.append(str(node. _item)) 44 return 45 - else: 46 self._str(node. _next, list_of_strings) 47 list_of_strings.insert(0, str(node._item) + \"-\") 48 49'if __name__ '__main__': 50 n = Node(1) 51 assert n._item == 1 52 assert n. _next is None 53 print(\"Node tests pass\") 54 55 LL = LinkedList() 56 57 for i in range(4): 58 assert len(LL) == i 59 LL.add_first(i) 60 61 for i in range (4): 62 assert LL.remove_first() == 3-1 63 assert len(LL) == 3-1 64 65 for i in range(4): LL.add_first(i) 66 assert str(LL) == \"3-2-1-0\" 67 printl\"starter