Lab 8 Solutions
Midsemester Survey
We have posted an optional survey that you can complete to give us feedback and help us make the course even better! Completing this survey will yield 1 Extra Credit Point that will be added at the end of the semester.
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 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 *
>>> 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: Link to List
Write a function link_to_list
that converts a given Link
to a
Python list.
def link_to_list(link):
"""Takes a Link and returns a Python list with the same elements.
>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> link_to_list(link)
[1, 2, 3, 4]
>>> link_to_list(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"
# Recursive solution
if link is Link.empty:
return []
return [link.first] + link_to_list(link.rest)
# Iterative solution
def link_to_list(link):
result = []
while link is not Link.empty:
result.append(link.first)
link = link.rest
return result
Use OK to test your code:
python3 ok q link_to_list
Question 3: Deep Map
Implement deep_map
, which takes a function f
and a link
. It returns a
new linked list with the same structure as link
, but with f
applied to any
element within link
or any Link
instance contained in link
.
The deep_map
function should recursively apply fn
to each of that
Link
's elements rather than to that Link
itself.
Hint: You may find the builtin isinstance
function useful.
def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.
>>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
>>> print_link(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
>>> print_link(s) # unchanged
<1 <2 3> 4>
>>> print_link(deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5))))))
<<2 <4 6> 8> <<10>>>
"""
"*** YOUR CODE HERE ***"
if link is Link.empty:
return link
if isinstance(link.first, Link):
first = deep_map(f, link.first)
else:
first = f(link.first)
return Link(first, deep_map(f, link.rest))
Use OK to test your code:
python3 ok q deep_map
Question 4: Add Links
Let's implement a method in order to add together items of link1
and link2
.
Do not assume that the links are the same length.
def add_links(link1, link2):
"""Adds two Links, returning a new Link
>>> l1 = Link(1, Link(2))
>>> l2 = Link(3, Link(4, Link(5)))
>>> new = add_links(l1,l2)
>>> print_link(new)
<1 2 3 4 5>
"""
"*** YOUR CODE HERE ***"
if link1 is not Link.empty:
return Link(link1.first, add_links(link1.rest, link2))
elif link2 is not Link.empty:
return Link(link2.first, add_links(link1, link2.rest))
else:
return Link.empty
# Iterative version (using reverse)
def add_links(link1, link2):
result = Link.empty
while link1 is not Link.empty:
result = Link(link1.first, result)
link1 = link1.rest
while link2 is not Link.empty:
result = Link(link2.first, result)
link2 = link2.rest
return reverse(result)
Use OK to test your code:
python3 ok q add_links
Question 5: Every Other
Implement every_other
, which takes a linked list s
. It mutates s
such
that all of the oddindexed elements (using 0based indexing) are removed from
the list. For example:
>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True
If s
contains fewer than two elements, s
remains unchanged.
Do not return anything!
every_other
should mutate the original list.
def every_other(s):
"""Mutates a linked list so that all the oddindiced elements are removed
(using 0based indexing).
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s)
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length)
>>> odd_length
Link(5, Link(1))
>>> singleton = Link(4)
>>> every_other(singleton)
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"
if s is Link.empty or s.rest is Link.empty:
return
else:
s.rest = s.rest.rest
every_other(s.rest)
Use OK to test your code:
python3 ok q every_other
Extra Questions
The following questions are for extra practice — they can be found in the the lab08_extra.py file. It is recommended that you complete these problems on your own time.
Question 6: Find Intersection
Implement intersection
, which takes two linked lists, xs
and ys
, and finds
the Link
at which the two linked list begin to intersect (or overlap).
Remember that all Link
s end with Link.empty
, so there will always be some
overlap.
For the two linked lists below, z1
should be the start of the linked list that
you return. Note that you should be comparing with identity, rather than
equality; an intersection means that some part of the Link
is shared between
xs
and ys
, not just that they have the same elements.
Try to aim for θ(n)
runtime (where n
is the sum of the lengths of xs
and
ys
), and even θ(1)
additional space.
xs: x1 > x2 > z1 > z2 > z3 > ...
^

ys: y1 +
def intersection(xs, ys):
"""
>>> a = Link(1)
>>> intersection(a, Link.empty) is Link.empty
True
>>> b = a
>>> intersection(a, b).first # intersection begins at a
1
>>> looks_like_a = Link(1)
>>> intersection(a, looks_like_a) is Link.empty # no intersection! (identity vs value)
True
>>> b = Link(1, Link(2, Link(3, a)))
>>> a.first = 5
>>> intersection(a, b).first # intersection begins at a
5
>>> c = Link(3, b)
>>> intersection(b, c).first # intersection begins at b
1
>>> intersection(c, b).first # intersection begins at b
1
>>> intersection(a, c).first # intersection begins at a
5
"""
"*** YOUR CODE HERE ***"
if xs is Link.empty or ys is Link.empty:
return Link.empty
# make xs and ys the same size
if len(xs) < len(ys):
return intersection(xs, ys.rest)
elif len(xs) > len(ys):
return intersection(xs.rest, ys)
# comparison
while xs is not ys:
xs, ys = xs.rest, ys.rest
return xs
Use OK to test your code:
python3 ok q intersection
Question 7: Cycles
The Link
class can represent lists with cycles. That is, a list may
contain itself as a sublist.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3
Implement has_cycle
that returns whether its argument, a Link
instance, contains a cycle.
Hint: Iterate through the linked list and try keeping track of which
Link
objects you've already seen.
def has_cycle(link):
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
"""
"*** YOUR CODE HERE ***"
lists = set()
while link is not Link.empty:
if link in lists:
return True
lists.add(link)
link = link.rest
return False
Use OK to test your code:
python3 ok q has_cycle
Extra for experts: Implement has_cycle
with only constant space. (If
you followed the hint above, you will use linear space.) The solution is short
(less than 20 lines of code), but requires a clever idea. Try to discover the
solution yourself before asking around:
def has_cycle_constant(link):
"""Return whether link contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle_constant(t)
False
"""
"*** YOUR CODE HERE ***"
if link is Link.empty:
return False
slow, fast = link, link.rest
while fast is not Link.empty:
if fast.rest == Link.empty:
return False
elif fast == slow or fast.rest == slow:
return True
else:
slow, fast = slow.rest, fast.rest.rest
return False
Use OK to test your code:
python3 ok q has_cycle_constant
Submit
Make sure to submit this assignment by running:
python3 ok submit
Extra Credit Practice Open in a new window
These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.
Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88lab01 for some problems designed to demonstrate how to solve these types of problems.
These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.
Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 45 points throughout the semester.
Use OK to test your code:
python3 ok q extra_credit