TWO WAY LINKED LIST

A Two Way linked list is a type of link list which contains two part as first link part pointing towards next node while second link part is pointing toward previous node. As shown in picture –

PROGRAM TO INSERT AND DELETE AND TRAVERSING THE TWO WAY LL –  If you think it is a bit larger then go function wise. It will help you implementing program for 1 operation.

#include"iostream.h"
#include"conio.h"
using namespace std;
class list
{
	struct node
	{
		int info;
		node *flink;
		node *blink;
	}*p;
	public:
	list()
	{
		p=NULL;
	}
	int ins_beg(int x);
	int ins_end(int x);
	int del_beg();
	int del_end();
	int del_giv(int x);
	int disp();
};
/*INSERTION AT BEG FUNCTION BY C#ODE STUDIO*/
int list::ins_beg(int x)
{
	node *ptr;
	ptr=p;
	p=new node;
	p->info=x;
	p->blink=NULL;
	p->flink=ptr;
	if(ptr==NULL)
		cout<<"\nVALUE INSERTED";
	else
	{
		ptr->blink=p;
		cout<<"\nVALUE INSERTED";
	}
}
/*INSERTION AT END FUNCTION BY C#ODE STUDIO*/
int list::ins_end(int x)
{
	node *temp,*ptr;
	ptr=p;
	if(ptr==NULL)
		ins_beg(x);
	else
	{
		temp=new node;
		temp->flink=NULL;
		temp->info=x;
		while(ptr->flink!=NULL)
		{
			ptr=ptr->flink;
		}
		temp-> blink=ptr;
		ptr->flink=temp;
		cout<<"\nVALUE INSERTED";
	}
}
/*DELETION AT BEG FUNCTION BY C#ODE STUDIO*/
int list::del_beg()
{
	node *ptr,*temp;
	ptr=p;
	if(ptr==NULL)
		cout<<"\nUNDERFLOW, EXITING...";
	else
	{
		if(ptr->flink==NULL && ptr->blink==NULL)
			ptr=NULL;
		else
		{
			temp=ptr->flink;
			p=ptr->flink;
			temp->blink=NULL;
			ptr->flink=NULL;
		}
	}
	cout<<"\nVALUE DELETED";
} 
/*DELETION AT END FUNCTION BY C#ODE STUDIO*/
int list::del_end()
{
	node *ptr,*temp;
	ptr=p;
	if(ptr==NULL)
		cout<<"\nUNDERFLOW ";
	else
		if(ptr->flink==NULL && ptr->blink==NULL)
			ptr=NULL;
		else
		{
			while(ptr->flink!=NULL)
			{
				temp=ptr;
				ptr=ptr->flink;
			}
			temp->flink=NULL;
			ptr->blink=NULL;
		}
	cout<<"\nVALUE DELETED";
}
/*DELETION OF VALUE FUNCTION BY C#ODE STUDIO*/
int list::del_giv(int x)
{
	node *ptr,*temp1,*temp2;
	ptr=p;
	temp1=NULL;
	temp2=NULL;
	if(ptr==NULL)
		cout<<"\nUNDERFLOW OCCURS : NO DATA";
	else
	{
		while(ptr->flink!=NULL && ptr->info!=x)
		{
			temp1=ptr;
			ptr=ptr->flink;
			temp2=ptr->flink;
		}
		if(ptr->flink==NULL && ptr->blink==NULL)
			ptr=NULL;
		else
			if(ptr->flink==NULL && ptr->blink!=NULL)
			{
				temp1->flink=NULL;
				ptr->blink=NULL;
			}
			else
			{
				temp1->flink=temp2;
				temp2->blink=temp1;
				ptr->flink=NULL;
				ptr->blink=NULL;
			}
		cout<<"\nVALUE DELETED = "<<x;	
	}
}
/*DISPLAY FUNCTION BY C#ODE STUDIO*/
int list::disp()
{
	node *ptr;
	ptr=p;
	cout<<"START => ";
	while(ptr!=NULL)
	{
		cout<<ptr->info<<" => ";
		ptr=ptr->flink;
	}
	cout<<" NULL ";
}
/*MAIN FUNCTION BY C#ODE STUDIO*/
int main()
{
	list l;
	int num,choice,i=1;
	cout<<"\nPROGRAM OF TWO WAY LINKED LIST : READ AND MAKE CHOICE"<<endl<<endl;
	while(i!=0)
	{
		cout<<"\n\t1:INSERTION AT BEG"
			<<"\n\t2:INSERTION AT END"
			<<"\n\t3:DELETION FROM BEG"
			<<"\n\t4:DELETION FROM END"
			<<"\n\t5:DELETE AN ELEMENT"
			<<"\n\t6:DISPLAY"<<endl;
		cout<<"\nENTER YOUR CHOICE : ";
		cin>>choice;
		switch(choice)
		{
			case 1: cout<<"\nENTER NUMBER : ";
					cin>>num;
					l.ins_beg(num);
					break;
			case 2: cout<<"\nENTER NUMBER : ";
					cin>>num;
					l.ins_end(num);
					break;
			case 3: l.del_beg();
					break;
			case 4: l.del_end();
					break;
			case 5: cout<<"\nENTER NUMBER : ";
					cin>>num;
					l.del_giv(num);
					break;
			case 6: l.disp();
					break;
			default: cout<<"\nWRONG CHOICE : MAKE CHOICE AGAIN";
		}
		cout<<"\n\n\tPRESS 1:CONTINUE AND 0:EXIT ::: ";
		cin>>i;
	}
	cout<<"\nPROGRAMMING @ C#ODE STUDIO";
	getch();
} 

