Lab 8: Linked Lists

Due by 11:59pm on Friday, April 3.

Starter Files

Download lab08.zip.

Optional WWPD For Inheritance Practice

Q1: What would Python print?

Predict the result of evaluating the following calls in the interpreter. Then try them out yourself!

>>> class Account:
...     interest = 0.02
...     def __init__(self, account_holder):
...         self.balance = 0
...         self.holder = account_holder
...     def deposit(self, amount):
...         self.balance = self.balance + amount
...         print("Yes!")
...
>>> class CheckingAccount(Account):
...     def __init__(self, account_holder):
...         Account.__init__(self, account_holder)
...     def deposit(self, amount):
...         Account.deposit(self, amount)
...         print("Have a nice day!")
...
>>> a = Account("Billy")
>>> a.balance

______
0

>>> c = CheckingAccount("Eric")
>>> c.balance

______
0

>>> a.deposit(30)

______
Yes!

>>> c.deposit(30)

______
Yes!
Have a nice day!

>>> c.interest

______
0.02

Required Questions

Inheritance and 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.

Q2: Mint

A mint is a place where coins are made. In this question, you'll implement a Mint class that can output a Coin with the correct year and worth.

  • Each Mint instance has a year stamp. The update method sets the year stamp of the instance to the present_year class attribute of the Mint class.
  • The create method takes a subclass of Coin (not an instance!), then creates and returns an instance of that subclass stamped with the Mint's year (which may be different from Mint.present_year if it has not been updated.)
  • A Coin's worth method returns the cents value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the present_year class attribute of the Mint class.
class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.present_year.

    >>> mint = Mint()
    >>> mint.year
    2025
    >>> dime = mint.create(Dime)
    >>> dime.year
    2025
    >>> Mint.present_year = 2105  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2025
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2105
    >>> Mint.present_year = 2180     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years)
    115
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    125
    """
    present_year = 2025

    def __init__(self):
        self.update()

    def create(self, coin):
        "*** YOUR CODE HERE ***"

    def update(self) -> None:
        "*** YOUR CODE HERE ***"

class Coin:
    cents = None # will be provided by subclasses, but not by Coin itself

    def __init__(self, year: int):
        self.year = year

    def worth(self) -> int:
        "*** YOUR CODE HERE ***"

class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

Use Ok to test your code:

python3 ok -q Mint

Q3: 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
    """
    "*** YOUR CODE HERE ***"

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)
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q list_to_link

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.