A linked list is either an empty linked list (`Link.empty`) or a first value and the rest of the linked list.

``````class Link:
"""
>>> s
"""
empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest

def __repr__(self):
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''

To check if a `Link` is empty, compare it against the class attribute `Link.empty`. For example, the below function prints out whether or not the link it is handed is empty:

``````def test_empty(link):
else:
print('This linked list is not empty!')``````

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (`first`) and a reference to another linked list (`rest`) which contains the rest of the values in the list.

### Question 1: WWPP: Linked Lists

Use OK to test your knowledge with the following "What Would Python Print?" questions:

``python3 ok -q link -u``

If you get stuck, try loading lab09.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.

``````>>> from lab09 import *
______1
______2
______True
______9001
______3
______1
______1
______2
______<1 2 3 4>``````

### Question 2: List to Link

Write a function `list_to_link` that converts a Python list to a `Link`.

``````def list_to_link(lst):
"""Takes a Python list and returns a Link with the same elements.

<1 2 3>
<4>
"""
if not lst:
else:

Use OK to test your code:

``python3 ok -q list_to_link``

### Question 3: Reverse

Implement `reverse`, which takes a linked list `link` and returns a linked list containing the elements of `link` in reverse order. The original `link` should be unchanged.

``````def reverse(link):
"""Returns a Link that is the reverse of the original.

<1>
<3 2 1>
<1 2 3>
"""
#return new

return new

# Recursive solution
return t
else:

Use OK to test your code:

``python3 ok -q reverse``

## Exceptions

Exceptions allow us to try a chunk of code, and then catch any errors that might come up. If we do catch an exception, we can run an alternative set of instructions. This construct is very useful in many situations.

``````try:
<try suite>
except Exception as e:
<except suite>
else:
<else suite>
finally:
<finally suite>``````

Notice that we can catch the exception as `e`. This binds the name `e` to the exception object. This can be helpful when we want to give extra information on what happened. For example, we can `print(e)` inside the except clause.

Also, we have an optional else case. The else suite is executed if the `try` suite finishes without any exceptions.

We also have an optional finally clause, which is always executed, whether or not an exception is thrown. We generally don't need to use the else and finally controls in this class.

When we write exception statements, we generally don't just use the class Exception as above. Rather, we figure out the specific type of exception that we want to handle, such as `TypeError` or `ZeroDivisionError`. To figure out which type of exception you are trying to handle, you can type purposely wrong things into the interpreter (such as 'hi' + 5 or 1 / 0) and see what kind of exception Python spits out.

### Question 4: No KeyErrors Allowed

If we try to look up a key that does not exist in a dictionary, then Python will raise a `KeyError`. Write the function `avoid_keyerror` which returns the value mapped to `key` in the `dictionary`. If `key` does not exist, print 'Avoid Exception' and map `key` to the string 'no value'.

``````def avoid_keyerror(dictionary, key):
""" Returns the value associated with key in dictionary. If key
does not exist in the dictionary, print out 'Avoid Exception' and
map it to the string 'no value'.

>>> d = {1: 'one', 3: 'three', 5: 'five'}
>>> avoid_keyerror(d, 3)
'three'
>>> avoid_keyerror(d, 4)
Avoid Exception
>>> d[4]
'no value'
"""

try:
return dictionary[key]
except KeyError as e:
print("Avoid Exception")
dictionary[key] = 'no value'``````

Use OK to test your code:

``python3 ok -q avoid_keyerror``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``