Lab 8 Solutions

Solution Files

Required Questions

Linked Lists

Consult the drop-down if you need a refresher on Linked Lists. It's okay to skip directly to the questions and refer back here should you get stuck.

A linked list is a data structure for storing a sequence of values. It is more efficient than a regular built-in list for certain operations, such as inserting a value in the middle of a long list. Linked lists are not built in, and so we define a class called Link to represent them. A linked list is either a Link instance or Link.empty (which represents an empty linked list).

A instance of Link has two instance attributes, first and rest.

The rest attribute of a Link instance should always be a linked list: either another Link instance or Link.empty. It SHOULD NEVER be None.

To check if a linked list is empty, compare it to Link.empty. Since there is only ever one empty list, we can use is to compare, but == would work too.

def is_empty(s):
    """Return whether linked list s is empty."""
    return s is Link.empty:

You can mutate a Link object s in two ways:

  • Change the first element with s.first = ...
  • Change the rest of the elements with s.rest = ...

You can make a new Link object by calling Link:

  • Link(4) makes a linked list of length 1 containing 4.
  • Link(4, s) makes a linked list that starts with 4 followed by the elements of linked list s.

Q1: Sum Nums

Write a function sum_nums that receives a linked list s and returns the sum of its elements. You may assume the elements of s are all integers. Try to implement sum_nums with recursion!

def sum_nums(s):
    """
    Returns the sum of the elements in s.

    >>> a = Link(1, Link(6, Link(7)))
    >>> sum_nums(a)
    14
    """

    if s == Link.empty:
        return 0
    return s.first + sum_nums(s.rest)

Use Ok to test your code:

python3 ok -q sum_nums

Write a function list_to_link that takes in a Python list and returns the linked list version of the sequence.

Try to find both an iterative and recursive solution for this problem!

def list_to_link(lst):
    """Takes a Python list and returns a linked list with the same elements.

    >>> link = list_to_link([1, 2, 3])
    >>> print(link)
    (1 2 3)
    """

    # Recursive solution
    if not lst:
        return Link.empty
    else:
        return Link(lst[0], list_to_link(lst[1:]))

# Iterative solution
def list_to_link(lst):
    result = Link.empty
    for i in range(1, len(lst) + 1):
        result = Link(lst[-i], result)
    return result
Video Walkthrough:

YouTube link

Use Ok to test your code:

python3 ok -q list_to_link

Q3: Every Other

Implement every_other, which takes a linked list s. It mutates s such that all of the odd-indexed elements (using 0-based 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.

def every_other(s):
    """Mutates a linked list so that all the odd-indiced elements are removed
    (using 0-based 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)
    """

    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

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.