Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

TITLE IMPLEMENTING A LINKED LIST WITH RECURSIVE FUNCTIONS IN C++ INTRODUCTION The linked list operations implemented in Project 3 that involved iteration (loops) can also

TITLE

IMPLEMENTING A LINKED LIST WITH RECURSIVE FUNCTIONS IN C++

INTRODUCTION

The linked list operations implemented in Project 3 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 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 kth element 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?

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

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Information Modeling And Relational Databases

Authors: Terry Halpin, Tony Morgan

2nd Edition

0123735688, 978-0123735683

More Books

Students also viewed these Databases questions

Question

7 of 28 View Policies Answered: 1 week ago

Answered: 1 week ago