Lab 9: Mutable Linked Lists
Due at 11:59pm on 07/21/2015.
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.
- To receive credit for this lab, you must complete Questions 2, 3, 4, and 5 in lab09.py and submit through OK. You must also unlock Question 1 (What would Python print?) using OK.
- Questions 6, 7, and 8 are extra practice. They can be found in the lab09_extra.py file. It is recommended that you complete these problems on your own time.
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:
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = restTo check if a Link is empty, compare it against the class attribute
Link.empty:
if link is Link.empty:
print('This linked list is empty!')Question 1: What would Python print?
Use OK to answer this "What would Python print?" question:
python3 ok -q wwpp -uIf you get stuck, try typing the lines into an interactive Python session.
>>> 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
______1Question 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 resultUse OK to test your code:
python3 ok -q link_to_listQuestion 3: 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>
"""
"*** 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_linkMutable Linked Lists
| Mutable Linked Lists | Regular Linked Lists | |
|---|---|---|
| Traits | - Represented with custom object, Link - Has methods and attributes - Mutable |
- Represented with abstract data type - Has selector functions - Not mutable |
| Examples |
|
|
| Explanations |
Link is mutable because we have created an object Link with attributes that allow direct access to the elements inside of it. This allows us to change the elements, thus mutating the Link
|
link is not mutable because its selector functions only return to us the values of its elements. We are not able to change or reassign these values.
|
Question 4: Mutable Mapping
Implement deep_map_mut(fn, link), which applies a function fn onto all elements in the given linked list link. If an element is itself a linked list, apply fn to each of its elements, and so on.
Your implementation should mutate the original linked list. Do not create any new linked lists.
Hint: The built-in
isinstancefunction may be useful.>>> s = Link(1, Link(2, Link(3, Link(4)))) >>> isinstance(s, Link) True >>> isinstance(s, int) False
def deep_map_mut(fn, link):
"""Mutates a deep link by replacing each item found with the
result of calling fn on the item. Does NOT create new Links (so
no use of Link's constructor)
Does not return the modified Link object.
>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> deep_map_mut(lambda x: x * x, link1)
>>> print_link(link1)
<9 <16> 25 36>
"""
"*** YOUR CODE HERE ***"
if link is Link.empty:
return
elif isinstance(link.first, Link):
deep_map_mut(fn, link.first)
else:
link.first = fn(link.first)
deep_map_mut(fn, link.rest)Use OK to test your code:
python3 ok -q deep_map_mutQuestion 5: Insert
Implement a function insert that takes a Link, a value, and an index, and
inserts the value into the Link at the given index. You can assume the linked
list already has at least one element. Do not return anything — insert should
mutate the linked list.
Note: If the index is out of bounds, raise an
IndexError
def insert(link, value, index):
"""Insert a value into a Link at the given index.
>>> link = Link(1, Link(2, Link(3)))
>>> insert(link, 9001, 0)
>>> print_link(link)
<9001 1 2 3>
>>> insert(link, 100, 2)
>>> print_link(link)
<9001 1 100 2 3>
>>> insert(link, 4, 5)
IndexError
"""
"*** YOUR CODE HERE ***"
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
elif link.rest is Link.empty:
raise IndexError
else:
insert(link.rest, value, index - 1)
# iterative solution
def insert(link, value, index):
while index > 0 and link.rest is not Link.empty:
link = link.rest
index -= 1
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
else:
raise IndexErrorUse OK to test your code:
python3 ok -q insertExtra Questions
The following questions are for extra practice — they can be found in the the lab09_extra.py file. It is recommended that you complete these problems on your own time.
Question 6: 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
# 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 reverseQuestion 7: 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_linksQuestion 8: Slice
Implement a function slice_link that slices a given link. slice_link
should slice the link starting at start and ending one element before
end, as with a normal Python list.
def slice_link(link, start, end):
"""Slices a Link from start to end (as with a normal Python list).
>>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
>>> new = slice_link(link, 1, 4)
>>> print_link(new)
<1 4 1>
"""
"*** YOUR CODE HERE ***"
if end == 0:
return Link.empty
elif start == 0:
return Link(link.first, slice_link(link.rest, 0, end-1))
else:
return slice_link(link.rest, start-1, end-1)Use OK to test your code:
python3 ok -q slice_link