Part $1-$ Recursion on a Linked List

Linked lists can be thought of as recursive structures. Every linked list is either:

the empty list, or

a node that links to a linked list

This makes them a great playground for implementing various types of recursive functions. We provide starter code that demonstrates a few methods of recursion in a LinkedList, and you will implement a few more.

Starter Code

The LinkedList class is already fully implemented. It is essentially a wrapper $-$ the LLNode class does all the interesting recursion.

In LLNode, we have implemented:

$\_--$

$-()$

$-()$

get$\_$tail$()$

$-(),-(),$ and get$\_$tail$()$ show various examples of recursive LLNode functions. Study them to understand how they work, then implement the following LLNode methods. Note that we have listed the parameters you should use $-$ this is a great hint into how you can efficiently structure your code. Do not change these.

add$\_$last $($self$,$ item$)$

recursively call on linked node until you hit the tail, at which point you should add a new node

we are not keeping track of a tail node, so this has $O(n)$ running time

sum$\_$al$1($self$)$

recursively add all items in linked list and return the sum

$-O(n)$

contains$($self$,$ item$)$

recursively call on linked node until you either:

find the item and return True, or

hit the end of the list without finding the item and return False

$-O(n)$ running time

remove$\_$all $($self$,$ item$)$

recursively removes all nodes holding item in linked list

$-O(n)$ running time

reverse$($self$)$

recursively reverses the linked list contained in self. link unless it is the tail node

after reversing the linked list in self.link, puts itself at the end of the reversed list

this method should return the new head of the list $($i$.$e$.,$ the old tail$)$

$-O(n)$ running time