Lab 9: Linked Lists and Exceptions
Due at 11:59:59 pm on 4/12/2022.
Starter Files
Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.
Linked Lists
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 = Link(1, Link(2, Link(3)))
>>> s
Link(1, Link(2, Link(3)))
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest is not Link.empty:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(repr(self.first), 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):
if link is Link.empty:
print('This linked list is empty!')
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 -uIf 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 *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______1
>>> link.rest.first
______2
>>> link.rest.rest.rest is Link.empty
______True
>>> link.first = 9001
>>> link.first
______9001
>>> link.rest = link.rest.rest
>>> link.rest.first
______3
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first
______1
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______1
>>> link2.rest.first
______2
>>> print_link(link2) # Look at print_link in lab09.py
______<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.
>>> link = list_to_link([1, 2, 3])
>>> print_link(link)
<1 2 3>
>>> print_link(list_to_link([4]))
<4>
"""
"*** YOUR CODE HERE ***"
if not lst:
return Link.empty
else:
return Link(lst[0], list_to_link(lst[1:]))Use OK to test your code:
python3 ok -q list_to_linkQuestion 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.
>>> print_link(reverse(Link(1)))
<1>
>>> link = Link(1, Link(2, Link(3)))
>>> new = reverse(link)
>>> print_link(new)
<3 2 1>
>>> print_link(link)
<1 2 3>
"""
"*** YOUR CODE HERE ***"
#new = Link(link.first)
#while link.rest is not Link.empty:
# link = link.rest
# new = Link(link.first, new)
#return new
new = Link.empty
while link is not Link.empty:
new = Link(link.first, new)
link = link.rest
return new
# Recursive solution
def reverse(link):
def reverse_to(link, t):
if link is Link.empty:
return t
else:
return reverse_to(link.rest, Link(link.first, t))
return reverse_to(link, Link.empty)Use OK to test your code:
python3 ok -q reverseExceptions
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'
"""
"*** YOUR CODE HERE ***"
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_keyerrorSubmit
Make sure to submit this assignment by running:
python3 ok --submit