EX17 - Linked List Part 2

In Exercise 17, you will continue implementing some algorithms for the linked-list data structure.

0. Pull the skeleton code

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

  1. 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.
  2. 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.
  3. 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.
  4. Return to the File Explorer pane and open the exercises directory. You should see it now contains the directory named ex17. 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 ex17. If you expand that directory, you should see the starter files

Part 1. linkify function

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:

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.

Part 2. scale function

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:

Part 3. concat function

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:

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 “EX17 - Recursive Part 2”. 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 ex17, type the following command (all on a single line):

python -m tools.submission exercises/ex17

In the file explorer pane, look to find the zip file named “21.mm.dd-hh.mm-exercises-ex17.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.