Python:

A LinkedList class that hasrecursiveimplementations of theaddandremovemethods described in the lesson. It should also haverecursiveimplementations of thecontains,insert, andreversemethods described in the exercises. The reverse method shouldnotchange thedatavalue each node holds - it must rearrange the order of the nodes (by changing thenextvalue each node holds).

It should have arecursivemethod namedto_regular_listthat takes no parameters and returns a regular Python list that has the same values (from the data attribute of the Nodes), in the same order, as the linked list.

It should have a method namedget_headthat takes no parameters and returns the value of _head.

Theheaddata member of the LinkedList class must be private.

• may use default arguments and/or helper functions.
• Include docstrings

The recursive functions mustnot:

• use any loops
• use any variables declared outside of the function
• use any mutable default arguments

Here's an example of how a recursive version of the display() method as well as the other methods from the lesson could be written:

 def rec_display(self, a_node): """recursive display method""" if a_node is None: return print(a_node.data, end=" ") self.rec_display(a_node.next) def display(self): """recursive display helper method""" self.rec_display(self._head) ----------------------------------------------------------------------------- def contains(self, key): """ Returns True if the list contains a Node with the value key, otherwise returns False """ if self._head is None: # If the list is empty return False current = self._head while current is not None: if current.data == key: return True current = current.next return False -------------------------------------------------------------- def insert(self, val, pos): """ Inserts a node containing val into the linked list at position pos """ if self._head is None: # If the list is empty self.add(val) return if pos == 0: temp = self._head self._head = Node(val) self._head.next = temp else: current = self._head counter = 0 for _ in range(pos-1): if current.next is None: current.next = Node(val) return current = current.next temp = current.next current.next = Node(val) current.next.next = temp ---------------------------------------------------------------------------- def reverse(self): """" Reverses the linked list """ previous = None current = self._head while current is not None: following = current.next current.next = previous previous = current current = following self._head = previous ---------------------------------------------------- def add(self, val): """ Adds a node containing val to the linked list """ if self._head is None: # If the list is empty self._head = Node(val) else: current = self._head while current.next is not None: current = current.next current.next = Node(val) ------------------------------------------------------ def remove(self, val): """ Removes the node containing val from the linked list """ if self._head is None: # If the list is empty return if self._head.data == val: # If the node to remove is the head self._head = self._head.next else: current = self._head while current is not None and current.data != val: previous = current current = current.next if current is not None: # If we found the value in the list previous.next = current.next