OUTPUT –
Will be long. So click on image to see output.

CIRCULAR LINKED LIST

A circular linked list is the link list in which the last node points to header node,
Manipulation of all the nodes are same as we do in the previous linked list.
Go through image to understand.

#include"conio.h"
#include"iostream"
using namespace std;
class list
{
	struct node
	{
		int info;
		node *link;
	}*p;
	public:
		list()
		{
			p=new node;
			p->info=0;
			p->link=p;
		}
		int insend(int x);
		int insbeg(int x);
		int headins(int x);
		int sumofele();
		int maxofele();
		int disp();
};
int list::maxofele()
{
	node *ptr;
	ptr=p->link;
	int max_ele=ptr->info;
	while(ptr!=p)
	{
		if(ptr->info > max_ele)
			max_ele=ptr->info;
		ptr=ptr->link;
	}
	p->info=max_ele;
	disp();
}
int list::sumofele()
{
	node *ptr;
	int sum=0;
	ptr=p->link;
	while(ptr!=p)
	{
		sum=sum+ptr->info;
		ptr=ptr->link;
	}
	p->info=sum;
	disp();
}
int list::insbeg(int x)
{
	node *ptr,*temp;
	ptr=p->link;
	temp=new node;
	temp->info=x;
	temp->link=ptr;
	p->link=temp;
	cout<<"\nITEM INSERTED AT BEGINING"<<endl;
	disp();
}
int list::insend(int x)
{
	if(p->link==p)
	{
		insbeg(x);
	}
	else
	{
		node *ptr,*t;
		ptr=p->link;
		while(ptr->link!=p)
			ptr=ptr->link;
		t=new node;
		t->info=x;
		t->link=ptr->link;
		ptr->link=t;
		cout<<"\nITEM INSERTED AT LIST"<<endl;
		disp();
	}	
}
int list::disp()
{
	node *ptr;
	ptr=p;
	cout<<"Values => Start => Header = ";
	do
	{
		cout<<ptr->info<<" => ";
		ptr=ptr->link;
	}while(ptr!=p);
	cout<<"NULL"<<endl<<endl;
}
int main()
{
	list l;
	int n=1,num,choice;
	while(n!=0)
	{
		cout<<"\n1:INSERT AT END"
			<<"\n2:INSERT AT BEG"
			<<"\n3:SUM OF ELEMENTS"
			<<"\n4:MAX OF ELEMENTS"
			<<"\n5:DISPLAY"<<endl;
		cout<<"\nINSERT CHOICE :";
		cin>>choice;
		switch(choice)
		{
			case 1: cout<<"\nINSERT VALUE : ";
					cin>>num;
					l.insend(num);
					break;
			case 2: cout<<"\nINSERT VALUE : ";
					cin>>num;
					l.insbeg(num);
					break;
			case 3: l.sumofele();
					break;
			case 4: l.maxofele();
					break;
			case 5: l.disp();
					break;
			default: cout<<"\nENTER CORRECT CHOICE ";
		}
		cout<<"\n1:CONTINUE, 0:EXIT :: ";
		cin>>n;
	}
	cout<<"\nPROGRAMMING @ C#ODE STUDIO";
	getch();
	return 0;
}

