IMPLEMENTING A LINKED LIST WITH RECURSIVE FUNCTIONS IN C++

INTRODUCTION: the program is written in C++ on the eclipse IDE

The linked list operations implemented in Project 3 that involved iteration (loops) can also be implementedrecursively. This project modifies the previous one by carrying out those operations using recursion.

DESCRIPTION

Modify the List class in Project 3 to carry out repetitive operations recursively. These operations include:

Dispose of the dynamic part of a List structure (the destructor).

Re-initialize an existing List to be empty.

Insert a value into a List, in the appropriate position. If the value is already present, the List is unchanged.

Remove a value from a List. If the value is not present, the List is unchanged.

Return the length of a List.

Report whether or not a particular value is present in a List.

Return the value of the k^thelement of a List.

Write out the values in a List, in order, to an output stream.

The remaining operations will be unchanged:

Initialize a List to be empty (the default constructor).

Is a List empty?

Theclient programshould beunchanged; only the List class will be modified.

HINTS

The smaller problem is always the "tail" of the List.

Previous Code: #include

using namespace std; // Allows all standard names to be used

// This will define the structure of the node(s) used in the LinkedList typedef struct _node { int listInfo; struct _node *next; } node;

// The LinkedList class class LinkedList { Private: node *headNode;

public: // The constructor to create a new LinkedList LinkedList() { headNode = nullptr; }

// To re-initialize the LinkedList // Postcondition: the LinkedList reset to empty void reinitialize() { headNode = nullptr; }

// A function to add a user input value into a LinkedList // Precondition: An integer value that must be a real number // Postcondition: The user input integer being added and sorted within the LinkedList // as long as the value is not already present within the list void add(int num) { node *newNode = new node; newNode -> listInfo = num;

if(headNode == nullptr) { newNode ->next = nullptr; headNode = newNode; return; }

node *previousNode; node *tempNode = headNode;

if(tempNode != NULL && tempNode ->listInfo == num) { cout << "That value is already present." << endl; return; }

if(tempNode ->listInfo > num) { newNode ->next = headNode; headNode = newNode; return; }

while(tempNode != NULL && tempNode ->listInfo < num) { previousNode = tempNode; tempNode = tempNode ->next; }

newNode ->next = tempNode; previousNode ->next = newNode;

}

// A function to remove a number from a LinkedList // Precondition: An integer value that must be a real number // Postcondition: The user input number removed if it is present void remove(int num) { node *tempNode; node *prevNode; tempNode = headNode;

if(tempNode ->listInfo == num) { headNode = tempNode ->next; tempNode ->next = nullptr; delete tempNode; return; }

while(tempNode != nullptr && tempNode ->listInfo != num) { prevNode = tempNode; tempNode = tempNode ->next; }

if(tempNode == nullptr) return;

prevNode ->next = tempNode ->next;

tempNode ->next = nullptr; delete tempNode; }

// A function to return the size of the LinkedList // Postcondition: returns the number of values found within the LinkedList int listSize() { node *tempNode = headNode; int counter = 0;

while(tempNode != nullptr) { tempNode = tempNode ->next; counter++; } return counter; }

// A function to determine whether or not a certain number can be found in the LinkedList // Precondition: An integer value that must be a real number // Postcondition: If the searched for integer is/ or is not found the console will print the result void isPresent(int num) { node *tempNode = headNode;

while(tempNode != nullptr && tempNode ->listInfo != num) { tempNode = tempNode ->next; }

if(tempNode != nullptr && tempNode->listInfo == num) cout << "The value " << num << " is present within the list." << endl; else cout << "The value " << num << " is not present within the list." << endl; }

// A function to return the value of the searched for nth element of the LinkedList. // Precondition: An integer value that must be a real number // Postcondition: Finds the position of the integer within the list if there is a value present int findNum(int n) { node *tempNode = headNode;

for(int i = 1; tempNode != nullptr && i < n; i++) { tempNode = tempNode ->next; }

if(tempNode == nullptr) return -1;

return tempNode ->listInfo; }

// A function to display all values found within the LinkedList // Postcondition: The console will print all values found within the LinkedList void printList() { node *tempNode = headNode;

if(tempNode == nullptr) { cout << "The list is currently empty." << endl; return; } cout << "List consists of the value(s): < " << tempNode ->listInfo; tempNode = tempNode ->next;

while(tempNode != nullptr) { cout << ", " << tempNode ->listInfo; tempNode = tempNode ->next; } cout << " >" << endl; }

// A function to check if the LinkedList is empty or not // Postcondition: Returns and prints if the LinkedList is empty void empty() { if(headNode == nullptr) cout << "The list is empty." << endl; else cout << "The list is not empty." << endl; } };