A struct was used to define a Node, which had two data members: an integer data
ID: 3724376 • Letter: A
Question
A struct was used to define a Node, which had two data members: an integer data and a Node * (node pointer) next. We implemented several methods for our list, for example, a destructor, a printAllNodes method, and an insertAtFront.
In this assignment, you will modify our lecture LinkedList to work in a slightly different way. We will use the insertAtEnd and removeAtEnd that make use of the tail pointer.
Implement soft delete. Soft deletion is a way of marking some data as no longer being considered a list member even though it is physically still present. To accomplish this, we will add a third data member to our Node struct, bool deleted, which will be true if the node is deleted and false otherwise. So that we can track how this works, we’ll also add two counters to our LinkedList class: int numNodes, which will track the number of Nodes that we consider not deleted (even if they are physically present), and int numNodesExisting, which will track the number of Nodes that are physically present whether they have been “soft deleted” or not. Make sure you update the methods we developed in lecture so that they will update numNodes and numNodesExisting. See the table for a list of how the functions should work with soft delete.
Finally, we’ll implement a cleanList( ) member function that will traverse the list and actually physically delete (deallocate and update the needed pointers) any Nodes that have been marked as deleted. Remember to update the relevant data member(s) of LinkedList as well.
Use the numNodes and numNodesExisting data members (and their getters) to test that your code is working as you expect.
Soft delete will not work properly unless all the methods play by its rules. Below is a table of the expected function of each of our methods given the soft delete.
Testing:
Write tests for each of the methods listed. Make sure all work with the three edge cases we discussed in lecture: an empty list, with lists of one Node, and with lists of multiple Nodes. For those that return Booleans, show some tests that will yield both true and false results.
Expected result from the defined methods
Method
Expected result
printAllNodes()
Uses the provided code; will be of use for debugging.
insertAtFront, insertAtEnd
When inserting a new node, its “deleted” member will need to be initialized to “false”. Makes use of the tail pointer to insertAtEnd. Updates necessary data members.
removeAtFront, removeAtEnd
Will simply mark the appropriate Node as deleted without deallocating space and without updating head or tail. Will update necessary data members.
cleanList()
Actually removes Nodes from heap memory.
operator=
Should copy over all the data literally, including the soft deleted Nodes. Edit: one way to do this is to simply make another pass through the lists with a pointer on each and update the deleted data member on the corresponding Node.
Here's the code:
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next;
};
class LinkedList {
private:
Node* head;
Node* tail;
void deleteAllNodes();
public:
LinkedList();
~LinkedList();
LinkedList& operator=(const LinkedList& rhs);
LinkedList(const LinkedList& listToCopy);
void printAllNodes() const;
void insertAtFront(int data);
bool removeAtFront();
// demonstrating difference between having tail pointer or not
void insertAtEnd(int data);
bool removeAtEnd();
};
LinkedList::LinkedList() {
head = nullptr;
tail = nullptr;
}
LinkedList::~LinkedList() {
deleteAllNodes();
}
void LinkedList::deleteAllNodes() {
Node* curr = head;
Node* tmp;
if (curr != nullptr) {
tmp = curr->next;
delete curr;
curr = tmp;
}
head = nullptr;
tail = nullptr;
}
LinkedList& LinkedList::operator=(const LinkedList& rhs) {
if (head != rhs.head) {
deleteAllNodes();
Node* rhsCurr = rhs.head;
while (rhsCurr != nullptr) {
insertAtEnd(rhsCurr->data);
rhsCurr = rhsCurr -> next;
}
}
return *this;
}
LinkedList::LinkedList(const LinkedList& listToCopy) {
// deleteAllNodes is safe for empty lists
head = nullptr;
tail = nullptr;
*this = listToCopy;
}
void LinkedList::insertAtFront(int data) {
// adding tail functionality
bool firstNode = false;
if (head==nullptr)
firstNode = true;
Node* newNode = new Node;
newNode->data = data;
newNode->next = head;
head = newNode;
if (firstNode)
tail = head;
}
bool LinkedList::removeAtFront() {
if (head==nullptr)
return false;
Node* tmp;
tmp = head;
head = head -> next;
if (tmp==tail) // length is one Node
tail = nullptr;
delete tmp;
return true;
}
// This method makes use of tail
void LinkedList::insertAtEnd(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = nullptr;
if (head==nullptr) // empty list case
head = newNode;
if (tail!=nullptr) //
tail->next = newNode;
tail = newNode;
}
// This method makes use of tail
bool LinkedList::removeAtEnd() {
// not much difference; we still have to get the second to last node
if (head==nullptr) // empty
return false;
else if (head->next == nullptr) { // length 1
delete head;
head = nullptr;
tail = nullptr;
}
else { // definitely 2 or more Nodes
Node* secondToLast = head;
while (secondToLast->next != tail) {
secondToLast = secondToLast -> next;
}
// now we are pointing to the last and second to last Nodes
delete tail;
secondToLast -> next = nullptr;
tail = secondToLast;
}
return true;
}
void LinkedList::printAllNodes() const {
cout << "printing list: " << endl;
Node* current = head;
if (head!=nullptr) {
cout << "head node is: " << head->data << endl;
while(current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
else
cout << "head is null" << endl;
if (tail!=nullptr)
cout << "tail node is: " << tail->data << endl;
else
cout << "tail is null" << endl;
cout << endl;
}
int main(int argc, const char * argv[]) {
LinkedList myList;
myList.insertAtFront(2);
myList.insertAtFront(-5);
myList.insertAtFront(0);
myList.printAllNodes();
cout << "testing remove at front " << endl;
cout << myList.removeAtFront() << endl;
myList.printAllNodes();
cout << "testing remove at end " << endl;
cout << myList.removeAtEnd() << endl;
myList.printAllNodes();
cout << "testing insertAtFront with length 1" << endl;
myList.insertAtFront(2);
myList.printAllNodes();
cout << "adding nodes again for testing " << endl;
myList.insertAtFront(-55);
myList.insertAtFront(4);
myList.insertAtFront(2);
myList.insertAtFront(-7);
myList.insertAtFront(3);
myList.insertAtFront(2);
myList.insertAtFront(6);
myList.insertAtFront(0);
myList.printAllNodes();
cout << "testing remove at end" << endl;
cout << myList.removeAtEnd() << endl;
cout << myList.removeAtEnd() << endl;
myList.printAllNodes();
cout << "testing insert at end" << endl;
myList.insertAtEnd(2);
myList.printAllNodes();
myList.insertAtEnd(4);
myList.printAllNodes();
myList.insertAtEnd(6);
myList.printAllNodes();
cout << "testing empty list" << endl;
LinkedList myEmptyList;
myEmptyList.printAllNodes();
cout << "testing empty list - remove at front" << endl;
cout << myEmptyList.removeAtFront() << endl;
myEmptyList.printAllNodes();
cout << "testing empty list - remove at end" << endl;
cout << myEmptyList.removeAtEnd() << endl;
myEmptyList.printAllNodes();
cout << "testing empty list - insertAtFront" << endl;
myEmptyList.insertAtFront(3);
myEmptyList.printAllNodes();
cout << "emptying list, then testing empty list - insert at end" << endl;
myEmptyList.removeAtFront(); // also testing this with length 1
myEmptyList.printAllNodes();
myEmptyList.insertAtEnd(6);
myEmptyList.printAllNodes();
cout << "emptying list, then testing empty list - insert at end with tail" << endl;
myEmptyList.removeAtEnd(); // also testing this with length 1
myEmptyList.printAllNodes();
myEmptyList.insertAtEnd(9);
myEmptyList.printAllNodes();
cout << "testing insertAtEnd with length 1" << endl;
myEmptyList.insertAtEnd(-1);
myEmptyList.printAllNodes();
myEmptyList.insertAtEnd(-2);
myEmptyList.printAllNodes();
cout << "resetting list to length 1" << endl;
cout << myEmptyList.removeAtEnd() << endl;
cout << "back to my list" << endl;
myList.printAllNodes();
cout << "copying my list via assignment" << endl;
LinkedList listB;
listB = myList;
cout << "making listB different from myList" << endl;
listB.insertAtEnd(4);
cout << "myList is now" << endl;
myList.printAllNodes();
cout << "listB is now" << endl;
listB.printAllNodes();
cout << "testing copy constructor with list > length 1" << endl;
LinkedList listC(listB);
listC.printAllNodes();
cout << "testing copy constructor with empty list" << endl;
LinkedList listD;
LinkedList listE(listD);
listE.printAllNodes();
cout << "testing copy constructor with length 1 list" << endl;
listE.insertAtEnd(5);
LinkedList listF(listE);
listF.printAllNodes();
cout << "testing assigning a list to itself" << endl;
listC = listC;
listC.printAllNodes();
return 0;
}
Method
Expected result
printAllNodes()
Uses the provided code; will be of use for debugging.
insertAtFront, insertAtEnd
When inserting a new node, its “deleted” member will need to be initialized to “false”. Makes use of the tail pointer to insertAtEnd. Updates necessary data members.
removeAtFront, removeAtEnd
Will simply mark the appropriate Node as deleted without deallocating space and without updating head or tail. Will update necessary data members.
cleanList()
Actually removes Nodes from heap memory.
operator=
Should copy over all the data literally, including the soft deleted Nodes. Edit: one way to do this is to simply make another pass through the lists with a pointer on each and update the deleted data member on the corresponding Node.
Explanation / Answer
updated LinkedList for lazy deletion : --------->>>>>>>
#include <iostream>
#define nullptr NULL
using namespace std;
struct Node {
int data;
bool deleted;
Node *next;
};
class LinkedList {
private:
Node* head;
Node* tail;
int numNodes;
int numNodesExisting;
void deleteAllNodes();
public:
LinkedList();
~LinkedList();
LinkedList& operator=(const LinkedList& rhs);
LinkedList(const LinkedList& listToCopy);
void cleanList();
void printAllNodes() const;
void insertAtFront(int data);
bool removeAtFront();
// demonstrating difference between having tail pointer or not
void insertAtEnd(int data);
bool removeAtEnd();
};
LinkedList::LinkedList() {
head = nullptr;
tail = nullptr;
numNodes = 0;
numNodesExisting = 0;
}
LinkedList::~LinkedList() {
cleanList();
}
void LinkedList::cleanList() {
Node* curr = head;
Node* tmp;
if (curr != nullptr) {
tmp = curr->next;
delete curr;
curr = tmp;
}
head = nullptr;
tail = nullptr;
}
void LinkedList::deleteAllNodes(){
Node* curr = head;
while(curr != NULL){
curr->deleted = true;
curr = curr->next;
}
numNodes = 0;
}
LinkedList& LinkedList::operator=(const LinkedList& rhs) {
if (head != rhs.head) {
cleanList();
numNodes = 0;
numNodesExisting = 0;
Node* rhsCurr = rhs.head;
while (rhsCurr != nullptr) {
insertAtEnd(rhsCurr->data);
tail->deleted = rhsCurr->deleted;
rhsCurr = rhsCurr -> next;
}
}
return *this;
}
LinkedList::LinkedList(const LinkedList& listToCopy) {
// deleteAllNodes is safe for empty lists
head = nullptr;
tail = nullptr;
*this = listToCopy;
}
void LinkedList::insertAtFront(int data) {
// adding tail functionality
bool firstNode = false;
if (head==nullptr)
firstNode = true;
Node* newNode = new Node;
newNode->data = data;
newNode->deleted = false;
newNode->next = head;
head = newNode;
if (firstNode)
tail = head;
numNodes++;
numNodesExisting++;
}
bool LinkedList::removeAtFront() {
if (head==nullptr)
return false;
head->deleted = true;
numNodes--;
return true;
}
// This method makes use of tail
void LinkedList::insertAtEnd(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = nullptr;
if (head==nullptr) // empty list case
head = newNode;
if (tail!=nullptr) //
tail->next = newNode;
tail = newNode;
numNodes++;
numNodesExisting++;
}
// This method makes use of tail
bool LinkedList::removeAtEnd() {
// not much difference; we still have to get the second to last node
if (head==nullptr) // empty
return false;
tail->deleted = true;
numNodes--;
return true;
}
void LinkedList::printAllNodes() const {
cout << "printing list: " << endl;
Node* current = head;
if (head!=nullptr) {
cout << "head node is: " << head->data << endl;
while(current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
else
cout << "head is null" << endl;
if (tail!=nullptr)
cout << "tail node is: " << tail->data << endl;
else
cout << "tail is null" << endl;
cout << endl;
}
int main(int argc, const char * argv[]) {
LinkedList myList;
myList.insertAtFront(2);
myList.insertAtFront(-5);
myList.insertAtFront(0);
myList.printAllNodes();
cout << "testing remove at front " << endl;
cout << myList.removeAtFront() << endl;
myList.printAllNodes();
cout << "testing remove at end " << endl;
cout << myList.removeAtEnd() << endl;
myList.printAllNodes();
cout << "testing insertAtFront with length 1" << endl;
myList.insertAtFront(2);
myList.printAllNodes();
cout << "adding nodes again for testing " << endl;
myList.insertAtFront(-55);
myList.insertAtFront(4);
myList.insertAtFront(2);
myList.insertAtFront(-7);
myList.insertAtFront(3);
myList.insertAtFront(2);
myList.insertAtFront(6);
myList.insertAtFront(0);
myList.printAllNodes();
cout << "testing remove at end" << endl;
cout << myList.removeAtEnd() << endl;
cout << myList.removeAtEnd() << endl;
myList.printAllNodes();
cout << "testing insert at end" << endl;
myList.insertAtEnd(2);
myList.printAllNodes();
myList.insertAtEnd(4);
myList.printAllNodes();
myList.insertAtEnd(6);
myList.printAllNodes();
cout << "testing empty list" << endl;
LinkedList myEmptyList;
myEmptyList.printAllNodes();
cout << "testing empty list - remove at front" << endl;
cout << myEmptyList.removeAtFront() << endl;
myEmptyList.printAllNodes();
cout << "testing empty list - remove at end" << endl;
cout << myEmptyList.removeAtEnd() << endl;
myEmptyList.printAllNodes();
cout << "testing empty list - insertAtFront" << endl;
myEmptyList.insertAtFront(3);
myEmptyList.printAllNodes();
cout << "emptying list, then testing empty list - insert at end" << endl;
myEmptyList.removeAtFront(); // also testing this with length 1
myEmptyList.printAllNodes();
myEmptyList.insertAtEnd(6);
myEmptyList.printAllNodes();
cout << "emptying list, then testing empty list - insert at end with tail" << endl;
myEmptyList.removeAtEnd(); // also testing this with length 1
myEmptyList.printAllNodes();
myEmptyList.insertAtEnd(9);
myEmptyList.printAllNodes();
cout << "testing insertAtEnd with length 1" << endl;
myEmptyList.insertAtEnd(-1);
myEmptyList.printAllNodes();
myEmptyList.insertAtEnd(-2);
myEmptyList.printAllNodes();
cout << "resetting list to length 1" << endl;
cout << myEmptyList.removeAtEnd() << endl;
cout << "back to my list" << endl;
myList.printAllNodes();
cout << "copying my list via assignment" << endl;
LinkedList listB;
listB = myList;
cout << "making listB different from myList" << endl;
listB.insertAtEnd(4);
cout << "myList is now" << endl;
myList.printAllNodes();
cout << "listB is now" << endl;
listB.printAllNodes();
cout << "testing copy constructor with list > length 1" << endl;
LinkedList listC(listB);
listC.printAllNodes();
cout << "testing copy constructor with empty list" << endl;
LinkedList listD;
LinkedList listE(listD);
listE.printAllNodes();
cout << "testing copy constructor with length 1 list" << endl;
listE.insertAtEnd(5);
LinkedList listF(listE);
listF.printAllNodes();
cout << "testing assigning a list to itself" << endl;
listC = listC;
listC.printAllNodes();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.