Lab 10: Linked Lists
Due at 11:59:59 pm on 11/17/2020.

Starter Files

Download lab10.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. See this article for more instructions on okpy and submitting assignments.

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 lab10.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.

>>> from lab10 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 lab10.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:

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.

    >>> 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 reverse

Question 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 IndexError with:

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 IndexError

Use OK to test your code:

python3 ok -q insert

Submit

Make sure to submit this assignment by running:

python3 ok --submit