Linked List Utils - UNC Comp 110

In this problem set you will write recursive functions that operate on linked lists of node objects using the functions cons, first, and rest. This problem set is similar to the array utils problem set but will force you to gain comfort working with function call recursion as opposed to loop-based iteration.

For this problem set you should not access the .data and .next properties directly. Instead you should use the functions first and rest.

We are providing skeleton function implementations of the first few functions as well as some example test cases for the first three functions. Many of these functions will use generics so that they work on lists of any type! Pay attention to how these functions are defined as you will need to write tests for the remainder of the functions.

To begin, npm run pull -- followed by npm start.

Then add your honor code header (below) to BOTH of the two files in PS05 you will be working in: list-utils.ts file as well as the test-runner-app.ts. Failure to do so may result in no credit assigned for this problem set.

/**    
 * Author:    
 * ONYEN:    
 * UNC Honor Pledge: I certify that no unauthorized assistance has been received   
 * or given in the completion of this work. I certify that I understand and 
 * could now rewrite on my own, without assistance from course staff,  
 * the problem set code I am submitting.
 */

As with the array utils problem set, you will implement the functions found in list-utils.ts and you will test these implementations from the file test-runner-app.ts.

1. last

Given a head Node<T>, return the value of the last node in the list.

2. valueAt

Given a head Node<T> and an index number as inputs, return the value of the Node stored at the given index. Note that, unlike arrays which have the indexing operator, the index parameter in this function refers to the nth Node in the linked list starting from index 0.

Hint #0: An edge case occurs when the list is empty. Return null.

Hint #1: A base case occurs when the index is 0. Here you should return the value of the first node of the list.

Hint #2: In the recursive case, you will need to modify both arguments to bring your recursive call closer to the base case of hint #1. Start by diagramming on paper what this means for a call to valueAt with a list of two or more nodes and an initial index of 1.

3. max

Given a head Node<number> and a record maximum number, return the maximum value in the list. Note that the initial call to max should be made with a record argument of Number.MIN_SAFE_INTEGER. An alias constant named MIN is established for this value in the main function of test-runner-app.ts.

The record parameter represents the "record maximum value" found recursively. You should compare the record maximum with the current node being processed and choose what record maximum argument to make the recursive call with accordingly.

4. all

Given a head Node<T> and a value of type T to search for, return true if every node in the list is equal to the value parameter, false otherwise. We will define all such that for the empty list we assume a vacuous truth and return true. For example:

all(cons("A", cons("B", null)), "A") // returns false
all(cons("A", cons("A", null)), "A") // returns true
all(null, "A") // returns true

5. equals

Given two head Node<T> parameters, return true if both lists are equal to one another, false otherwise. For example:

equals(cons("A", cons("B", null)), cons("A", cons("B", null))) // true
equals(cons("A", cons("B", null)), cons("B", cons("B", null))) // false
equals(cons("A", cons("B", null)), cons("B", null)) // false

Ensure your equals function is correctly implemented before continuing further!

From this point forward, you will write recursive functions that build up linked lists recursively. In order to test their return values versus some expected list, you will need to use the testList function imported from the test-util.ts file. If you look at this function, you will see that it uses your equals function to determine whether the expected list is equal to the list your function calls actually produce. Until your equals function is implemented correctly, you should not continue on to these next functions.

If your equals function is not implemented correctly, then you may find the following functions look like they're working in your test runner but are actually incorrect.

6. scale

Given an input head Node<number> and a scaling factor number, return a new list of nodes where every node in the input list has a corresponding node in the output list whose input value was multiplied by the scaling factor parameter. For example:

scale(cons(1, cons(2, null)), 3) // results in a list of 3 -> 6 -> null

7. arrayToList

Given an input array of type T and an index value, return a list of Node<T> with the same values in the same orders as the input array. You should assume and test with an assumption that this function is called with an initial an index argument of 0. For example:

arrayToList([1, 2, 3], 0) // returns a list with 1 -> 2 -> 3 -> null

8. concat

Given the head Node<T> of any two lists, return a new list of nodes where the second list of nodes is appended to the first list of nodes. For example:

let stringsAB = cons("A", cons("B", null));
let stringsCD = cons("C", cons("D", null));
concat(stringsAB, stringsCD)
// results in a list with nodes A -> B -> C -> D -> null

9. sub

Given a head node of an input list of any type, a starting index, and a length, return the sublist of the input list starting from the given index that is length long. For example:

let stringsABCD = cons("A", cons("B", cons("C", cons("D", null))));
sub(stringsABCD, 2, 1)
results in a list of C -> null
sub(stringsABCD, 2, 2)
results in a list of C -> D -> null

10. splice

Given a head node of a first list of type T, an index, and a head node of a second list of type T, return a new list of type T where the second list is spliced into, or inserted at, the given index of the first list. For example:

let stringsAB = cons("A", cons("B", null));
let stringsCD = cons("C", cons("D", null));
splice(stringsAB, 0, stringsCD)
// results in a list with nodes C -> D -> A -> B -> null
splice(stringsAB, 1, stringsCD)
// results in a list with nodes A -> C -> D -> B -> null

Comp 110 Linked List Utils