Write 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.

You may use default arguments and/or helper functions.

Your recursive functions must NOT:

• 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 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)

LESSON:

class Node:

\"\"\"

Represents a node in a linked list

\"\"\"

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

\"\"\"

A linked list implementation of the List ADT

\"\"\"

def __init__(self):

self._head = None

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 display(self):

\"\"\"

Prints out the values in the linked list

\"\"\"

current = self._head

while current is not None:

print(current.data, end=\" \")

current = current.next

print()

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

def is_empty(self):

\"\"\"

Returns True if the linked list is empty,

returns False otherwise

\"\"\"

return self._head is None