Lab 4: Linked Lists

  • Due: Wednesday 09/30 @ 11:59pm
  • Points: 1
  • Download: lab04.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.

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

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 lab04 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: Print Every Other

Implement print_every_other, which takes a linked list s and prints every other element of s, starting with the first, each on its own line. It prints nothing if s is empty. It returns None, which should happen automatically; you don't need a return statement.

def print_every_other(s: LinkedList) -> None:
    """Print every other element of linked list s, starting with the first.

    >>> sentence = Link('I', Link('have', Link('love', Link('for', Link('Oski')))))
    >>> print_every_other(sentence)
    I
    love
    Oski
    >>> print_every_other(Link(1, Link(2, Link(3, Link(4)))))
    1
    3
    >>> print_every_other(Link(5))
    5
    >>> print_every_other(())
    """
    "*** YOUR CODE HERE ***"

python3 -m pytest -k print_every_other

Q5: 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.

Optional Questions

These questions are optional. If you don't complete them, you will still receive credit for this assignment. They are great practice, so do them anyway!

Q6: Linked Sum

This was Question 6 on the Summer 2016 61A Midterm.

Implement linked_sum, which takes a linked list of positive integers s and a non-negative integer total. It returns the number of ways that adding up items in s can sum up to total. Each item can be used more than once.

def linked_sum(s: LinkedList[int], total: int) -> int:
    """Return the number of combinations of elements in s that
    sum up to total.

    >>> # Four combinations: 1 1 1 1 , 1 1 2 , 1 3 , 2 2
    >>> linked_sum(Link(1, Link(2, Link(3, Link(5)))), 4)
    4
    >>> linked_sum(Link(2, Link(3, Link(5))), 1)
    0
    >>> # One combination: 2 3
    >>> linked_sum(Link(2, Link(4, Link(3))), 5)
    1
    """
    if ____________________________:
        return 1
    elif ____________________________:
        return 0
    else:
        with_first = ____________________________
        without_first = ____________________________
        return ____________________________

python3 -m pytest -k linked_sum

Q7: Max Pair Sum

This was Question 4(e) on the Fall 2023 61A Final.

Definition: A pairing of a sequence s is a list of two-element tuples (called pairs) that contain adjacent elements of s. There must be at least one element of s between any two pairs in the pairing. The pairs in the pairing must be in the same order as they are in s.

The sequence [4, 5, 6, 1, 2, 3, 7, 8] has pairings [(6, 1), (3, 7)] and [(4, 5), (1, 2), (7, 8)] and [] and many others, but the following are not pairings of that sequence:

  • [(5, 1), (3, 7)] contains a pair (5, 1), but 5 and 1 are not adjacent in the sequence.
  • [(5, 6), (1, 2)] contains two pairs with no element between them, since 6 is adjacent to 1 in the sequence.
  • [(1, 2), (4, 5)] contains valid pairs, but those pairs are not in the same order as the sequence.

Implement max_pair_sum, which takes a linked list s (either a Link or ()). It returns the largest possible sum of the values in a pairing of s.

def max_pair_sum(s: LinkedList[int]) -> int:
    """Return the largest sum of values in a pairing for a linked list of positive numbers s.

    >>> L = Link                                                     # Abbreviate Link
    >>> max_pair_sum(L(3, L(4, L(5, L(3, L(4, L(5, L(6))))))))       # 4+5 + 5+6
    20
    >>> max_pair_sum(L(3, L(4, L(5, L(3, L(4, L(5, L(6, L(3))))))))) # 3+4 + 3+4 + 6+3
    23
    """
    if ____________________________:
        return 0
    n = ____________________________
    if not isinstance(s.rest.rest, Link):
        return n
    else:
        return max(n + max_pair_sum(____________), max_pair_sum(____________))

python3 -m pytest -k max_pair_sum

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