Lab 7: Linked Lists
Due at 11:59pm on 11/13/2016.
Starter Files
Download lab07.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 using ok. 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-6 in lab07.py and submit through OK.
- Question 1 is for practice, you don't need to submit anything for it.
- Questions 7 is a challenge problem. If you choose to complete it, you can skip another required question (Questions 2-6) on the lab and still get full credit.
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)))
>>> len(s)
3
>>> s[2]
3
>>> s = Link.empty
>>> len(s)
0
"""
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. 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.
Motivation
Since you are already familiar with Python's built-in lists, you might be wondering why we are teaching you another list representation. There are historical reasons, along with practical reasons. Later in the term, you'll be programming in Scheme, which is a programming language that uses linked lists for almost everything. But let's not worry about that for now. The real reason, is that certain operations are faster with linked lists.
Python's built-in list is like a sequence of containers with indices on them:
Linked lists are a list of items pointing to their neighbors. Notice that there's no explicit index for each item.
Suppose we want to add an item at the head of the list.
- With Python's built-in list, if you want to put an item into the container labeled with index 0, you must move all the items in the list into its neighbor containers to make room for the first item;
- With a linked list, you tell Python that the neighbor of the new item is the old beginning of the list.
To test this, in your terminal, enter the following command: python3 timing.py
insert 100000, which inserts 100,000 items into the beginning of both a linked
list and a Python built-in list to compare the speed.
Now, say we want the item at index 3.
- In the built-in list, you can simply grab the item from the container with 3 labeled on it;
- In the linked list, you need to start at the first item, and go to its neighbor's neighbor's neighbor to finally reach the item at index 3.
To test this, enter the following command in your terminal: python3 timing.py
index 10000. This program compares the speed of randomly accessing 10,000 items from both a linked list and a
built-in Python list (each with length 10,000).
You'll learn more about orders of growth this week, which will provide mathematical rigor when comparing the runtime of the same operations with different data structures.
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 lab07.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.
>>> from lab07 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 lab07.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>
"""
"*** 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:
python ok -q list_to_link --localQuestion 3: 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:
python ok -q link_to_list --localQuestion 4: 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, you can raise an
IndexErrorwith:raise IndexError
def insert(link, value, index):
"""Insert a value into a Link at the given index.
>>> link = Link(1, Link(2, Link(3)))
>>> print_link(link)
<1 2 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:
python ok -q insert --localQuestion 5: 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:
python ok -q reverse --localQuestion 6: 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 built-in 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:
python ok -q deep_map --localChallenge Question
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
3Implement 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
Linkobjects 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 FalseUse OK to test your code:
python ok -q has_cycle --localExtra 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 FalseUse OK to test your code:
python ok -q has_cycle_constant --local