In the article Introduction
to Linked Lists, we introduced the concept of linked list, the example
program was programmed to be able to add and display the elements in the linked
list. In reality only addition of elements to the linked list is not enough
to take the most out of linked list; we should be able to do other operations
such as insertion, deletion of elements etc.
This article would teach you to do such operation (insertion, addition, deletion
etc).
The program itself is quite big and has enough comments so I won’t discuss
anything here; rather I leave it up to you to understand all the operations
yourself!
// -- Linked Lists --
// ------------------
// Example program to illustrate
// addition, insertion, deletion
// and display of nodes in the
// 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 insert(int, int);
void add(int);
void display(void);
void del(int);
void free();
void main(void)
{
int ch,pos,num;
while(ch!=5)
{
cout<<"1> Add";
cout<<"\n2> Insert";
cout<<"\n3> Delete";
cout<<"\n4> Display";
cout<<"\n5> Quit\n";
cin>>ch;
switch(ch)
{
case 1:
cout<<"enter element:";
cin>>num;
add(num);
break;
case 2:
cout<<"enter pos:";
cin>>pos;
cout<<"enter element:";
cin>>num;
insert(pos,num);
break;
case 3:
cout<<"enter element to be deleted:";
cin>>num;
del(num);
break;
case 4:
display();
break;
}
}
// free-up the allocated
// memory
free();
}
// --FUNCTION--
// this function takes two
// arguments, 'loc' is the
// number of elements after
// which the new element having
// value 'inf' has to be inserted
void insert(int loc,int inf)
{
node *temp;
node *temp_new;
int i;
// if invalid, return
if(loc<=0) return;
temp=start;
// skip to the desired
// location where the node
// is to be added
for(i=1;i<loc;i++)
{
temp=temp->link;
if(temp==NULL)
{
cout<<"NOT POSSIBLE!";
return;
}
}
// allocate new node
temp_new=new node;
temp_new->info=inf;
// make it point to the
// respective node
temp_new->link=temp->link;
// make the prev. node where
// the new node is added, to
// point at the new node
temp->link=temp_new;
}
// --FUNCTION--
// display all the data
// in the linked list
void display(void)
{
node *temp;
temp=start;
// traverse or process
// through each element
// and keep printing
// the information
cout<<"\nelements are...\n";
while(temp!=NULL)
{
cout<<temp->info<<endl;
temp=temp->link;
}
}
// --FUNCTION--
// adds node to the end
// of the linked list
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;
}
}
// --FUNCTION--
// takes the argument of the
// 'info' part of the node
// to be deleted
void del(int inf)
{
node *temp, *old;
temp=start;
// while list not empty
while(temp!=NULL)
{
// if match is found
if(temp->info==inf)
{
// if it is the
// first node
if(temp==start)
start=temp->link;
else
old->link=temp->link;
delete temp;
return;
}
else
{
// traverse through
// each node
old=temp;
temp=temp->link;
}
}
}
// --FUNCTION--
// free up the allocated memory
// used by the nodes of the
// linked list
void free()
{
// 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;
}
}
Good-Bye!
Related Articles: