Linked List Program

This is program on linear list with Link based representation:

#include<iostream>
using namespace std;
template<class T>
class llist;
template<class T>
class chainnode
{
  	friend class llist<T>;
  	private:
    	chainnode<T> *link;
    	T data;
};
template<class T>
class llist
{
	public:
	    	chainnode<T> *first;
	    	llist() 
		{
			first=0;
		}
    		~llist();
	    	bool isempty()
		{
			return first==0;
		}
		int length();
		bool find(int k, T &x);
		int search(T &x);
		void del(int k, T &x);
		void insert(int k, T &x);
		void display();
};
template<class T>
llist<T>::~llist()
{
	chainnode<T> *next;
	while(first)
	{
		next=first->link;
		delete first;
		first=next;
	}
}
template<class T>
int llist<T>::length()
{
	// llist <T> *current
	chainnode<T> *current=first;
	int len=0;
	while(current)
	{
		len++;
		current=current->link;
	}
	return len;
}
template<class T>
bool llist<T>::find(int k, T &x)
{
	if(k<1)
		return false;
	chainnode<T> *current=first;
	int index=1;
	while(index<k && current!=0)
	{
		current=current->link;
		index++;
	}
	if(current)
	{
		x=current->data;
		return true;
	}
	return false;
}
template<class T>
int llist<T>::search(T &x)
{
	chainnode<T> *current=first;
	int index=1;
	while(current && current->data!=x)
	{
		current=current->link;
		index++;
	}
	if(current)
		return index;
	return 0;
}
template<class T>
void llist<T>::insert(int k, T &x)
{
	if(k<0)
		cout<<"Limit crossed";
	chainnode<T> *p=first;
	for(int i=1;i<k && p ;i++)
		p=p->link;
	if(k>0&&!p)
		cout<<" Out of Boundary";
	chainnode<T> *y=new chainnode<T>;
	y->data=x;
	if(k)
	{
		y->link=p->link;
		p->link=y;
	}
	else
	{
		y->link=first;
		first=y;
	}
}
template<class T>
void llist<T>::del(int k, T &x)
{
	if(k<1|| !first)   cout<<"Limit crossed";
	chainnode<T> *p=first;
	if(k==1)
		first=first->link;
	else
	{
		chainnode<T> *q=first;
		for(int i=1;i<k-1 && q; i++)
			q=q->link;
		if(!q|| !q->link)
			cout<<"Limit crossed";
		p=q->link;
		q->link=p->link;
	}
	x=p->data;
	delete p;
}
template<class T>
void llist<T>::display()
{
	chainnode<T> *current=first;
	while(current)
	{
		cout<<current->data<<"\t";
		current=current->link;
	}
}
int main()
{
	llist<int> l;
	int x,s,j,p,a,k,n;
	cout<<"Insertion of elements"<<endl;
	cout<<"enter size:";
	cin>>n;
	cout<<"Enter elements";
	for(int i=0;i<n;i++)
	{
		cin>>x;
		l.insert(i,x);
	}
	l.display();
	cout<<"Element to be searched: ";
	cin>>k;
	cout<<"Element is at"<<l.search(k)<<endl;
	cout<<"finding an element"<<endl;
	cin>>s;
	if(l.find(s,k))
		cout<<"Element is:"<<k<<endl;
	else
		cout<<"Element not found";
	cout<<" Enter position of element to be deleted";
	cin>>a;
	l.del(a,p);
	cout<<"after deleting the elements are:";
	l.display();
	return 0;
}

Link-based representation

As discussed in previous posts linear list can be implemented using  LINK-BASED  representation.

Linked list :- In this each element is represented by a node. This node has two fields which are Data field and Link field. The data field is used to store data while link field is used to store the address of next or previous node.

Singly linked list :-In this  the link field store the address of the next node.The last node has NULL address since it has no node to link.

Doubly linked list :-In this their are two link fields in node of which one stores the address of next node and the another stores address of the previous node.The next link of last node has no node to link so it stores NULL address, similarly the previous link of  the first node has NULL address.

Circular linked list :-In this similar to doubly linked list two link fields are maintained but the next link of last node stores the address of first node and the previous link of first node stores the address of last node.