Output –

HEADER LINKED LIST

Header linked list are the linked list with one node attached with start pointer. We doesnt have to consider that node in treversal. The next nodes of header node will contain elements and the header node will contain any special information related to all the element nodes.

Algorithm –

1: SET PTR=LINK [START]
2: REPEAT 3,4 WHILE PTR != NULL
3:   //HERE WE CAN APPLY OPERATIONS//
4:  PTR= LINK [PTR]
5: EXIT

Program –
Below, program contains insertion at end and beginning of header link list and display function along with two function sumofelement & maxofelement to store there corresponding data to header node.

#include"conio.h"
#include"iostream"
using namespace std;
class list
{
	struct node
	{
		int info;
		node *link;
	}*p,*start;
	public:
		list()
		{
			p=new node;
			p->info=0;
			p->link=NULL;
		}
		int insend(int x);
		int insbeg(int x);
		int headins(int x);
		int sumofele();
		int maxofele();
		int disp();
};
int list::maxofele()
{
	node *ptr;
	ptr=p->link;
	int max_ele=ptr->info;
	while(ptr!=NULL)
	{
		if(ptr->info > max_ele)
			max_ele=ptr->info;
		ptr=ptr->link;
	}
	p->info=max_ele;
	disp();
}
int list::sumofele()
{
	node *ptr;
	int sum=0;
	ptr=p->link;
	while(ptr!=NULL)
	{
		sum=sum+ptr->info;
		ptr=ptr->link;
	}
	p->info=sum;
	disp();
}
int list::insbeg(int x)
{
	node *ptr,*temp;
	ptr=p->link;
	temp=new node;
	temp->info=x;
	temp->link=ptr;
	p->link=temp;
	cout<<"\nITEM INSERTED AT BEGINING"<<endl;
	disp();
}
int list::insend(int x)
{
	if(p==NULL)
	{
		insbeg(x);
	}
	else
	{
		node *ptr,*t;
		ptr=p->link;
		while(ptr->link!=NULL)
			ptr=ptr->link;
		t=new node;
		t->info=x;
		t->link=ptr->link;
		ptr->link=t;
		cout<<"\nITEM INSERTED AT LIST"<<endl;
		disp();
	}	
}
int list::disp()
{
	node *ptr;
	ptr=p;
	cout<<"Values => Start => Header = ";
	while(ptr!=NULL)
	{
		cout<<ptr->info<<" => ";
		ptr=ptr->link;
	}
	cout<<"NULL"<<endl<<endl;
}
int main()
{
	list l;
	int n=1,num,choice;
	while(n!=0)
	{
		cout<<"\n1:INSERT AT END"
			<<"\n2:INSERT AT BEG"
			<<"\n3:SUM OF ELEMENTS"
			<<"\n4:MAX OF ELEMENTS"
			<<"\n5:DISPLAY"<<endl;
		cout<<"\nINSERT CHOICE :";
		cin>>choice;
		switch(choice)
		{
			case 1: cout<<"\nINSERT VALUE : ";
					cin>>num;
					l.insend(num);
					break;
			case 2: cout<<"\nINSERT VALUE : ";
					cin>>num;
					l.insbeg(num);
					break;
			case 3: l.sumofele();
					break;
			case 4: l.maxofele();
					break;
			case 5: l.disp();
					break;
			default: cout<<"\nENTER CORRECT CHOICE ";
		}
		cout<<"\n1:CONTINUE, 0:EXIT :: ";
		cin>>n;
	}
	cout<<"\nPROGRAMMING @ C#ODE STUDIO";
	getch();
	return 0;
}

Output –