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 exercises directory, create a directory named ex06.
linked_list.pyIn the ex06 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 __repr__(self) -> str:
"""Produce a string representation of a linked list."""
if self.next is None:
return f"{self.data} -> None"
else:
return f"{self.data} -> {self.next}"
def is_equal(lhs: Optional[Node], rhs: Optional[Node]) -> bool:
"""Test if two linked lists are deeply (values and order) equal to one another."""
if lhs is None and rhs is None:
return True
elif lhs is None or rhs is None or lhs.data != rhs.data:
return False
else:
return is_equal(lhs.next, rhs.next)
def last(head: Optional[Node]) -> Optional[int]:
"""Returns the last value of a Linked List, or None if the list is empty."""
return NoneThere is some magic happening in the above code listing. The __repr__ magic method is used to produce string representations of objects. So if you create a Node object and print it, python will automagically call the __repr__ method and print out your custom string message. This will be super helpful when you are creating your own linked lists for testing.
For example, without a __repr__ method defined on our Node class, we would expect to see something like this:
>>> example_node = Node(3, Node(2, None))
<Node object at 0x7f959129e130>But if we have the __repr__ method defined as above, we should get:
>>> example_node = Node(3, Node(2, None))
3 -> 2 -> NoneAdditionally, we have provided the is_equal function for testing if two linked lists are equivalent to each other. We will go over this function in class on Thursday, and you should make use of it when writing tests cases for all functions after max.
linked_list_test.pyEstablish a file for your test definitions named linked_list_test.py with the following contents:
"""Tests for linked list utils."""
from exercises.ex06.linked_list import Node, last
__author__ = "Your PID"
def test_last_empty() -> None:
"""Last of an empty List should be the empty list."""
assert last(None) == None
def test_last_non_empty() -> None:
"""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.
To run your tests, run python -m pytest exercises/ex06/linked_list_test.py in the terminal. This will be a more reliable way to test your functions than the testing/beaker tab in VSCode.
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.
For example, code like this will result in a type checking error that reads “Incompatible types in assignment (expression has type”Optional[int]“, variable has type”int“)”. This is beacuse we can’t be sure what the result of max(head.next) will be. It could be None or an int. So when we try to compare num and head.data, we get an error.
def max(head: Optional[Node]) -> Optional[int]:
if head is None:
...
else:
num: int = max(head.next)
if num > head.data:
.....We can fix this by being more explicit about what values we expect our variable to have. Now when we get to the num > head.data comparison, we know for sure we are comparing two ints.
def max(head: Optional[Node]) -> Optional[int]:
if head is None:
...
else:
num = max(head.next)
if num is None:
...
else:
if num > head.data:
.....You must use recursive function calls to implement the functions below. If you use loops your work for that function will be disqualified.
last – 10 pointsGiven an Optional[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 above.
value_at – 10 pointsGiven a head Optional[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)
NoneSkeleton function implementation:
def value_at(head: Optional[Node], index: int) -> Optional[int]:
return Nonemax – 10 pointsGiven 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)
NoneSkeleton function implementation:
def max(head: Optional[Node]) -> Optional[int]:
return Nonelinkify – 10 pointsGiven 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.
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.
A skeleton for linkify is:
def linkify(items: List[int]) -> Optional[Node]:
return NoneExample usage:
>>> linkify([1, 2, 3])
1 -> 2 -> 3 -> NoneAfter 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 – 10 pointsGiven 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.
Example usage:
>>> scale(linkify([1, 2, 3]), 2)
2 -> 4 -> 6 -> NoneSkeleton function implementation:
def scale(head: Optional[Node], factor: int) -> Optional[Node]:
return Noneconcat – 10 pointsGiven two linked lists, return an entirely new linked list where the first list is followed by the second list. You should not reuse any existing Node objects in the implementation of this function.
Hint #1: You will need to fully process both lists.
Hint #2: You do not need to make forward progress in both lists at each step.
Caution: Your function may appear to work locally but will have points deducted if you do not make new Node objects that correspond to each of the original Node objects in both linked lists.
Example usage:
>>> scale(linkify([1, 2, 3]), 2)
2-> 4 -> 6 -> None
>>> concat(linkify([1, 2, 3]), linkify([4, 5, 6]))
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NoneSkeleton function implementation:
def concat(lhs: Optional[Node], rhs: Optional[Node]) -> Optional[Node]:
return Nonesub – 10 pointsGiven a linked list, a starting index, and a length, return the sublist of the input list starting from the given index that is length long.
If your start index is larger than the length of your list, return None. If your start index is less than 0, just start your sublist from the beginning of the input list.
Additionally, if the length parameter is larger than the length of your input list, just include all elements following the start index.
Example usage:
>>> sub(linkify([1, 2, 3, 4]), 1, 2)
2-> 3 -> None
>>> sub(linkify([1, 2, 3, 4]), 5, 2)
None
>>> sub(linkify([1, 2, 3, 4]), -1, 2)
1-> 2 -> NoneSkeleton function implementation:
def sub(list: Optional[Node], start: int, length: int) -> Optional[Node]:
return Nonesplice – 10 pointsGiven a linked list, an index, and second linked list, return a new list where the second list is spliced into, or inserted at, the given index of the first list.
If the index is larger than the length of your list, append the second list to the end of the first list. If your start index is less than 0, splice your second list in at the start of your first list.
Example usage:
>>> splice(linkify([1, 2]), 1, linkify([3, 4]))
1-> 3 -> 4 -> 2 -> None
>>> splice(linkify([1, 2]), -1, linkify([3, 4]))
3 -> 4 -> 1 -> 2 -> None
>>> splice(linkify([1, 2]), 3, linkify([3, 4]))
1 -> 2 -> 3 -> 4 -> None
>>> splice(None, 1, linkify([3, 4]))
3 -> 4 -> None
>>> splice(linkify([1, 2]), 3, None)
1 -> 2 -> None
>>> splice(None, 3, None)
NoneSkeleton function implementation:
def splice(list_a: Optional[Node], index: int, list_b: Optional[Node]) -> Optional[Node]:
return NoneYou are required to write at least 3 tests for each of the functions above. This will be good practice in thinking about the different edge and use cases for each. Our autograder will be checking for this.
Reminder to change function names and rediscover tests as you add them. Test functions must have unique names and their names must begin with test_.
You 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.
Go ahead and delete any submission zips lingering around in your workspace from the previous exercise.
When you are ready to submit for grading, close out any open Python Debug Console terminals using the Trash Can and then open up a clean, new terminal.
python -m tools.submission exercises/ex06