The deleteElement(int deleteData) member function in the code for the Singly Lin

Question

The deleteElement(int deleteData) member function in the code for the Singly Linked Listbased implementation of a List ADT deletes the first occurrence of deleteData in the List. Modify this member function in such a way that all occurrences of deleteData in the List are deleted with a single call to the deleteElement function from main. After you modify the deleteElement function, run the main function (as given in the startup code for this question) by creating a List of at least 10 elements with certain elements repeating. Now ask for a value (deleteData) to delete from the user and call the deleteElement(deleteData) function to delete all occurrences of deleteData in the List. Capture the output of your program displaying the contents of the List before and after the call to the deleteElement function

#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 deleteData){

// The code given here deletes only the first occurrence of 'deleteData'

// Modify the deleteElement member function to delete all occurrences of 'deleteData'

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

while (currentNodePtr != 0){

if (currentNodePtr->getData() == deleteData){

nextNodePtr = currentNodePtr->getNextNodePtr();

prevNodePtr->setNextNodePtr(nextNodePtr);

break;

}

else{

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

}

}

void IterativePrint(){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

cout << currentNodePtr->getData() << " ";

currentNodePtr = currentNodePtr->getNextNodePtr();

}

cout << endl;

}

};

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: (before delete) ";

integerList.IterativePrint();

// to delete all occurrences of a particular data

int deleteData;

cout << "Enter the data to delete: ";

cin >> deleteData;

integerList.deleteElement(deleteData); // modify the deleteElement member function to delete

// all occurrences of 'deleteData'

cout << "Contents of the List (after delete): ";

integerList.IterativePrint();

return 0;

}

Explanation / Answer

The modification to deleteElement member function is highlighted in bold. The change is to remove the break statement from deleteElement member function so that attempt can be made to delete other occurances of given 'deleteData'. Also, currentNodePtr is updated after deletion so that further deletions (if any) can be done. Sample execution output is also provided for reference.

File: SinglyLinkedList.cpp

#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 deleteData) {
// The code given here deletes only the first occurrence of 'deleteData'
// Modify the deleteElement member function to delete all occurrences of 'deleteData'
Node * currentNodePtr = headPtr->getNextNodePtr();
Node * prevNodePtr = headPtr;
Node * nextNodePtr = headPtr;
while (currentNodePtr != 0) {
if (currentNodePtr->getData() == deleteData) {
nextNodePtr = currentNodePtr->getNextNodePtr();
prevNodePtr->setNextNodePtr(nextNodePtr);
currentNodePtr = nextNodePtr;
} else {
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
}
}
}

void IterativePrint() {
Node * currentNodePtr = headPtr->getNextNodePtr();
while (currentNodePtr != 0) {
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
};

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: (before delete) ";
integerList.IterativePrint();

// to delete all occurrences of a particular data
int deleteData;
cout << "Enter the data to delete: ";
cin >> deleteData;
integerList.deleteElement(deleteData); // modify the deleteElement member function to delete
// all occurrences of 'deleteData'
cout << "Contents of the List (after delete): ";
integerList.IterativePrint();
return 0;
}

Sample Execution Output:

Enter the number of elements you want to insert: 10
Enter element # 0 : 1
Enter element # 1 : 2
Enter element # 2 : 3
Enter element # 3 : 1
Enter element # 4 : 2
Enter element # 5 : 3
Enter element # 6 : 1
Enter element # 7 : 2
Enter element # 8 : 3
Enter element # 9 : 1
Contents of the List: (before delete) 1 2 3 1 2 3 1 2 3 1
Enter the data to delete: 1
Contents of the List (after delete): 2 3 2 3 2 3

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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