EX06 - Linked List Utils


Overview

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.

Setup

In the exercises directory, create a directory named ex06.

linked_list.py

In the ex06 directory, create a file named linked_list.py and establish the following starting contents:

There 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 -> None

Additionally, 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.py

Establish a file for your test definitions named linked_list_test.py with the following contents:

As 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.

Type Checking Hints

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.

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.

Requirements

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 points

Given 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 points

Given 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)
None

Skeleton function implementation:

def value_at(head: Optional[Node], index: int) -> Optional[int]:
    return None

max – 10 points

Given 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)
None

Skeleton function implementation:

def max(head: Optional[Node]) -> Optional[int]:
    return None

linkify – 10 points

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.

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 None

Example usage:

>>> 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 – 10 points

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.

Example usage:

>>> scale(linkify([1, 2, 3]), 2)
2 -> 4 -> 6 -> None

Skeleton function implementation:

def scale(head: Optional[Node], factor: int) -> Optional[Node]:
    return None

concat – 10 points

Given 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 -> None

Skeleton function implementation:

def concat(lhs: Optional[Node], rhs: Optional[Node]) -> Optional[Node]:
    return None

sub – 10 points

Given 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 -> None

Skeleton function implementation:

def sub(list: Optional[Node], start: int, length: int) -> Optional[Node]:
    return None

splice – 10 points

Given 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)
None

Skeleton function implementation:

def splice(list_a: Optional[Node], index: int, list_b: Optional[Node]) -> Optional[Node]:
    return None

Testing – 10 points

You 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_.

Hand-in is Open

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