Data Structures. Modify the following two files to implement functions that perform operations on a linked list. This is done through Putty and Unix. The functions that need to be completed are denoted by the bolded TODO comments in the code. The expected output is also shown.

The first is src/Node.hpp

There is a test program, src/int test driver.cpp, that tests the linked list operations where the actual template parameter is of type int. There is also a reference file, test/test.ref that contains the correct output of running the program. Executing the make test command will compare the reference file to your output. If you see TEST SUCCESSFUL after the program output, then there is a high likelihood that your implementation of Node.hpp is correct.

/** * @file Node.hpp * CSC 237, Spring 2021, Assignment 1 */

#ifndef NODE_HPP #define NODE_HPP

#include #include

/** * @class Node * @brief A node in a linked list */ template struct Node { /** The data element **/ T data; /** A pointer to the next Node **/ Node* next; };

/** * Insert an element into a linked list at a given position * @pre The position is within the bound of the list, that is, * 1 <= position <= length(head)+1 * @param head the head of the linked list. * @param position the list position at which to insert element. * @param element the element to insert into the list. * @return the head of the modified list */ template Node* insert(Node* head, int position, T element) { Node *newNode = new Node(); newNode->data = element; if (position == 1) { newNode->next = head; head = newNode; } else { Node* previousNode = head; for (int p = 1; p < position-1; p++) { previousNode = previousNode->next; } newNode->next = previousNode->next; previousNode->next = newNode; }

return head; }

/** * Display a string representation of the list to standard out. * @param head the head of the linked list. */ template void show(Node* head) { Node* currentNode = head; while (currentNode != nullptr) { std::cout << currentNode->data; std::cout << " -> "; currentNode = currentNode->next; } std::cout << "NULL" << std::endl; }

/** * Checks whether the list is empty. * @param head the head of the linked list. * @return True if the list is empty, otherwise false. */ template bool isEmpty(Node* head) { return head == nullptr; }

// TODO document and complete the implementation of the following function that // returns the number of elements in a linked list. template int length(Node* head) { return 0; }

// TODO document and complete the implementation of the following function that // returns a boolean indicating whether the parameter element is contained // within the linked list. template bool contains(Node* head, T element) { return false; }

// TODO document and complete the implementation of the following function that // returns the element at the desired position of the list. Note that the // positions start at one, unlike a C++ array, where the indices start at zero. // You can assume that the caller of the function will pass in a valid // position, but that assumption must be documented appropriately. template T getElement(Node* head, int position) { return head->data; }

// TODO document and complete the implementation of the following function that // returns the position of the first instance of the element passed in as a // parameter. If the element is not present in the list, then return -1. template int getPosition(Node* head, T element) { return -1; }

// TODO document and complete the implementation of the following function that // replaces the element at the desired position of the list and returns the // head of the modified list. Note that the positions start at one, unlike a // C++ array, where the indices start at zero. You can assume that the caller // of the function will pass in a valid position, but that assumption must be // documented appropriately. template Node* replace(Node* head, int position, T element) { return head; }

// TODO document and complete the implementation of the following function that // removes the Node at the desired position of the list and returns the head of // the modified list. Note that the positions start at one, unlike a C++ array, // where the indices start at zero. You can assume that the caller of the // function will pass in a valid position, but that assumption must be // documented appropriately. template Node* remove(Node* head, int position) { return head; }

#endif

This second file is src/string test driver.cpp

This is the test component of this assignment. You need to add tests in the src/string test driver.cpp file to test the linked list operations where the actual template parameter is of type std::string. Make sure to test all of the operations and potential corner cases. There is also a reference file, test/string test.ref that contains the sample output of running your test program.

/** * @file string_test_driver.cpp * CSC 237, Spring 2021, Assignment 1 */

#include #include "Node.hpp"

/** * Tests the Node functions using string as the actual template parameter * @return the exit code */ int main() { // TODO write tests for the Node functions using std::string as the actual // parameter type.

return 0; }

EXPECTED OUTPUT:

==============================================================

-bash-4.1$ ./int_test_driver Create an empty list containing type int isEmpty(head): true show(head) NULL length(head): 0

Add the integers from 1 to 10 to the list isEmpty(head): false show(head) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL

head = insert(head, 10, 42) show(head) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 42 -> 10 -> NULL length(head): 11

contains(head, 5): true contains(head, 9000): false

getElement(head, 10): 42

getPosition(head, 42): 10 getPosition(head, 20): -1

replace(head, 7, 9000) show(head) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 9000 -> 8 -> 9 -> 42 -> 10 -> NULL

head = remove(head, 7) show(head) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> 42 -> 10 -> NULL length(head): 10

head = remove(head, 1) show(head) 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> 42 -> 10 -> NULL length(head): 9

===============================================================

-bash-4.1$ ./string_test_driver Create an empty list containing type string isEmpty(head): true show(head) NULL length(head): 0

Add the strings to the list isEmpty(head): false show(head) one -> two -> three -> four -> five -> NULL

head = insert(head, 3, std::string("Bob")) show(head) one -> two -> Bob -> three -> four -> five -> NULL length(head): 6

contains(head, std::string("one")): true contains(head, std::string("Alice")): false

getElement(head, 3): Bob

getPosition(head, std::string("five")): 6 getPosition(head, std::string("Alice")): -1

replace(head, 3, std::string("Eve")) show(head) one -> two -> Eve -> three -> four -> five -> NULL

head = remove(head, 3) show(head) one -> two -> three -> four -> five -> NULL length(head): 5

head = remove(head, 1) show(head) two -> three -> four -> five -> NULL length(head): 4