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 Previous Code that involved iteration (loops) can also be implemented recursively. This project modifies the previous one by carrying out those operations using recursion.

DESCRIPTION

Modify the List class in Previous Code 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.

Return the length of a List.

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

Return the value of the k^th element of a List.

The remaining operations will be unchanged:

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

Is a List empty?

The client program should be unchanged; only the List class will be modified.

HINTS

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

Previous Code:

#include

using namespace std; typedef struct _node { int listInfo; struct _node *next; } node;

class LinkedList { Private: node *headNode;

public: LinkedList() { headNode = nullptr; }

void reinitialize() { headNode = nullptr; }

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;

}

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

int listSize() { node *tempNode = headNode; int counter = 0;

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

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

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

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

void empty() { if(headNode == nullptr) cout << "The list is empty." << endl; else cout << "The list is not empty." << endl; } };