Program to implement linked representation of Linear list using templates

#include<iostream.h>
#include<constream.h>
#include<stdlib.h>
template<class T>
class ChainNode
{
friend Chain<T>;
private:
T data;
ChainNode<T>*link;
};
template<class T>
class Chain
{
private:
ChainNode<T>*first; 
public:
Chain()
{
first=0;
}
~Chain();
int IsEmpty()const;
int Length()const;
int Find(int k,T&x);
int Search(const T&x);
void Delete(int k,T&x);
void Insert(int k,const T&x);
void Output();
};
template<class T>
Chain<T>::~Chain()
{
ChainNode<T>*next;
while(first)
{
next=first->link;
delete first;
first=next;
}
}
template<class T>
int Chain<T>::Length()const
{
ChainNode<T>*current=first;
int len=0;
while(current)
{
current=current->link;
len++;
}
return len;
}
template<class T>
int Chain<T>::Find(int k,T&x)
//set x to the kth element in the chain
//return 0 if no kth element, return 1 otherwise
{
if(k<1)
return 0;
ChainNode<T>*current=first;
int index=1; //index of current
while(index<k&&current)
{
current=current->link;
index++;
}
if(current&&x==current->data)
return 1;
else
return 0; //no kth element
}
template<class T>
int Chain<T>::Search(const T&x)
{
ChainNode<T>*current=first;
int index=1; //index of current
while(current&&current->data!=x)
{
current=current->link;
index++;
}
if(current)
{
return index;
}
else
return 0;
}
template<class T>
void Chain<T>::Delete(int k,T&x)
{
if(k<1||!first)
cout<<"out of bounds\n"; //no kth element
ChainNode<T>*p=first;
if(k==1) //p is already at k
first=first->link; //remove
else
{
ChainNode<T>*q=first;
for(int index=1;index<k-1&&q;index++)
{
q=q->link;
}
if(!q||!q->link)
cout<<"the element doesnot exist\n";
p=q->link;
q->link=p->link; //remove from linked list
//free node p
delete p;
}
 
}
template<class T>
void Chain<T>::Insert(int k,const T&x)
{
if(k<0)
cout<<"out of bounds\n"; //no kth element
//p will be eventually to kth node
ChainNode<T>*p=first;
for(int index=1;index<k&&p;index++)
p=p->link;
if(k>0&&!p)
cout<<"out of bounds\n"; //no kth element
ChainNode<T>*y=new ChainNode<T>;
y->data=x;
if(k)
{
//insert after p
y->link=p->link;
p->link=y;
}
else
{
y->link=first;
first=y;
}
}
template<class T>
void Chain<T>::Output()
{
ChainNode<T>*p=first;
while(p)
{
cout<<p->data<<"\t";
p=p->link;
}
}
 
 
void menu()
{
cout<<"\n MENU\n";
cout<<"1.Length\n";
cout<<"2.Find\n";
cout<<"3.Search\n";
cout<<"4.Delete\n";
cout<<"5.Insert\n";
cout<<"6.Output\n";
}
void main()
{
int choice;
int k,x,len,p;
clrscr();
Chain<int>obj;
do
{
menu();
cout<<"enter choice\n";
cin>>choice;
switch(choice)
{
case 1:
len=obj.Length();
if(len==0)
cout<<"List is empty\n";
else
cout<<"length of linkedlist is "<<len<<endl;
break;
case 2:
cout<<"enter k,x(position and value)\n";
cin>>k>>x;
p=obj.Find(k,x);
if(p==1)
cout<<"found"<<endl;
if(p==0)
cout<<"not found"<<endl;
break;
case 3:
cout<<"enter x(value)\n";
cin>>x;
p=obj.Search(x);
if(p)
cout<<"searching is sucessful and found at "<<p<<endl;
else
cout<<"searching not sucessful"<<endl;
break;
case 4:
cout<<"enter k,x(position and value)\n";
cin>>k>>x;
obj.Delete(k,x);
break;
case 5:
cout<<"enter k,x(index and value)\n";
cin>>k>>x;
obj.Insert(k,x);
break;
case 6:
cout<<"elements in the list are:\n\n";
obj.Output();
break;
default:
cout<<"invalid choice\n";
}
}
while(choice>=1&&choice<=6);
getch();
}