EX16 - Linked List Part 1

In Exercise 16, you will implement a few algorithms to process a singly-linked list data structure. Your starting point will be the Node class that we have been working with in lecture.

0. Pull the skeleton code

You will find the starter files needed by “pulling” from the course workspace repository. Before beginning, be sure to:

0. Be sure you are in your course workspace. Open the file explorer and you should see your work for the course. If you do not, open your course workspace through File > Open Recent.
1. Open the Source Control View by clicking the 3-node (circles) graph (connected by lines) icon in your sidebar or opening the command palatte and searching for Source Control.
2. Click the Ellipses in the Source Control pane and select “Pull” from the drop-down menu. This will begin the pulling process from the course repository. It should silently succeed.
3. Return to the File Explorer pane and open the exercises directory. You should see it now contains the directory named ex16. If you expand those directories, you will see the starter files for this exercise.

If the above did not work, try the following:

1. Click the Ellipses in the Source Control pane and select “Pull, Push” from the drop-down menu. Then select “Pull from”. Then select “upstream” and the main option. This will begin the pulling process from the course repository. It should silently succeed.
2. Return to the File Explorer pane and open the exercises directory. You should see it now contains another directory named ex16. If you expand that directory, you should see the starter files

Part 1. last function

Write a function called last with the following specifications:

• 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 definition is provided with the correct function signature below.

    def last(head: Optional[Node]) -> Optional[int]:
        """Returns the last value of a Linked List, or None if the list is empty."""
        return None

Part 2. value_at function

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

Part 3. max function

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

4. Make a Backup Checkpoint “Commit”

As you make progress on this exercise, making backups is encouraged. Note that you do not have to make a backup in order to submit your work, though you are encouraged to before each submission so that you can revert back to a previous point in your project if you accidentally change something you did not intend to.

1. Open the Source Control panel (Command Palette: “Show SCM” or click the icon with three circles and lines on the activity panel).
2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
3. Move your mouse’s cursor over the word Changes and notice the + symbol that appears. Click that plus symbol to add all changes to the next backup. You will now see the files listed under “Staged Changes”.
   • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
4. In the Message box, give a brief description of what you’ve changed and are backing up. This will help you find a specific backup (called a “commit”) if needed. In this case a message such as, “Progress on Exercise 3” will suffice.
5. Press the Check icon to make a Commit (a version) of your work.
6. Finally, press the Ellipses icon (…), look for “Pull/Push” submenu, and select “Push to…”, and in the dropdown select your backup repository.

5. Submit to Gradescope for Grading

Login to Gradescope and select the assignment named “EX16 - Recursive Part 1”. You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to Visual Studio Code.

If you do not see a Terminal at the bottom of your screen, open the Command Palette and search for “View: Toggle Integrated Terminal”.

To produce a zip file for ex16, type the following command (all on a single line):

python -m tools.submission exercises/ex16

In the file explorer pane, look to find the zip file named “21.mm.dd-hh.mm-exercises-ex16.zip”. The “mm”, “dd”, and so on, are timestamps with the current month, day, hour, minute. If you right click on this file and select “Reveal in File Explorer” on Windows or “Reveal in Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.