In these exercises you will implement a few algorithms to process a singly-linked list data structure. Just like in the List Utility functions, these functions will be pure and are well suited for writing test cases. As such, you will also write test cases demonstrating their usage and verifying their correctness.
In the comp110/exercises directory, create a directory named ex10_recursion.
linked_list.pyIn the ex10_recursion directory, create a file named linked_list.py and establish the following starting contents:
"""Utility functions for working with Linked Lists."""
from __future__ import annotations
from typing import Optional
__author__ = "Your PID"
class Node:
"""An item in a singly-linked list."""
data: int
next: Optional[Node]
def __init__(self, data: int, next: Optional[Node]):
"""Construct a singly linked list. Use None for 2nd argument if tail."""
self.data = data
self.next = next
def last(head: Optional[Node]) -> Optional[int]:
"""Returns the last value of a Linked List, or None if the list is empty."""
return Nonelinked_list_test.pyEstablish a file for your test definitions named linked_list_test.py with the following contents:
"""Tests for linked list utils."""
from comp110.exercises.ex10_recursion.linked_list import Node, last
__author__ = "Your PID"
def test_last_empty():
"""Last of an empty List should be the empty list."""
assert last(None) == None
def test_last_non_empty():
"""Last of a non-empty list should return a reference to its last Node."""
linked_list = Node(1, Node(2, Node(3, None)))
assert last(linked_list) == 3As you can see, a skeleton definition of last and some simple tests for last are provided to help get you started. You will responsible for defining the other functions and writing their tests.
You must use recursive function calls to implement the functions below. If you use loops your work for that function will be disqualified.
lastGiven an Option[Node] representing the head Node of a List of any length, including empty, return the value of the last node in the list. If the list is empty, return None. A skeleton definitition is provided with the correct function signature.
value_atGiven a head Option[Node] and an index int as inputs, return the value of the Node stored at the given index, or None 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. Return None.
Hint #2: A second base case occurs when the index is 0. Here you should return the value of the first node of the list.
Example usage:
>>> 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)
NonemaxGiven a head Node, return the maximum value in the linked list. If the linked list is empty, return None.
>>> 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)
NoneYou should write your own tests to be confident of your implementations. None of these functions require much code to complete, but will take some mental gymnastics to think about approaching recursively.
Remember: Focus on what you need to do with only the head node and then leave the rest of the problem working through the rest of the list to the recursive function call.
It is possible to write functionally correct programs that do not satisfy the constraints of the type checker. The reason for this a combination of naivete on the type checker’s part, as well as some gnarly theoretical computer science related to the halting problem which you’ll learn about in COMP455.
The short story is a type checker is typically not going to be able to reason through every possible code path in the same way you’re able to. For example, if you have a function that declares it returns Optional[int], and you call that function, then you are going to need to check for the possibility of None as a return value. This is true even if before the function call you made some other test about the argument that convinced you the function call would return an int. Typically this is a sign you can rewrite your logic to be both easier to follow while also satisfying the type checker. Think about making your test of None based on the returned value of the recursive call rather than on the argument before the call is made. Play around with the code and challenge yourself to rewrite it. This is a puzzle and it’s good practice that forces you to grapple with solving the same problem from different angles of attack.