In the previous article Introduction
to Linked Lists, we introduced the basic concept of linked list. To
make the program (an the article) as simple as possible, we discussed only the
addition and display of nodes in the linked list although necessary we didn't’t
discussed the deletion of node in that article.
In this article we will be discussing about the deletion of nodes from linked
lists.
Deletion of node (elements) from a linked list
The node to be deleted can be represented by many ways but here we will be
representing it by its info. So if we have the following linked list
And we want to delete node1 then we will express it by its info part (i.e. 10).
The main theory behind deletion of nodes is pretty simple. We need to make
the link pointer of the node before the target node (to be deleted) to point
at the node after the target node. Suppose if we wish to delete node having
info as 10 from the above linked list then it will be accomplished as below:
Now since node1 is orphan and has no meaning, it can be deleted
to free-up memory as represented below:
The following example program illustrates all this. Keep reading
the comments to understand what is happening where!
// -- Linked Lists --
// ------------------
// Example program in C++
// to illustrate the most simple
// linked list
// NOTE: this program can do three
// operation [adding, deleting,
// and displaying] of data in a
// linked list
#include<iostream.h>
// node class, this will
// represent the nodes or elements
// of the linked list
class node
{
public:
int info;
node *link;
};
// declare global objects
node *start=NULL;
// function prototypes
void add(int inf);
void display(void);
void del(int);
void main(void)
{
int ch;
// input elements
while(ch!=0)
{
cout<<"enter element to be added:";
cout<<"\nenter 0 to stop...\n";
cin>>ch;
if(ch!=0) add(ch);
cout<<"\n\n";
}
ch=-1;
while(ch!=0)
{
cout<<"enter element to be deleted:";
cout<<"\nenter 0 to stop...\n";
cin>>ch;
if(ch!=0) del(ch);
cout<<"\n\n";
}
cout<<"elements are...\n";
display();
// below is a bit confusing
// part.
// here all the nodes that
// we have allocated are
// being freed up
node temp;
while(start!=NULL)
{
// store the next node
// to the one being deleted
temp=*start;
// delete the node
delete start;
// retrieve the next node
// to be deleted
start=temp.link;
}
}
void add(int inf)
{
node *temp1;
node *temp2;
// if the element to be added
// is the first element
if(start==NULL)
{
// allocate a new node
temp1=new node;
temp1->info=inf;
temp1->link=NULL;
// make start point at it
start=temp1;
}
// if not
else
{
temp1=start;
// find out the last element
while(temp1->link!=NULL)
temp1=temp1->link;
// allocate new node
temp2=new node;
temp2->info=inf;
temp2->link=NULL;
// make the last element
// of the list to point
// at the newly created node
temp1->link=temp2;
}
}
void display(void)
{
node *temp;
temp=start;
// traverse or process
// through each element
// and keep printing
// the information
while(temp!=NULL)
{
cout<<temp->info<<endl;
temp=temp->link;
}
}
// this function takes an
// argument which is the info
// of the node to be delted
void del(int num)
{
node *old;
node *target;
target=start;
while(target!=NULL)
{
// if node to be
// delted is found
if(target->info==num)
{
// if node to be deleted
// is the first node
// in the list
if(target==start)
start=target->link;
// if not
else
// then make the node
// prev. to the node
// to be deleted to
// point at the node
// which is after it
old->link=target->link;
// free-up the memory
delete(target);
return;
}
else
{
// traverse through
// each node
old=target;
target=target->link;
}
}
}
Related Articles: