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.py`

In 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 None
```

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:

```
"""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) == 3
```

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.

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 `int`

s.

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

Skeleton function implementation:

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

`max`

– 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)
None
```

Skeleton function implementation:

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

`linkify`

– 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 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 pointsGiven a head `Node`

of a linked list and a `int`

`factor`

to scale by, return a new linked list of `Node`

s 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 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 -> None
```

Skeleton function implementation:

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

`sub`

– 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 -> None
```

Skeleton function implementation:

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

`splice`

– 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)
None
```

Skeleton function implementation:

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

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

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`