Lab 15 - Linked List

Due by 11:59pm on March 11, 2025

Starter Files

Download lab15.zip. Inside the archive, you will find starter files for the questions in this lab.

Topics

Linked Lists

We've learned that a Python list is one way to store sequential values. Another type of list is a linked list. A Python list stores all of its elements in a single object, and each element can be accessed by using its index. A linked list, on the other hand, is a recursive object that only stores two things: its first value first and a reference to the rest of the list rest, which is another linked list.

We can implement a class, Link, that represents a linked list object. Each instance of Link has two instance attributes, first and rest.

class Link:

    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link), "Link does not follow proper structure"
        self.first = first # first item in the list
        self.rest = rest # the "rest" of the list

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

A valid linked list can be one of the following:

1. An empty linked list (Link.empty)
2. A Link object containing the first value of the linked list and a reference to the rest of the linked list

What makes a linked list recursive is that the rest attribute of a single Link instance points to another linked list! In the big picture, each Link object stores a single value of the list in its "first" attribute. When multiple Links are linked together through each instance's rest attribute, an entire sequence is formed.

Note: This definition means that there are two options for rest attribute of any Link instance: it must be either Link.empty or another Link instance! This is enforced in Link.__init__, which raises an AssertionError if the value passed in for rest is neither of these things.

To check if a linked list is empty, compare it against the class attribute Link.empty. This will often be your base case. For example, the function below prints out whether or not the link it is passed in 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!')

Going Through a Linked List

Although linked lists are recursive, there are still simple enough for us to iterate through them using a while loop. Let's say we want to print out each of the first values in the a linked list. Below are two approaches:

Recursive Approach

def print_ll(link):
    if link is Link.empty:
        return
    else:
        print(link.first)
        print_ll(link.rest)

Iterative Approach

def print_ll(link):
    while link is not Link.empty:
        print(link.first)
        link = link.rest

Required Questions

Q1: Convert Link

Write a function called convert_link that takes in a linked list and returns the sequence as a simple Python list. You may assume that the input list is shallow; that is none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem! When coming up with your recursive solution, it may be helpful to remember that you can concatenate python lists using the + operator like this: where [a, b] + [c] appends "c" to produce a new list [a, b, c].

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

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> convert_link(link)
    [1, 2, 3, 4]
    >>> convert_link(Link.empty)
    []
    """
    # Write your code here

Q2: Store Digits

Write a function store_digits that takes in an integer n and returns a linked list where each element of the list is a digit of n.

Important: Try not to use any string manipulation functions like str and reversed. If you're stuck, consider: how do we access the digits of n one by one? How would we access the "ones" place?

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    """
    # Write your code here

Q3: Every Other

Implement every_other, which takes a linked list link. It mutates link such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(link)
>>> link
Link(1, Link(3))

If link contains fewer than two elements, link remains unchanged. Do not return anything! every_other should mutate the original list.

def every_other(link):
    """Mutates a linked list so that all the odd-indexed 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)
    """
    # Write your code here

Q4: Deep Map Mut

Implement deep_map_mut, 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.

The built-in isinstance function 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)
    >>> link1
    Link(9, Link(Link(16), Link(25, Link(36))))
    """
    # Write your code here

Hints:

• If the element inside of a link is another link, it is another instance of the same problem we were trying to solve, which means we should recursively call our function on that inner link.
• How can you use isinstance to check if an element inside of a link is another link?

Submit

Submit the lab15.py file on Canvas to Gradescope in the window on the assignment page.