// CS 250 question 2- Fall, 2015 // Write a function to delete an item in a // d
ID: 3770642 • Letter: #
Question
// CS 250 question 2- Fall, 2015 // Write a function to delete an item in a // double linked list // NOTE: // A double linked list has two pointers in each node // - p points to the next node // - rp points to the previous node // To delete a node in a DOUBLE LINKED LIST both forward and reverse // pointers must be changed // Be CERTAIN to consider the SPECIAL CASE of deleting the first node, // since the parameter s must be changed (that is why it is passed // as an alias parameter) // Remember to return the deleted memory to the heap // YOU CAN ASSUME THAT THE ITEM IS IN THE DOUBLE LINKED LIST // The function should change pointers // NO CREDIT will be given for changing the data // You MUST match the output given below #include <iostream> using std::cout; using std::cin; using std::endl; using std::ostream; struct node { int data; node * p; // FORWARD LINK node * rp; // REVERSE LINK }; ostream & operator<<( ostream &, const node *); // Written by Instructor void addFront2( node * & start, int); // Written by Instructor void cleanUp2( node *); // Written by Instructor void deleteNode(node * & s, int itemToDelete); // WRITTEN BY STUDENT void q2() { cout << " QUESTION 2 STARTING**********" << endl; node * a; a = NULL; addFront2(a,400); addFront2(a,300); addFront2(a,200); addFront2(a,100); cout << "BEFORE a is " << a << endl << endl; deleteNode(a,300); cout << "AFTER deleting 300 a is " << a << endl << endl; deleteNode(a,100); cout << "AFTER deleting 100 a is " << a << endl << endl; deleteNode(a,400); cout << "AFTER deleting 400 a is " << a << endl << endl; deleteNode(a,200); cout << "AFTER deleting 200 a is " << a << endl << endl; cleanUp2(a); } void deleteNode(node * & s, int itemToDelete) // Student Writes this Function { // PRECONDITION: itemToDelete is in the Double Linked List return; } void addFront2( node * & start, int x) { node * t = new node; t->data = x; if( start != NULL ) { t->p = start; t->rp = NULL; start->rp = t; } else { t->p = NULL; t->rp = NULL; } start = t; } void cleanUp2( node * s) { node * walker, * prev; walker = s; while ( walker != NULL ) { prev = walker; walker = walker->p; delete prev; } } ostream & operator<<(ostream & w, const node * s) { const node * walker = s; const node * trailer = walker; w << "Forward Print " << endl << " "; if ( s==NULL) { w << "EMPTY LIST"; } else { while ( walker != NULL ) { w << walker->data << ' '; trailer = walker; walker = walker->p; } } w << endl << "Reverse Print " << endl << " "; if ( trailer == NULL ) { w << "EMPTY LIST"; return w; } while ( trailer != NULL) { w << trailer->data << ' '; trailer = trailer->rp; } return w; } /* BEFORE a is Forward Print 100 200 300 400 Reverse Print 400 300 200 100 AFTER deleting 300 a is Forward Print 100 200 400 Reverse Print 400 200 100 AFTER deleting 100 a is Forward Print 200 400 Reverse Print 400 200 AFTER deleting 400 a is Forward Print 200 Reverse Print 200 AFTER deleting 200 a is Forward Print EMPTY LIST Reverse Print EMPTY LIST Press any key to continue */
Explanation / Answer
// CS 250 question 2- Fall, 2015
// Write a function to delete an item in a
// double linked list
// NOTE:
// A double linked list has two pointers in each node
// - p points to the next node
// - rp points to the previous node
// To delete a node in a DOUBLE LINKED LIST both forward and reverse
// pointers must be changed
// Be CERTAIN to consider the SPECIAL CASE of deleting the first node,
// since the parameter s must be changed (that is why it is passed
// as an alias parameter)
// Remember to return the deleted memory to the heap
// YOU CAN ASSUME THAT THE ITEM IS IN THE DOUBLE LINKED LIST
// The function should change pointers
// NO CREDIT will be given for changing the data
// You MUST match the output given below
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ostream;
struct node {
int data;
node * p; // FORWARD LINK
node * rp; // REVERSE LINK
};
ostream & operator<<( ostream &, const node *); // Written by Instructor
void addFront2( node * & start, int); // Written by Instructor
void cleanUp2( node *); // Written by Instructor
void deleteNode(node * & s, int itemToDelete); // WRITTEN BY STUDENT
void q2()
{
cout << " QUESTION 2 STARTING**********" << endl;
node * a;
a = NULL;
addFront2(a,400);
addFront2(a,300);
addFront2(a,200);
addFront2(a,100);
cout << "BEFORE a is " << a << endl << endl;
deleteNode(a,300);
cout << "AFTER deleting 300 a is " << a << endl << endl;
deleteNode(a,100);
cout << "AFTER deleting 100 a is " << a << endl << endl;
deleteNode(a,400);
cout << "AFTER deleting 400 a is " << a << endl << endl;
deleteNode(a,200);
cout << "AFTER deleting 200 a is " << a << endl << endl;
cleanUp2(a);
}
void deleteNode(node * & s, int itemToDelete) // Student Writes this Function
{
// PRECONDITION: itemToDelete is in the Double Linked List
node *parent,*child;
parent = child = s;
while(child!=NULL)
{
if(child->data == itemToDelete)
{
if(child->rp ==NULL && child->p == NULL)
s = NULL;
else if(child->rp == NULL)
{
cout<<"Found at first ";
s = child->p;
s->rp = NULL;
}
else if(child->p == NULL)
parent->p = NULL;
else
{
cout<<"Found at middle ";
parent->p = child->p;
(child->p)->rp = child->rp;
}
delete child;
break;
}
parent = child;
child = child->p;
}
return;
}
void addFront2( node * & start, int x)
{
node * t = new node;
t->data = x;
if( start != NULL )
{
t->p = start;
t->rp = NULL;
start->rp = t;
}
else
{
t->p = NULL;
t->rp = NULL;
}
start = t;
}
void cleanUp2( node * s)
{
node * walker, * prev;
walker = s;
while ( walker != NULL )
{
prev = walker;
walker = walker->p;
delete prev;
}
}
ostream & operator<<(ostream & w, const node * s)
{
const node * walker = s;
const node * trailer = walker;
w << "Forward Print " << endl << " ";
if ( s==NULL)
{
w << "EMPTY LIST";
}
else
{
while ( walker != NULL )
{
w << walker->data << ' ';
trailer = walker;
walker = walker->p;
}
}
w << endl << "Reverse Print " << endl << " ";
if ( trailer == NULL )
{
w << "EMPTY LIST";
return w;
}
while ( trailer != NULL)
{
w << trailer->data << ' ';
trailer = trailer->rp;
}
return w;
}
int main()
{
q2();
return 1;
}
/*
BEFORE a is
Forward Print
100 200 300 400
Reverse Print
400 300 200 100
AFTER deleting 300 a is
Forward Print
100 200 400
Reverse Print
400 200 100
AFTER deleting 100 a is
Forward Print
200 400
Reverse Print
400 200
AFTER deleting 400 a is
Forward Print
200
Reverse Print
200
AFTER deleting 200 a is
Forward Print
EMPTY LIST
Reverse Print
EMPTY LIST
Press any key to continue
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.