Lab 7: Linked Lists

  • Due: Friday 10/16 @ 11:59pm
  • Points: 1
  • Download: lab07.zip

Attendance

You need to submit the lab problems in addition to attending to get credit for lab. Students in mega lab only need to submit the lab problems. Preceptor interviews are highly recommended but not required for lab submissions.

If you are in regular lab, your TA will come around during lab to check you in. If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your lab): attendance form.

Required Questions

Python 3.12 or newer is required for the remainder of the course. Please upgrade if you're using Python 3.11 (or older). See the Install Python section of Lab 0 for instructions.

Review

This drop-down provides an overview of working with linked lists.

Linked Lists

A linked list is a sequence type that is more efficient than a built-in list for certain operations, such as inserting a value at the front of a long list. Two linked lists that differ only in their first item can share the same rest.

type LinkedList[T] = Link[T] | tuple[()]

@dataclass
class Link[T]:
    first: T
    rest: LinkedList[T] = ()  # rest defaults to an empty linked list

A Link is a non-empty LinkedList, and so has a first and rest. The rest of a Link should always be a linked list: either another Link or ().

You can make a LinkedList 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.

Printing a Link shows its elements within parentheses: print(Link(3, Link(4))) displays (3 4).

The second element of s is s.rest.first and the third is s.rest.rest.first.

This linked list visualizer is a great way to understand the structure of a complex linked list.

To check whether a linked list s is empty, use isinstance(s, Link). The VS Code type checker infers that s is a Link and therefore has first and rest attributes only when isinstance(s, Link) is true:

def sum_link(s: LinkedList[int]) -> int:
    """Return the sum of the items in linked list s."""
    if not isinstance(s, Link):
        return 0
    return s.first + sum_link(s.rest)

The type LinkedList[int] describes a linked list whose elements are all integers. A type variable, such as T in def extend[T](s: LinkedList[T], t: LinkedList[T]) -> LinkedList[T], represents any type and expresses that the inputs and output to this function all contain the same type of items.

Linked Lists

Q1: WWPD: Linked Lists

Read over the Link class in link.py. Make sure you understand the doctests.

Predict what Python will display when the following lines are entered into an interactive session in which the Link class has already been defined, then unlock the test to check your answers. Type ERROR if it errors:

python3 -m pytest -k link_wwpd --unlock
Unlocking Examples

>>> from lab07 import Link
>>> a = Link(1000)
>>> a.first
______
>>> a.rest    # the empty linked list is ()
______
>>> print(a)  # printing a linked list shows all its items in parentheses
______

>>> b = Link(1, Link(2, Link(3)))
>>> print(b)
______
>>> b.first
______
>>> b.rest.rest.first
______
>>> b.rest.rest.rest
______
>>> skip = Link(9001, b.rest.rest)
>>> skip.first
______
>>> skip.rest.first
______
>>> skip.rest.rest
______
>>> b.rest.first
______
>>> print(Link(4, b))
______

>>> c = Link(Link(1), Link(2))
>>> c.first.first
______
>>> c.first.rest
______
>>> c.rest.first
______
>>> print(c)
______

>>> d = Link(5, Link(6, Link(7)))
>>> print(d)
______
>>> print(d.rest.rest)
______
>>> print(Link(8, Link(9, d.rest)))
______
>>> print(Link(10, Link(d.rest.rest, d.rest)))
______

>>> print(Link(5, 6))
______

If you get stuck, try drawing a linked list on a piece of paper or running python3 -i link.py and then evaluating different expressions.

Q2: Change

Write a function that takes in a linked list s and two values, old and new. The function returns a copy of s but with all instances of old replaced with new.

Hint: Use recursion. It's easier in this case!

def change[T](s: LinkedList[T], old: T, new: T) -> LinkedList[T]:
    """Returns a linked list matching s but with all instances of old (if any)
    replaced by new.

    >>> s = Link(1, Link(2, Link(3)))
    >>> t = change(s, 3, 1)
    >>> print(t)
    (1 2 1)
    >>> u = change(t, 1, 2)
    >>> print(u)
    (2 2 2)
    >>> v = change(u, 5, 1)
    >>> print(v)
    (2 2 2)
    >>> print(s)   # The original linked list s is unchanged.
    (1 2 3)
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return ()
python3 -m pytest -k change

Q3: Without One

Implement without, which takes a linked list s and a non-negative integer index i. It returns a linked list with all of the elements of s except for the one at index i. (Assume s.first is the element at index 0.)

The original linked list s should not be changed.

If i is greater than or equal to the length of s, then without should return a linked list with the same contents as s.

Hint: Use recursion. It's easier in this case!

def without(s: LinkedList, i: int) -> LinkedList:
    """Return a linked list like s but without the element at index i.

    >>> s = Link(3, Link(5, Link(7, Link(9))))
    >>> print(without(s, 0))
    (5 7 9)
    >>> print(without(s, 2))
    (3 5 9)
    >>> print(without(s, 4))  # There is no index 4, so all of s is retained.
    (3 5 7 9)
    >>> print(s)              # The original linked list s is unchanged.
    (3 5 7 9)
    >>> without((), 0)
    ()
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return ()
python3 -m pytest -k without

Q4: Store Digits

Write a function store_digits that takes in an integer n and returns a linked list containing the digits of n in the same order (from left to right).

Important: Do not use any string manipulation functions, such as str or reversed.

def store_digits(n: int) -> LinkedList[int]:
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(first=1, rest=())
    >>> print(store_digits(2345))
    (2 3 4 5)
    >>> print(store_digits(876))
    (8 7 6)
    >>> print(store_digits(2450))
    (2 4 5 0)
    >>> print(store_digits(20105))
    (2 0 1 0 5)
    >>> # a check that you do not use str or reversed
    >>> import inspect, ast
    >>> [n.id for n in ast.walk(ast.parse(inspect.getsource(store_digits)))
    ...  if isinstance(n, ast.Name) and n.id in ('str', 'reversed')]
    []
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return ()
python3 -m pytest -k store_digits

Submit Assignment

Submit this assignment by running Provenance: Prepare Submission Bundle from the VS Code command palette and uploading the resulting zip to Gradescope. The zip already contains the files you've edited. Lab 00 has detailed instructions.

Your responses to WWPD questions are not submitted, and they do not need to be. Lab credit is based on the code writing questions.


Back to Top

Accessibility Nondiscrimination

Copyright ©2026, Regents of the University of California and respective authors.

This site is built following the Berkeley Class Site template, which is generously based on the Just the Class, and Just the Docs templates.

View all course offerings