The following is the logic for deleting the whichever node you want
template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function
/*
case 1: to delete ith node change i-1th node link to (i+1)th node
case 2: to delete 1st node, change first pointer to 2nd node:
steps:
1. p points to 1st node
2. move first to 2nd node, so 1st node is logically deleted
3. copy 1st node data to x, already p is pointing to 1st node so copy 1st node data to x
4. delete 1st node
5. return data of the deleted node
case 3: to delete last node, store NULL last but one node link field.
steps:
1. store NULL last but one node link filed
2. copy last node data to x
3. delete last node
4. return the data of the deleted node
case 4: if LL contains only one node, reinitialise first=NULL, after deletion of single node
*/
//deletion AT ITH NODE in the sll
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
template<class T>
class sll;
template<class T>
class node
{
private:
T data;
node<T>* link;
friend class sll<T>;
};
template <class T>
class sll
{
private:
node<T> * first;
public:
//Mem.Fun declarations
sll();
~sll();
int isempty();
void display();
int length();
void append(node<T> *k);
void create();
T del(int i);
};
//Member Functions defination
template<class T>
sll<T>::sll()
{
first=NULL;//first points to no where,it is an empty node
}
template<class T>
int sll<T>::isempty()
{
return(first==NULL);//return true when linked list is empty and false otherwise
}
template<class T>
void sll<T>::display()
{
node<T>* p;//p is pointer to a node
if(isempty())
cout<<"Linked List is empty\n";
else
{
cout<<"Linked list is as follows\n";
p=first;
while(p!=NULL)
{
cout<<p->data<<"\t"<<p->link<<"\n";
p=p->link;
}
}//end of else
}//end of display()
//finding lengh of nodes
template<class T>
int sll<T>::length()
{
node<T> *p=first;
int ctr=0;
while(p!=NULL)
{
ctr++;
p=p->link;
}
return(ctr);
}//end of length()
template<class T>
void sll<T>::append(node<T> *k)
{
node<T> *last;
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)//keep moving last pointer until last node is reached
{
last=last->link;
}
last->link=k;//attach last node and new node k
}
}
template <class T>
void sll<T>::create()
{
T x;
node<T> *k;
first=NULL;
cout<<"enter values terminated by -1 or !\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new node<T>;
k->data=x;
append(k);
cin>>x;
}
}//end of create()
//deletion of the ith node which ever node you want
template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function
void main()
{
sll<int> a;//creating object a, d.c is called
int x,i;
clrscr();
a.create();
cout<<"enter which position you want to delete(ith node)\n";
cin>>i;
x=a.del(i);
if(x= =-1)
cout<<"Non existing node\n";
else
cout<<"deleted value is \t"<<x<<"\n";
cout<<"after deleting ith node \n";
a.display();
getch();
}
template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function
/*
case 1: to delete ith node change i-1th node link to (i+1)th node
case 2: to delete 1st node, change first pointer to 2nd node:
steps:
1. p points to 1st node
2. move first to 2nd node, so 1st node is logically deleted
3. copy 1st node data to x, already p is pointing to 1st node so copy 1st node data to x
4. delete 1st node
5. return data of the deleted node
case 3: to delete last node, store NULL last but one node link field.
steps:
1. store NULL last but one node link filed
2. copy last node data to x
3. delete last node
4. return the data of the deleted node
case 4: if LL contains only one node, reinitialise first=NULL, after deletion of single node
*/
//deletion AT ITH NODE in the sll
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
template<class T>
class sll;
template<class T>
class node
{
private:
T data;
node<T>* link;
friend class sll<T>;
};
template <class T>
class sll
{
private:
node<T> * first;
public:
//Mem.Fun declarations
sll();
~sll();
int isempty();
void display();
int length();
void append(node<T> *k);
void create();
T del(int i);
};
//Member Functions defination
template<class T>
sll<T>::sll()
{
first=NULL;//first points to no where,it is an empty node
}
template<class T>
int sll<T>::isempty()
{
return(first==NULL);//return true when linked list is empty and false otherwise
}
template<class T>
void sll<T>::display()
{
node<T>* p;//p is pointer to a node
if(isempty())
cout<<"Linked List is empty\n";
else
{
cout<<"Linked list is as follows\n";
p=first;
while(p!=NULL)
{
cout<<p->data<<"\t"<<p->link<<"\n";
p=p->link;
}
}//end of else
}//end of display()
//finding lengh of nodes
template<class T>
int sll<T>::length()
{
node<T> *p=first;
int ctr=0;
while(p!=NULL)
{
ctr++;
p=p->link;
}
return(ctr);
}//end of length()
template<class T>
void sll<T>::append(node<T> *k)
{
node<T> *last;
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)//keep moving last pointer until last node is reached
{
last=last->link;
}
last->link=k;//attach last node and new node k
}
}
template <class T>
void sll<T>::create()
{
T x;
node<T> *k;
first=NULL;
cout<<"enter values terminated by -1 or !\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new node<T>;
k->data=x;
append(k);
cin>>x;
}
}//end of create()
//deletion of the ith node which ever node you want
template<class T>
T sll<T>::del(int i)
{
node<T> *p, *pres,*prev;
T x;
if(i<0||i>length())//i must be between 1 and length
{
return(-1);//ith node does not exist
}
else if(i==1)
{
p=first;//p points to first node
first=first->link;//move first to 2nd node so 1st node is logically deleted
x=p->data;//copy 1st node data to x
delete p;//delete 1st node
return(x);//return data of the deleted node
}
else//delete middle node or last node
{
pres=first;//present points to 1st node
for(int j=1;j<=i-1;j++)//searching for the ith node
{
prev=pres; //move prev ptr to pres ptr
pres=pres->link;//move pres ptr to next node
}
prev->link=pres->link;//change i-1 node link to i+1 th node
x=pres->data;
delete pres;
return(x);
}//end of else
}//end of del() function
void main()
{
sll<int> a;//creating object a, d.c is called
int x,i;
clrscr();
a.create();
cout<<"enter which position you want to delete(ith node)\n";
cin>>i;
x=a.del(i);
if(x= =-1)
cout<<"Non existing node\n";
else
cout<<"deleted value is \t"<<x<<"\n";
cout<<"after deleting ith node \n";
a.display();
getch();
}
No comments:
Post a Comment