#include <iostream> using namespace std; // implementing the dynamic List ADT us

Question

#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 for the member function to find the value of the

// middle element in the list and return the value

};

int main(){

int listSize;

cout << "Enter the number of elements you want to insert: ";

cin >> listSize;

List integerList; // Create an empty list

for (int i = 0; i < listSize; i++){

int value;

cout << "Enter element # " << i << " : ";

cin >> value;

integerList.insertAtIndex(i, value);

}

cout << "Contents of the List: ";

integerList.IterativePrint();

// add code to call the member function to find the value of the middle element in the

// integerList and print the return value of the function

return 0;

}

Q1-25 pts) Extend the source code for the Singly Linked List (attached to the quiz description) by adding a member function to find the middle value of the elements in the List. Also, extend the main function given in the source code to call the member function and print the return value (i.e., the middle value of the elements in the List) Test your program with both even and odd values for the size of the Linked List. If 'n' is the size of the Linked List, the program should print the n/2th element in the Linked List if 'n' is even and print the (n-1)/2th element in the Linked List if 'n' is odd. You should test the program with two values (an odd value and an even value) for the size of the Linked List that could range anywhere from 10 to 20. The maximum value for any element in the Linked List is Note: You are supposed to use the source code provided with the quiz description. You are not supposed to add any indexing variable or member function to the Node class. Also, you are required to use the existing private variables and public member functions of the List class in the source code and do the implementation. All of the computations should be incorporated in the member function to compute the middle value of the elements in the List.

Explanation / Answer

function finds the middle value in the linked list: has been inserted:

#include <cstdlib>
#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;
}
//the member function middle to find the value of the middle element in the
// integerList and print the return value of the function
int middle(){
// two pointer for accessing the middle element
Node* firstNodePtr = headPtr;
Node* secondNodePtr = headPtr;
if(headPtr!=NULL)
{
//firstNodePtr increments doubly and SecondNodePtr moves to find the middle node
while(firstNodePtr != NULL && firstNodePtr ->getNextNodePtr()!=NULL ){
firstNodePtr = firstNodePtr ->getNextNodePtr()->getNextNodePtr();
secondNodePtr = secondNodePtr->getNextNodePtr();
}
//returns the middle node
return(secondNodePtr->getData());
}
  
}
};

int main(int argc, char** argv) {
int listSize;
cout << "Enter the number of elements you want to insert: ";
cin >> listSize;
List integerList; // Create an empty list
for (int i = 0; i < listSize; i++){
int value;
cout << "Enter element # " << i << " : ";
cin >> value;
integerList.insertAtIndex(i, value);
}
cout << "Contents of the List: ";
integerList.IterativePrint();
//code to call the member function to find the value of the middle element in the
// integerList and print the return value of the function
cout<<"The middle element in the list :"<<integerList.middle();
return 0;
  
}

sample output #1 for odd number in the list

Enter the number of elements you want to insert: 5
Enter element # 0 : 4
Enter element # 1 : 7
Enter element # 2 : 1
Enter element # 3 : 2
Enter element # 4 : 3
Contents of the List: 4 7 1 2 3
The middle element in the list :1
RUN SUCCESSFUL (total time: 14s)

sample output #2 for odd number in the list

Enter the number of elements you want to insert: 6
Enter element # 0 : 1
Enter element # 1 : 2
Enter element # 2 : 3
Enter element # 3 : 4
Enter element # 4 : 5
Enter element # 5 : 6
Contents of the List: 1 2 3 4 5 6
The middle element in the list :3
RUN SUCCESSFUL (total time: 11s)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.