Q1 - 40 pts) Consider the implementation of the List ADT using Singly Linked Lis
ID: 3870889 • Letter: Q
Question
Q1 - 40 pts) Consider the implementation of the List ADT using Singly Linked List. Add a member function (to the List class) called recursivePrintForwardReverseOrders that prints the contents of the list in a recursive fashion in both the forward order and reverse order.
For example, if the contents of the List are: 10 --> 4 --> 8 --> 12 --> 9, the recursive member function should print the List as follows:10 4 8 12 99 12 8 4 10
Note that both the forward and reverse orders should be printed through an invocation of the recursivePrintForwardReverseOrders member function on the List object called from the main function. You are free to choose the parameter(s) that need to be passed to the recursivePrintForwardReverseOrders function. But, you are not supposed to pass more than three parameter(s). A suggestion for the parameter to pass is given in the main function of the code posted for Question 1.
To test your code (and take screenshot), create a List of at least 5 elements and then call the recursivePrintForwardReverseOrders function on this List object by passing a pointer to the first node in the Linked List as an argument, as shown in the main function of the Singly Linked List code for Question 1.
Singly Linked List
#include <iostream>
using namespace std;
// implementing the dynamic List ADT using Linked List
class Node{
private:
int data;
Node* nextNodePtr;
public:
Node(){}
void setData(int d){
data = d;
}
int getData(){
return data;
}
void setNextNodePtr(Node* nodePtr){
nextNodePtr = nodePtr;
}
Node* getNextNodePtr(){
return nextNodePtr;
}
};
class List{
private:
Node *headPtr;
public:
List(){
headPtr = new Node();
headPtr->setNextNodePtr(0);
}
Node* getHeadPtr(){
return headPtr;
}
bool isEmpty(){
if (headPtr->getNextNodePtr() == 0)
return true;
return false;
}
void insert(int data){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
while (currentNodePtr != 0){
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
}
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(0);
prevNodePtr->setNextNodePtr(newNodePtr);
}
void insertAtIndex(int insertIndex, int data){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == insertIndex)
break;
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(currentNodePtr);
prevNodePtr->setNextNodePtr(newNodePtr);
}
int read(int readIndex){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == readIndex)
return currentNodePtr->getData();
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
return -1; // an invalid value indicating
// index is out of range
}
void modifyElement(int modifyIndex, int data){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == modifyIndex){
currentNodePtr->setData(data);
return;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
}
void deleteElement(int deleteIndex){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
Node* nextNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == deleteIndex){
nextNodePtr = currentNodePtr->getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
prevNodePtr->setNextNodePtr(nextNodePtr);
}
void IterativePrint(){
Node* currentNodePtr = headPtr->getNextNodePtr();
while (currentNodePtr != 0){
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
// add code to the member function mergeList(List)
};
int main(){
int largerListSize;
cout << "Enter the number of elements you want to insert in the larger list: ";
cin >> largerListSize;
List largerIntegerList;
for (int i = 0; i < largerListSize; i++){
int value;
cout << "Enter element # " << i << " : ";
cin >> value;
largerIntegerList.insertAtIndex(i, value);
}
cout << "Contents of the Larger List: ";
largerIntegerList.IterativePrint();
int smallerListSize;
cout << "Enter the number of elements you want to insert in the smaller list: ";
cin >> smallerListSize;
List smallerIntegerList;
for (int i = 0; i < smallerListSize; i++){
int value;
cout << "Enter element # " << i << " : ";
cin >> value;
smallerIntegerList.insertAtIndex(i, value);
}
cout << "Contents of the Smaller List: ";
smallerIntegerList.IterativePrint();
largerIntegerList.mergeList(smallerIntegerList);
cout << "Contents of the merged list: ";
largerIntegerList.IterativePrint();
return 0;
}
Explanation / Answer
void ReverseList()
{
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* previousNodePtr = NULL;
Node* nextNodePtr;
while (currentNodePtr != NULL)
{
nextNodePtr = currentNodePtr->getNextNodePtr();
currentNodePtr->setNextNodePtr(previousNodePtr);
previousNodePtr = currentNodePtr;
currentNodePtr = nextNodePtr;
}
headPtr->setNextNodePtr(previousNodePtr);
}
void recursivePrintForwardReverseOrders()
{
IterativePrint();
//Now Reverse the list.
ReverseList();
IterativePrint();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.