Data Structures. Modify the following two files to implement the functions in a linked list using recursion. This is done through Putty and Unix. The two files that need to be modified are Node.hpp, where error checking is needed in appropriate functions that throw std::logic_error exceptions and exception_test_driver.cpp where cases will be tested. The functions that need to be completed are denoted by the bolded TODO comments in the code.

The first is Node.hpp

Node.hpp

/** * @file Node.hpp */

#ifndef NODE_HPP #define NODE_HPP

#include #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) throw(std::logic_error){ // Error check if (head == nullptr && position > 1) { throw (std::logic_error("Invalid insert position")); }

// Base case if (position == 1) { Node* newNode = new Node(); newNode->data = element; newNode->next = head; return newNode; } // Recursive case else { head->next = insert(head->next, position-1, element); 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) { // Base case if (head == nullptr) { std::cout << "NULL" << std::endl; } // Recursive case else { std::cout << head->data << " -> "; show(head->next); } }

/** * 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; }

/** * Gets the number of elements in the list. * @param head the head of the linked list. * @return The length of the entries currently in the list. */ template int length(Node* head) { // TODO implement this function using recursion. return 0; }

/** * Checks whether a element is contained in the list. * @param head the head of the linked list. * @param element the element to test. * @return True if the element is in the list, otherwise false. */ template bool contains(Node* head, T element) { // TODO implement this function using recursion. return false; }

/** * Gets the element at the given position in the list * @pre 1 <= position <= length(head) * @param head the head of the linked list * @param position the list position of the desired element. * @return the element at the desired list position. */ template T getElement(Node* head, int position) { // TODO implement this function using recursion. return head->data; }

/** * Gets the position of the first occurrence of the desired element. * @param head the head of the linked list * @param element the desired element. * @return The integer position of the desired element if it occurs in the list, * otherwise -1. */ template int getPosition(Node* head, T element) { // TODO implement this function using recursion. return -1; }

/** * Replaces the element at the given position in the list. * @pre 1 <= position <= length(head) * @param head the head of the linked list. * @param position the list position of the element to replace. * @param element the replacement element * @return the head of the modified list. */ template Node* replace(Node* head, int position, T element) { // TODO implement this function using recursion. return head; }

/** * Removes the element at a given position from the list. * @pre 1 <= position <= length(head) * @param head the head of the linked list. * @param position the list position of the entry to remove. * @return the head of the modified list. */ template Node* remove(Node* head, int position) { // TODO implement this function using recursion. return head; }

#endif

/** * @file Node.hpp */

#ifndef NODE_HPP #define NODE_HPP

#include #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) throw(std::logic_error){ // Error check if (head == nullptr && position > 1) { throw (std::logic_error("Invalid insert position")); }

// Base case if (position == 1) { Node* newNode = new Node(); newNode->data = element; newNode->next = head; return newNode; } // Recursive case else { head->next = insert(head->next, position-1, element); 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) { // Base case if (head == nullptr) { std::cout << "NULL" << std::endl; } // Recursive case else { std::cout << head->data << " -> "; show(head->next); } }

/** * 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; }

/** * Gets the number of elements in the list. * @param head the head of the linked list. * @return The length of the entries currently in the list. */ template int length(Node* head) { // TODO implement this function using recursion. return 0; }

/** * Checks whether a element is contained in the list. * @param head the head of the linked list. * @param element the element to test. * @return True if the element is in the list, otherwise false. */ template bool contains(Node* head, T element) { // TODO implement this function using recursion. return false; }

/** * Gets the element at the given position in the list * @pre 1 <= position <= length(head) * @param head the head of the linked list * @param position the list position of the desired element. * @return the element at the desired list position. */ template T getElement(Node* head, int position) { // TODO implement this function using recursion. return head->data; }

/** * Gets the position of the first occurrence of the desired element. * @param head the head of the linked list * @param element the desired element. * @return The integer position of the desired element if it occurs in the list, * otherwise -1. */ template int getPosition(Node* head, T element) { // TODO implement this function using recursion. return -1; }

/** * Replaces the element at the given position in the list. * @pre 1 <= position <= length(head) * @param head the head of the linked list. * @param position the list position of the element to replace. * @param element the replacement element * @return the head of the modified list. */ template Node* replace(Node* head, int position, T element) { // TODO implement this function using recursion. return head; }

/** * Removes the element at a given position from the list. * @pre 1 <= position <= length(head) * @param head the head of the linked list. * @param position the list position of the entry to remove. * @return the head of the modified list. */ template Node* remove(Node* head, int position) { // TODO implement this function using recursion. return head; }

#endif

-----------------------------------------------------------------------------------------------------------------------------------------------------------

exception_test_driver.cpp

/** * @file exception_test_driver.cpp */

#include "Node.hpp"

/** * Tests the error cases of the Node functions that rely on position. * @return the exit code */ int main() {

// this sets cout to print booleans as strings std::cout << std::boolalpha;

// TODO write tests that use invalid positions for the Node functions that // rely on position.

return 0; }