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();
}

Leave a Reply