Question
Need help in modifying the insert function and remove function in the header file. I've included the header file where the modifications need to be
Need help in modifying the insert function and remove function in the header file. I've included the header file where the modifications need to be made and the main for testing the functions.
For the insert function the old start node should have the prev pointer changed from NULL to newNode and newNode prev pointer should be set to NULL. Not sure if I did this part correctly.
The remove function should find el using the find method. It can start with the result of find and update the pointers. Not sure how to implement this part.
I would appreciate any help with this.
#ifndef LINKEDLISTHEADER_H_INCLUDED
#define LINKEDLISTHEADER_H_INCLUDED
#include
using namespace std;
template
struct Node {
DT info;
Node
* next;
Node
* prev;
};
template
class DoublyLinkedList {
public:
DoublyLinkedList();
DoublyLinkedList(const DoublyLinkedList
& list1);
~DoublyLinkedList();
DoublyLinkedList
& operator = (const DoublyLinkedList
& list1);
void insert (DT el); // insert at the beginning of the list. resets curr
bool first (DT & el); // sets el to be the first element. sets curr = first. returns false if list is empty, otherwise returns true
bool getNext (DT & el); // sets el to curr->next. curr is updated. returns false if curr/curr->next is null, otherwise returns true
bool find (DT el); // returns if el is present in the list. curr is set to refer to that element.
bool retrieve (DT & el);// if el is present, sets el to be that element. curr is set to refer to that element.
bool replace (DT el); // replaces element referred to by curr with el. returns false if curr is null, otherwise returns true
bool remove (DT & el); // if el is present, then sets el to be that element and removes that element from the list. curr is set to NULL
bool isEmpty();
void makeEmpty(); // empty the list. also set curr to NULL
void display();
void displayReverse();
private:
Node
* start;
Node
* curr;
void deepCopy(const DoublyLinkedList
& list1); // need to ensure that curr is referring to the right node
};
template
DoublyLinkedList
::DoublyLinkedList() {
start = curr = NULL;
}
template
DoublyLinkedList
::DoublyLinkedList(const DoublyLinkedList
& list1) {
deepCopy(list1);
}
template
DoublyLinkedList
::~DoublyLinkedList() {
makeEmpty();
}
template
DoublyLinkedList
& DoublyLinkedList
::operator = (const DoublyLinkedList
& list1) {
if (this == & list1) return *this;
makeEmpty();
deepCopy(list1);
return *this;
}
template
void DoublyLinkedList
::deepCopy(const DoublyLinkedList
& list1) {
start = curr = NULL;
if (list1.start == NULL) return;
Node
* list1Curr = list1.start;
Node
* newNode = new Node
;
newNode->info = list1Curr->info;
newNode->prev = NULL;
start = newNode;
if (list1.curr == list1Curr) curr = newNode;
list1Curr = list1Curr->next;
while (list1Curr != NULL) {
Node
* nextNode = new Node
;
newNode->next = nextNode;
nextNode->info = list1Curr->info;
nextNode->prev = newNode;
if (list1.curr == list1Curr) curr = newNode;
list1Curr = list1Curr->next;
newNode = nextNode;
}
newNode->next = NULL;
}
// need to write the code
template
void DoublyLinkedList
::insert(DT el) {
Node
* newNode = new Node
;
newNode->info = el;
newNode->next = start;
start = newNode;
newNode->prev = NULL;
//curr = NULL;
return;
}
template
bool DoublyLinkedList
::first(DT & el) {
if (start == NULL) return false;
curr = start;
el = start->info;
return true;
}
template
bool DoublyLinkedList
::getNext(DT & el) {
if (curr == NULL) return false;
curr = curr->next;
if (curr == NULL) return false;
el = curr->info;
return true;
}
template
bool DoublyLinkedList
::find (DT el) {
DT item;
if (!first (item)) return false;
do {
if (item == el) return true;
} while (getNext(item));
return false;
}
template
bool DoublyLinkedList
::retrieve (DT & el) {
if (!find(el)) return false;
el = curr->info;
return true;
}
template
bool DoublyLinkedList
::replace (DT el) {
if (curr == NULL) return false;
curr->info = el;
return true;
}
// need to code in
template
bool DoublyLinkedList
::remove (DT & el) {
if (start == NULL) return false;
curr = NULL;
Node
* ptr = start;
if (ptr->info == el) {
el = ptr->info;
start = start->next;
delete ptr;
return true;
//return false;
}
}
template
bool DoublyLinkedList
::isEmpty () {
return (start == NULL);
}
template
void DoublyLinkedList
::makeEmpty () {
while (start != NULL) {
curr = start;
start = start->next;
delete curr;
}
curr = NULL;
}
template
void DoublyLinkedList
::display() {
Node
* currPtr = start;
while (currPtr != NULL) {
cout << currPtr->info << "->";
currPtr = currPtr->next;
}
cout << endl;
}
template
void DoublyLinkedList
::displayReverse() {
// first get the pointer to the last node in the list
Node
* currPtr = start;
if (currPtr == NULL) return;
while (currPtr->next != NULL) currPtr = currPtr->next;
// now loop starting from currPtr and looking at prev pointers
while (currPtr != NULL) {
cout << currPtr->info << "->";
currPtr = currPtr->prev;
}
cout << endl;
}
#endif // LINKEDLISTHEADER_H_INCLUDED
#include #include
#include "DoublyLinkedListHeader.h"
using namespace std;
void fn1(DoublyLinkedList l1) { string item = "s3"; l1.remove(item); l1.display(); l1.displayReverse(); }
int main() { DoublyLinkedList list1; // check insert works list1.insert("s1"); list1.insert("s2"); list1.display(); list1.displayReverse();
string item; list1.first(item); cout << item << endl; // check replace list1.replace("s3"); list1.display(); list1.displayReverse(); list1.insert("s4"); list1.insert("s5"); list1.display(); list1.displayReverse();
// check remove item = "s1"; list1.remove(item); list1.display(); list1.displayReverse();
// check =, makeEmpty DoublyLinkedList list2 = list1; list2.display(); list2.displayReverse();
list2.makeEmpty(); list1.display(); list1.displayReverse(); list2.display(); list2.displayReverse();
// check copy constructor fn1(list1); list1.display(); list1.displayReverse(); return 0; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started