Linked List Utils - COMP110

Overview

In these exercises you will implement a few algorithms to process a singly-linked list data structure.

In the last few lectures, we have been writing methods and functions for the Node class. In this exercise, you will be creating functions that take in and/or return Node objects. Create a new folder in your exercises folder called ex05, and then create a new file in the ex05 folder called linked_list.py. Then, copy your code of the Node class we’ve been using in lectures and paste it into your linked_list.py file. You must use recursive function calls to implement the functions below. If you use loops, your work for that function will be disqualified.

`value_at`

Given a head Node | None and an index int as inputs, return the value of the Node stored at the given index, or raise an IndexError if the index does not exist.

Hint #0: In the recursive case, you will need to modify both arguments to bring your recursive call closer to the base case of hint #2. Start by diagramming on paper what this means for a call to value_at with a list of two or more nodes and an initial index of 1.

Hint #1: An edge case occurs when the list is empty. Raise an IndexError, e.g.: raise IndexError("Index is out of bounds on the list.")

Hint #2: A second base case occurs when the index is 0. Here you should return the value of the current Node being processed on the list.

Skeleton function implementation:

    def value_at(head: Node | None, index: int) -> int:
        raise IndexError("Index is out of bounds on the list.")

Example usage:


>>> from exercises.ex05.linked_list import Node, value_at
>>> value_at(Node(10, Node(20, Node(30, None))), 0)
10
>>> value_at(Node(10, Node(20, Node(30, None))), 1)
20
>>> value_at(Node(10, Node(20, Node(30, None))), 2)
30
>>> value_at(Node(10, Node(20, Node(30, None))), 3)
IndexError: Index is out of bounds on the list.

`max`

Given a head Node, return the maximum value in the linked list. If the linked list is empty, raise a ValueError.

Skeleton function implementation:

    def max(head: Node | None) -> int:
        raise ValueError("Cannot call max with None")


>>> from exercises.ex05.linked_list import Node, max
>>> max(Node(10, Node(20, Node(30, None))))
30
>>> max(Node(10, Node(30, Node(20, None))))
30
>>> max(Node(30, Node(20, Node(10, None))))
30
>>> max(None)
ValueError: Cannot call max with None.

`linkify`

Given a list[int], your linkify function should return a Linked List of Nodes with the same values, in the same order, as the input list.

A skeleton for linkify is:

    def linkify(items: list[int]) -> Node | None:
        return None

You will find it helpful to use Python’s slice subscription notation here, which we haven’t discussed in full but you should now be able to pickup quickly. Try the following in the REPL:


>>> items = [10, 20, 30, 40]
>>> items[1]
20
>>> items[1:3]
[20, 30]
>>> items[:3]
[10, 20, 30]
>>> items[1:]
[20, 30, 40]

Notice when using slice notation a new list is returned to you whose values start with the first index number, inclusive, and end with the index number following the colon, exclusive. If you leave off the starting index, it defaults to 0. If you leave off the ending index, it defaults to the len of the list.

Example usage:


>>> from exercises.ex05.linked_list import linkify
>>> linkify([1, 2, 3])
1 -> 2 -> 3 -> None

After you are certain of the correctness of your linkify function, you may find it valuable to use in writing test cases for the following functions.

`scale`

Given a head Node of a linked list and a int factor to scale by, return a new linked list of Nodes where each value in the original list is scaled (multiplied) by the scaling factor.

Skeleton function implementation:

    def scale(head: Node | None, factor: int) -> Node | None:
        return None

Example usage:


>>> from exercises.ex05.linked_list import scale, linkify
>>> scale(linkify([1, 2, 3]), 2)
2 -> 4 -> 6 -> None

Linting and Type Correctness

Your code will need to pass the common stylistic and type checking guidelines used throughout the semester.

Submit to Gradescope

When you are ready to submit for grading, run the following command:

python -m tools.submission exercises/ex05