Need help in modifying the insert function and remove function in the header fil
ID: 3702167 • Letter: N
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 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;
}
Explanation / Answer
Here is the code for the deleting a node in double linked list
void deleteteNode(struct Node** headRef, struct Node* delet)
{
if (*headRef == NULL || delet == NULL)
return;
if (*headRef == delet)
*headRef = delet->next;
if (delet->next != NULL)
delet->next->prev = delet->prev;
if (delet->prev != NULL)
delet->prev->next = delet->next;
free(delet);
}
void deleteteNodeAtGivenPos(struct Node** headRef, int n)
{
if (*headRef == NULL || n <= 0)
return;
struct Node* cur = *headRef;
int i;
for (int i = 1; cur != NULL && i < n; i++)
cur = cur->next;
if (cur == NULL)
return;
deleteteNode(headRef, cur);
}
Insert at front
void push(struct Node** head_ref, int newData)
{
Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = newData;
new_node->next = (*head_ref);
new_node->prev = NULL;
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
(*head_ref) = new_node;
}
Insert in between
void insertAfter(struct Node* prev_node, int newData)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));
new_node->data = newData;
new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
Insert at the end
void append(struct Node** head_ref, int newData)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref; /* used in step 5*/
new_node->data = newData;
new_node->next = NULL;
if (*head_ref == NULL)
{
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.