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
