Algorithm : Set Operations


Let us consider two sorted sets pointed by heders p1 and p2 respectively.
In real, each element of a set is a node of a single linked list.We will need to
store their union set,intersection set and difference set in a linked list 
pointed by header node p3.


Intersection(p1, p2,p3)
{
  m1=p1->link               //m1 points to the 1st element of 1st set
  while(m1≠NULL)            //until 1st set becomes empty
  {
    m2=p2->link             //m2 points to the 1st element of 2nd set 
    while(m2≠NULL)          //until 2nd set becomes empty
    {
      if(m1->ele=m2->ele)
      {
	  t=getnode()
	  t->ele=m1->ele
	  if(p3->link=NULL)
	  {
	   p3->link=t
	   m3=t
	  }
	  else
	  {
	   m3->link=m1
	   m3=m3->link      //m3 moves to next node
	  }
      }
      m2=m2->link             //m2 moves to next node
    }
   m1=m1->link                //m1 moves to next node
  }
  show(p3)
}


union(p1, p2,p3)
{
  m1=p1->link               //m1 points to the 1st element of 1st set
  while(m1≠NULL)            //until 1st set becomes empty
  {
    t=getnode()
    t->ele=m1->ele
    if(p3->link=NULL)
    {
      p3->link=t
      trav=t
    }
    else
     {
       trav->link=t
       trav=trav->link
     }
     m1=m1->link               //m1 moves to next node
  }

   m2=p2->link             //m2 points to the 1st element of 2nd set
  while(m2≠NULL)           //until 2nd set becomes empty
  {
   ptr=p3->link            //ptr points to the 1st element of p3
   while(ptr≠NULL)
   {
     if(ptr->ele=m2->ele)    //if element of 1st set & 2nd set is 
     {                         equal then control breaks from this           
       Break                   loop
     }
     save2=ptr
     ptr=ptr->link
   }
   if(ptr=NULL)
   {
     t=getnode()
     t->ele=m2->ele
     save2->link=t
     t->link=ptr
   }
   m2=m2->link               //m2 moves to next node
  }
  show(p3)
}


Difference(p1, p2,p3)
{  
  m1=p1->;link             //m1 points to the 1st element of 1st set
  while(m1≠NULL)          //until 1st set becomes empty
  {
    m2=p2->link           //m2 points to the 1st element of 2nd set
    while(m2≠NULL)        //until 2nd set becomes empty
    {
      if(m1->ele=m2->ele)
      {
	  break
      }
      else if(m1->ele≠m2->ele)
      {
       m2=m2->link               //m2 moves to next node
      }
    }
    if(m2=NULL)
    {
     if(p3->link=NULL)
     {
      p3->link=m1
      trav=m1
     }
     else
     {
       trav->link=m1
       trav=trav->link
     }
    }
    m1=m1->link                 //m1 moves to next node
  }
    show(p3)
}


Here we use two functions show(header) and getnode().
The 1st one shows the elements in the linked list pointed by header.
The 2nd one creates a node and return it's address to the pointer variable.


C Program For Set Operation

Source Code:


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<alloc.h>

struct node
{
 int ele;
 struct node *link;
};


struct node * getnode()
{
 struct node *t;
 t=(struct node *)malloc(sizeof(struct node));
 t->link=NULL;
 return t;
}

void create(struct node *P)
{
  struct node *trav,*t;
  int i,n,el;

  printf("\nEnter number of elements:");
  scanf("%d",&n);
  for(i=1;i<=n;i++)
   {
     t=getnode();
     printf("\nEnter element-%d :",i);
     scanf("%d",&el);
     t->ele=el;
     if(P->link==NULL)
      {
	 P->link=t;
	 trav=P->link;
      }
     else
      {
	 trav->link=t;
	 trav=t;
      }
   }
}
void show(struct node *P)
{
  struct node *trav;
  if(P->link==NULL)
   {
     printf("\nSet not created.");
   }
  else
   {
     printf("\nThe set is: { ");
     trav=P->link;
     while(trav!=NULL)
      {
	printf(" %d,",trav->ele);
	trav=trav->link;
      }
      printf("}");
   }
}


void uni_on(struct node *p1,struct node *p2)
{
  struct node *p3,*m1,*m2,*trav,*save1,*save2,*ptr,*t;
  p3=getnode();
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    t=getnode();
    t->ele=m1->ele;
    if(p3->link==NULL)
    {
      p3->link=t;
      trav=t;
    }
    else
     {
       trav->link=t;
       trav=trav->link;
     }
     m1=m1->link;
  }

  m2=p2->link;
  while(m2!=NULL)
  {
   ptr=p3->link;
   while(ptr!=NULL)
   {
     if(ptr->ele==m2->ele)
     {
       break;
     }
     save2=ptr;
     ptr=ptr->link;
   }
   if(ptr==NULL)
   {
     t=getnode();
     t->ele=m2->ele;
     save2->link=t;
     t->link=ptr;
   }
   m2=m2->link;
  }
  show(p3);
}

void intersection(struct node *p1,struct node *p2)
{
  struct node *p3,*trav,*m1,*m2,*t,*m3;
  p3=getnode();
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    m2=p2->link;
    while(m2!=NULL)
    {
      if(m1->ele==m2->ele)
      {
	t=getnode();
	t->ele=m1->ele;
	if(p3->link==NULL)
	{
	  p3->link=t;
	  m3=t;
	}
	else
	{
	  m3->link=m1;
	  m3=m3->link;
	}
      }
      m2=m2->link;
    }
   m1=m1->link;
  }
  show(p3);
}

void difference(struct node *p1,struct node *p2)
{
  struct node *p3,*trav,*m1,*m2,*t;
  p3=getnode();
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    m2=p2->link;
    while(m2!=NULL)
    {
      if(m1->ele==m2->ele)
      {
	break;
      }
      else if(m1->ele!=m2->ele)
      {
       m2=m2->link;
      }
    }
    if(m2==NULL)
    {
     t=getnode();
     t->ele=m1->ele;
     if(p3->link==NULL)
     {
      p3->link=t;
      trav=t;
     }
     else
     {
       trav->link=t;
       trav=trav->link;
     }
    }
    m1=m1->link;
  }
    show(p3);
}



main()
{
  int ch,ch1,x,ch4,ch3;
  struct node *p1,*p2;
  p1=getnode();
  p2=getnode();

  while(1)
  {
    printf("\n@ Set operations:");
    printf("\n\t1.Creation.\n\t2.Union\n\t3.Tntersection\n\t4.Difference.\n\t5.Display\n\t6.Exit");
    printf("\nEnter your choice:");
    scanf("%d",&ch);
    switch(ch)
     {
       case 1:printf("\nCreate=>1.set-1 2.set-2");
	      printf("\nEnter your choice:");
	      scanf("%d",&ch4);
	      switch(ch4)
	      {
		case 1:
		       create(p1);
		       break;
		case 2:
		       create(p2);
		       break;
	      }
	      break;
       case 2:
	      uni_on(p1,p2);
	      break;

       case 3:
	      intersection(p1,p2);

	      break;
       case 4:
	      difference(p1,p2);

	      break;
       case 5:
	      printf("\nshow=>1.set-1 2.set-2");
	      printf("\nEnter your choice:");
	      scanf("%d",&ch3);
	      switch(ch3)
	      {
		case 1:

		       show(p1);
		       break;
		case 2:

		       show(p2);
		       break;
	      }
	      break;
       case 6:
	      exit(0);
     }
  }
}

Algorithm : Single Linked-List Operation

 Let us consider a single linked list pointed by header.We have to
 Perform insertion,deletion,searching,traversal,sorting,inversion
 And merging operations in this linked list.

Insert_begining(header,item)
{
  In this case We have to insert an element item at the beginning of  
  the list such that it become the first node.

  t=getnode()           //getnode is a function which create a
                         new node(node has two part i) data ii) link
                         of the linked list and return the address
                         of node.
 t->data=item
 if(header->link=NULL)
 {
  header->link=t
 }
 else
 {
  t->link=header->link
  header->link=t
 }
}



Insert_end(header,item)
{
 In this case we want to insert an element item at the end of 
 the list such that it become the last node.

 t=getnode()
 t->data=item
 if(header->link=NULL)
 {
  header->link=t
 }
 else
 {
   trav=header->link              //trav points to 1st node
   while(trav->link≠NULL)        //until trav reaches the last node  
   {
    trav=trav->link               //trav moves to next node
   }
   trav->link=t                   //the node,t is added at the last 
 }                                  position of the list
}



Insert_any(header,key,item)
{
  In this case we have toinsert an element,item in this list after a
  node whose data is key. 

  t=getnode()
  t->data=item
  trav=header->link                    //trav points to 1st node
  while(trav->data≠key and trav≠NULL)  //until key not found and
  {                                      the trav becomes NULL
    trav=trav->link                    //trav moves to next node
  }
  if(trav=NULL)                       //checks if key not found
  {
   Print  "Insertion impossible"
  }
  else
  {
   t->link=trav->link        //t points to the node just after trav
   trav->link=t              //trav points to t
  }
}


Traversal(header)
{
 trav=header->link
 if(trav=NULL)
    print  "List empty"
 else
 {
  while(trav!=NULL)            //until trav becomes NULL
  {
   Print  "trav->data”
   trav=trav->link             //trav moves to next node
  }
 }
}


Delete_begining(header)
{
 In this case we have to delete the 1st node of the list.

 if(header->link=NULL)
   print  "List empty"
 else
 {
   x=header->link            //x points to the 1st node in the list
   header->link=x->link      //the link part of header points to the 
 }                             2nd node
}




Delete_end(header)
{
 In this case we have to delete the last node of the list.
 if(header->link=NULL)
   print  "List empty"
 else
 {
   ptr=header->link               //ptr points to the 1st node in the list 
   if(ptr->link=NULL)             //checks if there is only one node 
     header->link=NULL            present in the list
   else
   {
     trav=ptr->link               //trav points to the 2nd node
     while(trav->link≠NULL)       //until trav reaches the last node
     {
      ptr=trav                    //ptr points to trav
      trav=trav->link             //trav moves to next node
     }
     ptr->link=NULL               //the link part of the node just before 
   }                              the last node is made NULL
 }
}


Delete_any(header,key)
{
  In this case we have to delete a node from the list containing the  
  value,key.

  if(header->link=NULL)
    print  "List empty"
  else
  {
   ptr=header                //ptr points to header node
   trav=ptr->link           //trav points to the 1st node in the list
   while(trav->data≠key and trav≠NULL)    //until the key not found
   {                                        or trav becomes NULL                 
     ptr=trav                             //ptr points to trav  
     trav=trav->link                      //trav moves to next node         
   }
   if(trav=NULL)                       //checks if the key not found
   {
    Print  "Deletion impossible"
   }
   else
   {
     ptr->link=trav->link    //the link part of ptr points to the
   }                           node just after trav
  }
}

Search(header,item)
{
  In this case we have to search a node in the list containing the
  value,item.

  if(header->link=NULL)
    Print  “List empty"
  else
  {
    trav=header->link            //trav points to the 1st node
    j=0
    while(trav≠NULL)             //until trav becomes NULL   
    {
      if(trav->data=item)        //checks if the item is found 
      {
	  Print  "Element found in position j”
	  Return       
      }
      trav=trav->link         //if item not found,trav moves to  
      j=j+1                    next node
    }
    if(trav=NULL)            
      Print  "Element not found"
  }
}



Inversion(header)
{
  In this case we have to inverse the linked list such that the
  header node of the list points to the last node.

  if(header->link=NULL)
    printf  "List empty"
  else
  {
    p=NULL
    q=header->link         //q points to the 1st node
    while(q≠NULL)          //until q becomes NULL   
    { 
      r=q->link            //r points to the node just after q
      q->link=p
      p=q                  //p points to q  
      q=r                  //q points to r      
    }
    header->link=p         //link part of header points to p
  }
}





Sorting(header)
{
  In this case we have to sort the nodes of the list accoeding to
  the value of the nodes in ascending or descending order. 

  if(header->link=NULL)
    Print  "List empty"
  else
  {
    for(ptr=header->link;ptr->link≠NULL;ptr=ptr->link)  
    {
      for(trav=ptr->link;trav≠NULL;trav=trav->link)
      {
	if(option=ascending)
	{
	  if(ptr->data>trav->data)
	  {
	    t=ptr->data
	    ptr->data=trav->data
	    trav->data=t
	  }
      }
       else if(option=descending)
       {
	   if(ptr->datadata)
	   {
	     t=ptr->data
	     ptr->data=trav->data
	     trav->data=t
	   }
       }
      }
    }
  }
}


Merge_unsorted(h1,h2)
{
  In this case we have to merge two unsorted linked lists pointed by 
  headers h1 and h2.

  trav=h1->link         //trav points to the 1st node of 1st list
  ptr=h2->link          //ptr points to the 1st node of 2nd list
  if(trav=NULL  &&  ptr=NULL)
     print  "Merging not possible"
  else
  {
    while(trav->link≠NULL)    //until trav reaches the last node
    {                           of 1st linked-list
      trav=trav->link         //trav moves to next node
    }
    trav->link=h2->link       //now trav points to the 1st node
  }                            of 2nd linked-list
}




Merge_sorted(h1, h2, h3)
{
 In this case we have to merge two linked lists in sorted order 
 pointed by headers h1 and h2.

 p1=h1->link                 //p1 points to the 1st node of 1st list
 p2=h2->link                 //p2 points to the 1st node of 2nd list   
 while(p1≠NULL && p2≠NULL)   
 {
   t=getnode()
   if(p1->datadata)
   {
     t->data=p1->data
     p1=p1->link            //p1 moves to next node
   }
   else
   {
     t->data=p2->data
     p2=p2->link            //p2 moves to next node 
   }
   if(h3->link=NULL)        
   {
    h3->link=t
    trav=t
   }
   else
   {
    trav->link=t
    trav=trav->link
   }
 }
   while(p1≠NULL)
   {
    t=getnode()
    t->data=p1->data
    p1=p1->link
    trav->link=t
    trav=trav->link
   }
   while(p2≠ NULL)
   {
    t=getnode()
    t->data=p2->data
    p2=p2->link
    trav->link=t
    trav=trav->link
   }

}


C Program For Single Linked-List Operation

Source Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct node
{
 int data;
 struct node *link;
};

struct node *header;

struct node * getnode()
{
 struct node *t;
 int item;
 t=(struct node *)malloc(sizeof(struct node));
 t->link=NULL;
 return t;
}

void traversal()
{
 struct node *trav;
 trav=header->link;
 if(trav==NULL)
    printf("\nList empty.");
 else
 {
 printf("\nLINK  LIST :\n\n");
 while(trav!=NULL)
 {
  printf("  %d",trav->data);
  trav=trav->link;
 }
 }
 printf("\n");
}

void insert_beg(int item)
{
 struct node *t;
 t=getnode();
 t->data=item;
 if(header->link==NULL)
 {
  header->link=t;
 }
 else
 {
  t->link=header->link;
  header->link=t;
 }
}

void insert_end(int item)
{
 struct node *trav,*t;
 t=getnode();
 t->data=item;
 if(header->link==NULL)
 {
  header->link=t;
 }
 else
 {
   trav=header->link;
   while(trav->link!=NULL)
   {
    trav=trav->link;
   }
   trav->link=t;
 }
}

void insert_any(int key,int item)
{
  struct node *trav,*t;
  t=getnode();
  t->data=item;
  trav=header->link;
  while(trav->data!=key && trav!=NULL)
  {
    trav=trav->link;
  }
  if(trav==NULL)
  {
   printf("\nInsertion impossible\n");
  }
  else
  {
   t->link=trav->link;
   trav->link=t;
  }
}

void delete_beg()
{
 struct node *x;
 if(header->link==NULL)
 {
   printf("\nList empty.\n");

 }
 else
 {
   x=header->link;
   header->link=x->link;

 }
}

void delete_end()
{
 struct node *trav,*ptr;
 if(header->link==NULL)
 {
   printf("\nList empty.\n");
 }
 else
 {
   ptr=header->link;
   if(ptr->link==NULL)
   {
     header->link=NULL;
   }
   else
   {
     trav=ptr->link;
     while(trav->link!=NULL)
     {
      ptr=trav;
      trav=trav->link;
     }
     ptr->link=NULL;
   }
 }
}

void delete_any(int key)
{
  struct node *trav,*ptr;
  if(header->link==NULL)
  {
   printf("\nList empty.\n");
  }
  else
  {
   ptr=header;
   trav=ptr->link;
   while(trav->data!=key && trav!=NULL)
   {
     ptr=trav;
     trav=trav->link;
   }
   if(trav==NULL)
   {
    printf("\nDeletion impossible.\n");
   }
   else
   {
     ptr->link=trav->link;
   }
  }
}

void search(int item)
{
  int j;
  struct node *trav;
  if(header->link==NULL)
  {
    printf("\nList empty");
  }
  else
  {
    trav=header->link;
    j=1;
    while(trav!=NULL)
    {
      if(trav->data==item)
      {
	printf("\nElement found in position=> %d",j);
	return;
      }
      trav=trav->link;
      j++;
    }
    if(trav==NULL)
    {
      printf("\nElement not found.");
    }
  }
}

void sorting(int s)
{
  struct node *trav,*ptr;
  int t;
  if(header->link==NULL)
  {
    printf("nList empty");
  }
  else
  {
    for(ptr=header->link;ptr->link!=NULL;ptr=ptr->link)
    {
      for(trav=ptr->link;trav!=NULL;trav=trav->link)
      {
	if(s==1)
	{
	if(ptr->data>trav->data)
	{
	  t=ptr->data;
	  ptr->data=trav->data;
	  trav->data=t;
	}
       }
       else if(s==2)
       {
	 if(ptr->datadata)
	{
	  t=ptr->data;
	  ptr->data=trav->data;
	  trav->data=t;
	}
       }
      }
    }
  }
}

void inversion()
{
  struct node *p,*q,*r;
  if(header->link==NULL)
  {
    printf("\nList empty");
  }
  else
  {
    p=NULL;
    q=header->link;
    while(q!=NULL)
    {
      r=q->link;
      q->link=p;
      p=q;
      q=r;
    }
    header->link=p;
    traversal();
  }
}

void merge_u(struct node *h1,struct node *h2)
{
  struct node *trav,*ptr;
  trav=h1->link;
  ptr=h2->link;
  if(trav==NULL  &&  ptr==NULL)
     printf("\nMerging not possible.");
  else
  {
    while(trav->link!=NULL)
    {
      trav=trav->link;
    }
    trav->link=h2->link;
  }
}

void  merge_sort(struct node *h1,struct node *h2,struct node *h3)
{
 struct node *p1,*p2,*trav,*t;
 p1=h1->link;
 p2=h2->link;
 h3->link=NULL;
 while(p1!=NULL && p2!=NULL)
 {
   t=getnode();
   if(p1->datadata)
   {
     t->data=p1->data;
     p1=p1->link;
   }
   else
   {
     t->data=p2->data;
     p2=p2->link;
   }
   if(h3->link==NULL)
   {
    h3->link=t;
    trav=t;
   }
   else
   {
    trav->link=t;
    trav=trav->link;
   }
 }
   while(p1!=NULL)
   {
    t=getnode();
    t->data=p1->data;
    p1=p1->link;
    trav->link=t;
    trav=trav->link;
   }
   while(p2!=NULL)
   {
    t=getnode();
    t->data=p2->data;
    p2=p2->link;
    trav->link=t;
    trav=trav->link;
   }

}

void main()
{
 int ch,ch1,ch2,item,key,ch3,s,ch4,ch5;
 struct node *h1,*h2,*h3;
 h1->link=NULL;
 h2->link=NULL;
 clrscr();
 while(1)
 {

   printf("\nLinked List Operations:");
   printf("\n1.Linked list-1\n2.Linked list-2\n3.Merging\n4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch4);
   switch(ch4)
   {
     case 1:
	    header=h1;
 while(1)
 {
 start :
 printf("\nLINKED LIST-1 OPERATION :");
 printf("\n1.Insertion  2.Deletion 3.Traversal 4.Search\n5.Sorting  6.Inversion  7.Exit from LL-1");
 printf("\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
	  printf("\nINSERTION:");
	  printf("\n1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch1);
	  switch(ch1)
	  {
	  case 1:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_beg(item);
		 break;
	  case 2:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_end(item);
		 break;
	  case 3:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 printf("\nEnter the key:");
		 scanf("%d",&key);
		 insert_any(key,item);
		 break;
	  case 4:
		 break;
	  }
	  goto start;
   case 2:
	  printf("\nDELETION:");
	  printf("\n1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch2);
	  switch(ch2)
	  {
	  case 1:
		 delete_beg();
		 break;
	  case 2:
		 delete_end();
		 break;
	  case 3:
		 printf("\nEnter the data of the node to be deleted:");
		 scanf("%d",&key);
		 delete_any(key);
		 break;
	  case 4:
		 break;
	  }
	  goto start;
   case 3:
	  traversal();
	  goto start;
   case 4:
	  printf("\nSEARCHING:");
	  printf("\nEnter the element you want to search:");
	  scanf("%d",&item);
	  search(item);
	  goto start;
   case 5:
	  printf("\nSORTING:");
	  printf("\nSorting-> 1.Ascending order 2.Decending order");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch3);
	  switch(ch3)
	  {
	    case 1:
		   s=1;
		   sorting(s);
		   traversal();
		   break;
	    case 2:
		   s=2;
		   sorting(s);
		   traversal();
		   break;
	  }
	  goto start;
   case 6:
	  printf("\nINVERSION:");
	  inversion();
	  goto start;
   case 7:
	  goto end;
  }
  end : break;
 }
 break;
 case 2:
	header=h2;
 while(1)
 {
 start2 :
 printf("\nLINKED LIST-2 OPERATION :");
 printf("\n1.Insertion  2.Deletion 3.Traversal 4.Search\n5.Sorting  6.Inversion  7.Exit from LL-2");
 printf("\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
	  printf("\nINSERTION:");
	  printf("\n1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch1);
	  switch(ch1)
	  {
	  case 1:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_beg(item);
		 break;
	  case 2:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_end(item);
		 break;
	  case 3:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 printf("\nEnter the key:");
		 scanf("%d",&key);
		 insert_any(key,item);
		 break;
	  case 4:
		 break;
	  }
	  goto start2;
   case 2:
	  printf("\nDELETION:");
	  printf("\n1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch2);
	  switch(ch2)
	  {
	  case 1:
		 delete_beg();
		 break;
	  case 2:
		 delete_end();
		 break;
	  case 3:
		 printf("\nEnter the data of the node to be deleted:");
		 scanf("%d",&key);
		 delete_any(key);
		 break;
	  case 4:
		 break;
	  }
	  goto start2;
   case 3:
	  traversal();
	  goto start2;
   case 4:
	  printf("\nSEARCHING:");
	  printf("\nEnter the element you want to search:");
	  scanf("%d",&item);
	  search(item);
	  goto start2;
   case 5:
	  printf("\nSORTING:");
	  printf("\nSorting-> 1.Ascending order 2.Decending order");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch3);
	  switch(ch3)
	  {
	    case 1:
		   s=1;
		   sorting(s);
		   traversal();
		   break;
	    case 2:
		   s=2;
		   sorting(s);
		   traversal();
		   break;
	  }
	  goto start2;
   case 6:
	  printf("\nINVERSION:");
	  inversion();
	  goto start2;
   case 7:
	  goto end2;
  }
  end2 : break;
 }
 break;
 case 3:
	printf("\nMERGING:=>");
	printf("1.Unsorted 2.Sorted list");
	printf("\nEnter your choice:");
	scanf("%d",&ch5);
	switch(ch5)
	{
	  case 1:
		 header=h1;
		 merge_u(h1,h2);
		 traversal();
		 break;
	  case 2:

		 merge_sort(h1,h2,h3);
		 header=h3;
		 traversal();
		 break;
	}
	break;
 case 4:
	exit(0);
}
}
 getch();
}

Algorithm :Double Linked-List Operation

 Let us consider a double linked list pointed by header.We have to
 Perform insertion,deletion,searching,traversal,sorting,inversion
 And merging operations in this linked list.

Insert_begining(header,item)
{
  In this case We have to insert an element item at the beginning of  
  the list such that it become the first node.

  t=getnode()           //getnode is a function which create a
                         new node(node has two part i) data ii) link
                         of the linked list and return the address
                         of node.
 t->data=item
 if(header->rlink=NULL)
 {
  header->rlink=t
  t->llink=header
 }
 else
 {
  trav=header->rlink
  t->rlink=trav
  trav->llink=t
  header->rlink=t
  t->llink=header
 }
}


Insert_end(header,item)
{
 In this case we want to insert an element item at the end of 
 the list such that it become the last node.

 t=getnode()
 t->data=item
 if(header->rlink=NULL)
 {
  header->rlink=t
  t->llink=header
 }
 else
 {
   trav=header->rlink            //trav points to 1st node
   while(trav->rlink≠NULL)       //until trav reaches the last node
   {
    trav=trav->rlink             //trav moves to next node
   }
   trav->rlink=t                 //the node,t is added at the last
   t->llink=trav                   position of the list   
 }                                  
}


Insert_any(header,key,item)
{
  In this case we have toinsert an element,item in this list after a
  node whose data is key. 
  
  trav=header->rlink                   //trav points to the 1st node
  while(trav->data≠key && trav≠NULL)  //until key is found or trav 
  {                                       reaches NULL
    trav=trav->rlink                   //trav moves to next node
  }
  if(trav=NULL)                        //checks if key not found
   Print  "Insertion impossible"
  else
  {
   t=getnode()
   t->data=item
   ptr=trav->rlink                  //ptr points the node just after
   trav->rlink=t                      key-containing node
   t->llink=trav
   t->rlink=ptr
   if(ptr≠NULL)                    //checks if the key-containing 
   {                                  node is not the last node
    ptr->llink=t
   }
  }
}


Forward_trav(header)
{
 trav=header->rlink                //trav points to the 1st node
 if(trav=NULL)
    print  "List empty"
 else
 {
 while(trav≠NULL)                  //until trav becomes NULL
 {
  Print  “trav->data”
  trav=trav->rlink                 //trav moves forward to next node
 }
 }
}



Backward_trav(header)
{
 trav=header->rlink           //trav points to the 1st node
 if(trav=NULL)
    print  "List empty"
 else
 {
  while(trav->rlink≠NULL)     //until trav reaches the last node
  {
   trav=trav->rlink           //trav moves to next node
  }
  while(trav≠header)          //until trav reaches the header node      
  {
   Print  “trav->data”
   trav=trav->llink           //trav moves backward to previous node 
  }
 }
}


Delete_begining(header)
{
 In this case we have to delete the 1st node of the list.

 if(header->rlink=NULL)
   print  "List empty"
 else
 {
   x=header->rlink               //x points to the 1st node
   ptr=x->rlink                  //ptr points to the 2nd node
   header->rlink=x->rlink        
   if(x->rlink≠NULL)             //checks if there’s not only 1 node                   
   {
    x->rlink->llink=header       //left-link part of 2nd node points
   }                               to header          
 }                             
}

Delete_end(header)
{
 In this case we have to delete the last node of the list.

 if(header->rlink=NULL)
   print  "List empty"
 else
  {
     trav=header->rlink           //trav points to the 1st node
     while(trav->rlink≠NULL)      //until trav reaches the last node
     {
      trav=trav->rlink            //trav moves forward to next node
     }
     trav->llink->rlink=NULL      //the right-link part of the node,
  }                                just before the last node is made
}                                  NULL



Delete_any(header,key)
{
  In this case we have to delete a node from the list containing the  
  value,key.

  if(header->rlink=NULL)
    print  "List empty"
  else
  {
   trav=header->rlink       //trav points to the 1st node in the list
   while(trav->data≠key and trav≠NULL)    //until the key is found
   {                                        or trav becomes NULL                 
     trav=trav->rlink              //trav moves forward to next node         
   }
   if(trav=NULL)                   //checks if the key not found
   {
    Print  "Deletion impossible"
   }
   else
   {
     f=trav->rlink    //f points to next node of key-containing node  
     r=trav->llink    //r points to previous node of key-containing node  
     r->rlink=f                                               
     f->llink=r
   }                           
  }
}


Search(header,item)
{
  In this case we have to search a node in the list containing the
  value,item.

  if(header->rlink=NULL)
    Print  “List empty"
  else
  {
    trav=header->rlink           //trav points to the 1st node
    j=0
    while(trav≠NULL)             //until trav becomes NULL   
    {
      if(trav->data=item)        //checks if the item is found 
      {
	  Print  "Element found in position j”
	  Return       
      }
      trav=trav->rlink         //if item not found,trav moves to  
      j=j+1;                     next node
    }
    if(trav=NULL)            
      Print  "Element not found"
  }
}



Inversion(header)
{
  In this case we have to inverse the linked list such that the
  header node of the list points to the last node.

  if(header->rlink=NULL)
    printf  "List empty"
  else
  {
    p=NULL
    q=header->rlink     //q points to the 1st node 
    while(q≠NULL)        //until q becomes NULL
    {
     r=q->rlink          //r points to the node just after q
     q->rlink=p          //right-link of q points to p
     q->llink=r          //left-link of q points to r
     p=q                 //p points to q  
     q=r                 //q points to r
    }
    header->rlink=p      //right-link of header points to last node
    p->llink=header      //left-link of last node points to header
  }
}



Sorting(header)
{
  if(header->rlink=NULL)
    print  "List empty"
  else
  {
    for(ptr=header->rlink;ptr->rlink≠NULL;ptr=ptr->rlink)
    {
      for(trav=ptr->rlink;trav≠NULL;trav=trav->rlink)
      {
	  if(option=ascending)
	  {
	    if(ptr->data>trav->data)
	    {
	      t=ptr->data
	      ptr->data=trav->data
	      trav->data=t
	    }
        }
       else if(option=descending)
       {
	   if(ptr->datadata)
	   {
	     t=ptr->data
	     ptr->data=trav->data
	     trav->data=t
	   }
       }
      }
    }
  }
}


Merge_unsorted(h1,h2)
{
  In this case we have to merge two unsorted linked lists,pointed by 
  h1 and h2. 

  trav=h1->rlink         //trav points to the 1st node of 1st list
  ptr=h2->rlink          //ptr points to the 1st node of 2nd list
  if(trav=NULL  &&  ptr=NULL)
     print  "Merging not possible"
  else
  {
    while(trav->rlink≠NULL)    //until trav reaches the last node
    {                           of 1st linked-list
      trav=trav->rlink         //trav moves to next node
    }
    trav->rlink=ptr         //rlink of trav points to 1st node of h2
    ptr->llink=trav         
    h2->llink=NULL
    h2->rlink=NULL
  }                             
}



Merge_sorted(h1, h2, h3)
{
 p1=h1->rlink                //p1 points to the 1st node of 1st list
 p2=h2->rlink                //p2 points to the 1st node of 2nd list
 while(p1!=NULL && p2!=NULL)
 {
   t=getnode()
   if(p1->datadata)
   {
     t->data=p1->data
     p1=p1->rlink              //p1 moves to next node
   }
   else
   {
     t->data=p2->data
     p2=p2->rlink              //p2 moves to next node
   }
   if(h3->rlink=NULL)
   {
    h3->rlink=t
    t->llink=h3
    trav=t
   }
   else
   {
    trav->rlink=t
    t->llink=trav
    trav=trav->rlink
   }
 }
   while(p1≠NULL)
   {
    t=getnode()
    t->data=p1->data
    p1=p1->rlink
    trav->rlink=t
    t->llink=trav
    trav=trav->rlink
   }
   while(p2≠NULL)
   {
    t=getnode()
    t->data=p2->data
    p2=p2->rlink
    trav->rlink=t
    t->llink=trav
    trav=trav->rlink
   }
 }


C Program For Double Linked List

Source Code:



#include>stdio.h>
#include>conio.h>
#include>stdlib.h>

struct node
{
 int data;
 struct node * llink;
 struct node * rlink;
};

struct node *header;

struct node * getnode()
{
 struct node *t;
 t=(struct node *)malloc(sizeof(struct node));
 t->rlink=NULL;
 t->llink=NULL;
 return t;
}

void fortrav()
{
 struct node *trav;
 trav=header->rlink;
 if(trav==NULL)
    printf("\nList empty.");
 else
 {
 printf("\nLINK  LIST :\n\n");
 while(trav!=NULL)
 {
  printf("  %d",trav->data);
  trav=trav->rlink;
 }
 }
 printf("\n");
}

void backtrav()
{
 struct node *trav;
 trav=header->rlink;
 if(trav==NULL)
    printf("\nList empty.");
 else
 {
 printf("\nLINK  LIST :\n\n");

 while(trav->rlink!=NULL)
 {
  trav=trav->rlink;
 }
 while(trav!=header)
 {
   printf("  %d",trav->data);
   trav=trav->llink;
 }
 }
 printf("\n");
}


void insert_beg(int item)
{
 struct node *t,*trav;
 t=getnode();
 t->data=item;
 if(header->rlink==NULL)
 {
  header->rlink=t;
  t->llink=header;
 }
 else
 {
  trav=header->rlink;
  t->rlink=trav;
  trav->llink=t;
  header->rlink=t;
  t->llink=header;
 }
}

void insert_end(int item)
{
 struct node *trav,*t;
 t=getnode();
 t->data=item;
 if(header->rlink==NULL)
 {
  header->rlink=t;
  t->llink=header;
 }
 else
 {
   trav=header->rlink;
   while(trav->rlink!=NULL)
   {
    trav=trav->rlink;
   }
   trav->rlink=t;
   t->llink=trav;
 }
}

void insert_any(int key,int item)
{
  struct node *trav,*t,*ptr;
  trav=header->rlink;
  while(trav->data!=key && trav!=NULL)
  {
    trav=trav->rlink;
  }
  if(trav==NULL)
  {
   printf("\nInsertion impossible\n");
  }
  else
  {
   t=getnode();
   t->data=item;
   ptr=trav->rlink;
   trav->rlink=t;
   t->llink=trav;
   t->rlink=ptr;
   if(ptr!=NULL)
   {
    ptr->llink=t;
   }
  }
}

void delete_beg()
{
 struct node *x,*ptr;
 if(header->rlink==NULL)
 {
   printf("\nList empty.\n");
 }
 else
 {
   x=header->rlink;
   ptr=x->rlink;
   header->rlink=x->rlink;
   if(ptr->rlink!=NULL)
   {
    ptr->rlink->llink=header;
   }
 }
}

void delete_end()
{
 struct node *trav,*ptr;
 if(header->rlink==NULL)
 {
   printf("\nList empty.\n");
 }
 else
 {
     trav=header->rlink;
     while(trav->rlink!=NULL)
     {
      trav=trav->rlink;
     }
     trav->llink->rlink=NULL;

 }
}

void delete_any(int key)
{
  struct node *trav,*ptr,*f,*r;
  if(header->rlink==NULL)
  {
   printf("\nList empty.\n");
  }
  else
  {
   trav=header->rlink;
   while(trav->data!=key && trav!=NULL)
   {
     trav=trav->rlink;
   }
   if(trav==NULL)
   {
    printf("\nDeletion impossible.\n");
   }
   else
   {
     f=trav->rlink;
     r=trav->llink;
     r->rlink=f;
     f->llink=r;
   }
  }
}

void search(int item)
{
  int j;
  struct node *trav;
  if(header->rlink==NULL)
  {
    printf("\nList empty");
  }
  else
  {
    trav=header->rlink;
    j=1;
    while(trav!=NULL)
    {
      if(trav->data==item)
      {
	printf("\nElement found in position=> %d",j);
	return ;
      }
      trav=trav->rlink;
      j++;
    }
    if(trav==NULL)
    {
      printf("\nElement not found.");
    }
  }
}

void sorting(int s)
{
  struct node *trav,*ptr;
  int t;
  if(header->rlink==NULL)
  {
    printf("nList empty");
  }
  else
  {
    for(ptr=header->rlink;ptr->rlink!=NULL;ptr=ptr->rlink)
    {
      for(trav=ptr->rlink;trav!=NULL;trav=trav->rlink)
      {
	if(s==1)
	{
	if(ptr->data>trav->data)
	{
	  t=ptr->data;
	  ptr->data=trav->data;
	  trav->data=t;
	}
       }
       else if(s==2)
       {
	 if(ptr->datadata)
	{
	  t=ptr->data;
	  ptr->data=trav->data;
	  trav->data=t;
	}
       }
      }
    }
  }
}

void inversion()
{
  struct node *p,*q,*r;
  if(header->rlink==NULL)
  {
    printf("\nList empty");
  }
  else
  {
    p=NULL;
    q=header->rlink;
    while(q!=NULL)
    {
     r=q->rlink;
     q->rlink=p;
     q->llink=r;
     p=q;
     q=r;
    }
    header->rlink=p;
    p->llink=header;
  }
}

void merge_u(struct node *h1,struct node *h2)
{
  struct node *trav,*ptr;
  trav=h1->rlink;
  ptr=h2->rlink;
  if(trav==NULL  &&  ptr==NULL)
     printf("\nMerging not possible.");
  else
  {
    while(trav->rlink!=NULL)
    {
      trav=trav->rlink;
    }
    trav->rlink=ptr;
    ptr->llink=trav;
    h2->llink=NULL;
    h2->rlink=NULL;
  }
}

void  merge_sort(struct node *h1,struct node *h2,struct node *h3)
{
 struct node *p1,*p2,*trav,*t;
 p1=h1->rlink;
 p2=h2->rlink;
 h3->rlink=NULL;
 h3->llink=NULL;
 while(p1!=NULL && p2!=NULL)
 {
   t=getnode();
   if(p1->datadata)
   {
     t->data=p1->data;
     p1=p1->rlink;
   }
   else
   {
     t->data=p2->data;
     p2=p2->rlink;
   }
   if(h3->rlink==NULL)
   {
    h3->rlink=t;
    t->llink=h3;
    trav=t;
   }
   else
   {
    trav->rlink=t;
    t->llink=trav;
    trav=trav->rlink;
   }
 }
   while(p1!=NULL)
   {
    t=getnode();
    t->data=p1->data;
    p1=p1->rlink;
    trav->rlink=t;
    t->llink=trav;
    trav=trav->rlink;
   }
   while(p2!=NULL)
   {
    t=getnode();
    t->data=p2->data;
    p2=p2->rlink;
    trav->rlink=t;
    t->llink=trav;
    trav=trav->rlink;
   }

}
void main()
{
 int ch,ch1,ch2,item,key,ch3,s,ch4,ch5,c1;
 struct node *h1,*h2,*h3;
 clrscr();
 h1=getnode();
 h2=getnode();
 h3=getnode();
 h1->rlink=NULL;
 h1->llink=NULL;
 h2->rlink=NULL;
 h2->llink=NULL;
 h3->rlink=NULL;
 h3->llink=NULL;

 while(1)
 {

   printf("\nLinked List Operations:");
   printf("\n1.Linked list-1\n2.Linked list-2\n3.Merging\n4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch4);
   switch(ch4)
   {
     case 1:
	    header=h1;
 while(1)
 {
 start :
 printf("\nLINKED LIST-1 OPERATION :");
 printf("\n\t1.Insertion  2.Deletion 3.Traversal 4.Search\n\t5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1");
 printf("\n\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
	  printf("\n\nINSERTION:");
	  printf("\n\t1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
	  printf("\n\nEnter your choice:");
	  scanf("%d",&ch1);
	  switch(ch1)
	  {
	  case 1:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_beg(item);
		 break;
	  case 2:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_end(item);
		 break;
	  case 3:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 printf("\nEnter the key:");
		 scanf("%d",&key);
		 insert_any(key,item);
		 break;
	  case 4:
		 break;
	  }
	  goto start;
   case 2:
	  printf("\n\nDELETION:");
	  printf("\n\t1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
	  printf("\n\nEnter your choice:");
	  scanf("%d",&ch2);
	  switch(ch2)
	  {
	  case 1:
		 delete_beg();
		 break;
	  case 2:
		 delete_end();
		 break;
	  case 3:
		 printf("\nEnter the data of the node to be deleted:");
		 scanf("%d",&key);
		 delete_any(key);
		 break;
	  case 4:
		 break;
	  }
	  goto start;
   case 3:
	  printf("\nTraversal:");
	  printf("\n\t1.Forward traversal  2.Backward traversal");
	  printf("\nEnter yourchoice:");
	  scanf("%d",&c1);
	  switch(c1)
	  {
	  case 1:
		 fortrav();
		 break;
	  case 2:
		 backtrav();
		 break;
	  }
	  goto start;
   case 4:
	  printf("\n\nSEARCHING:");
	  printf("\nEnter the element you want to search:");
	  scanf("%d",&item);
	  search(item);
	  goto start;
   case 5:
	  printf("\n\nSORTING:");
	  printf("\nSorting-> 1.Ascending order 2.Decending order");
	  printf("\n\nEnter your choice:");
	  scanf("%d",&ch3);
	  switch(ch3)
	  {
	    case 1:
		   s=1;
		   sorting(s);
		   fortrav();
		   break;
	    case 2:
		   s=2;
		   sorting(s);
		   fortrav();
		   break;
	  }
	  goto start;
   case 6:
	  printf("\n\nINVERSION:");
	  inversion();
	  fortrav();
	  goto start;
   case 7:
	  clrscr();
	  goto start;
   case 8:
	  goto end;
  }
  end : break;
 }
 break;
 case 2:
	header=h2;
 while(1)
 {
 start2 :
 printf("\n\nLINKED LIST-2 OPERATION :");
 printf("\n\t1.Insertion  2.Deletion 3.Traversal 4.Search\n\t5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2");
 printf("\n\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
	  printf("\n\nINSERTION:");
	  printf("\n\t1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
	  printf("\n\nEnter your choice:");
	  scanf("%d",&ch1);
	  switch(ch1)
	  {
	  case 1:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_beg(item);
		 break;
	  case 2:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_end(item);
		 break;
	  case 3:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 printf("\nEnter the key:");
		 scanf("%d",&key);
		 insert_any(key,item);
		 break;
	  case 4:
		 break;
	  }
	  goto start2;
   case 2:
	  printf("\n\nDELETION:");
	  printf("\n\t1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
	  printf("\n\nEnter your choice:");
	  scanf("%d",&ch2);
	  switch(ch2)
	  {
	  case 1:
		 delete_beg();
		 break;
	  case 2:
		 delete_end();
		 break;
	  case 3:
		 printf("\nEnter the data of the node to be deleted:");
		 scanf("%d",&key);
		 delete_any(key);
		 break;
	  case 4:
		 break;
	  }
	  goto start2;
   case 3:
	  printf("\nTraversal");
	  printf("\n\t1.Forward traversal 2.Backward traversal");
	  printf("\n\nEnter yourchoice:");
	  scanf("%d",&c1);
	  switch(c1)
	  {
	  case 1:
		fortrav();
		break;
	  case 2:
		 backtrav();
		 break;
	  }
	  goto start2;
   case 4:
	  printf("\n\nSEARCHING:");
	  printf("\nEnter the element you want to search:");
	  scanf("%d",&item);
	  search(item);
	  goto start2;
   case 5:
	  printf("\n\nSORTING:");
	  printf("\nSorting-> 1.Ascending order 2.Decending order");
	  printf("\n\nEnter your choice:");
	  scanf("%d",&ch3);
	  switch(ch3)
	  {
	    case 1:
		   s=1;
		   sorting(s);
		   fortrav();
		   break;
	    case 2:
		   s=2;
		   sorting(s);
		   fortrav();
		   break;
	  }
	  goto start2;
   case 6:
	  printf("\n\nINVERSION:");
	  inversion();
	  fortrav();
	  goto start2;
   case 7:
	  clrscr();
	  goto start2;
   case 8:
	  goto end2;
  }
  end2 : break;
 }
 break;
 case 3:
	printf("\n\nMERGING:=>");
	printf("1.Unsorted 2.Sorted list");
	printf("\n\nEnter your choice:");
	scanf("%d",&ch5);
	switch(ch5)
	{
	  case 1:

		 merge_u(h1,h2);
		 header=h1;
		 fortrav();
		 break;
	  case 2:

		 merge_sort(h1,h2,h3);
		 header=h3;
		 fortrav();
		 break;
	}
	break;
 case 4:
	exit(0);
}
}
 getch();
}

Algorithm : Polynomial Operations

Let us consider a polynomial expression of single variable x stored in a linked list
pointed by header node p. The nodes are arranged in descending order of exponent starting
from the header.The algorithm ‘Evaluate’ calculates the value of the polynomial depending
on the value of the x user gives. 
Evaluate(p,x)
{
  if(p->link=NULL)
	print "There is no expression to solve..!"
  else
	{
	s=0
	trav=p->link
	while(trav≠NULL)
		{
		s=s+trav->coeff*(x^trav->exp)  
		trav=trav->link
		}
	print s
	}
}

Let us consider there are two such polynomial expressions stored in two single linked list
pointed by header p1 and p2 respectively. Now the first algorithm ‘Addition’ adds the above
two polynomials and store the output polynomial in another linked list pointed by p3.
And the second algorithm ‘Multiplication’ multiplies the above two polynomials and store
the output polynomial in another linked list pointed by p3.

Addition(p1,p2,p3)
{
  m1=p1->link
  m2=p2->link
  while(m1≠NULL && m2≠NULL)					 
	{								  
	t=getnode()
	if(m1->exp>m2->exp)
		{
		t->exp=m1->exp
		t->coeff=m1->coeff
		m1=m1->link
		}
	

     else if(m1->expexp)
		{
		t->exp=m2->exp
		t->coeff=m2->coeff
		m2=m2->link
		}
	else
		{
		r=m1->coeff+m2->coeff
		if(r≠0)
			{
			t->exp=m1->exp
			t->coeff=r
			}
		else
			t=NULL
		m1=m1->link
		m2=m2->link
		}
	if(t≠NULL)
		{        	if(p3->link=NULL)
			{
			p3->link=t
			trav=t
			}
		else
			{
			trav->link=t
			trav=trav->link
			}
		}
	}
while(m1≠NULL)							
	{
	t=getnode()
	t->exp=m1->exp
	t->coeff=m1->coeff
	m1=m1->link
	trav->link=t
	trav=trav->link
	}

while(m2≠NULL)
	{
	t=getnode()
	t->exp=m2->exp
	t->coeff=m2->coeff
	m2=m2->link
	trav->link=t
	trav=trav->link
	}
show(p3)
}


Multiplication(p1,p2,p3)
{
  m1=p1->link
  while(m1≠NULL)
	{
	 m2=p2->link
	 while(m2≠NULL)
		{
		c=m1->coeff*m2->coeff
		e=m1->exp+m2->exp
		t=getnode()
		t->exp=e
		t->coeff=c
		if(p3->link=NULL)
			p3->link=t
		else
			{
			trav=p3->link
			while(trav≠NULL && trav->exp>=t->exp)
				{
				save=trav
				trav=trav->link
				}
			if(save->exp=t->exp)
				{
				save->coeff=save->coeff+t->coeff
				}
			else
				{
				save->link=t
				t->link=trav
				}
			}
		 m2=m2->link
		}
	 m1=m1->link
	}
 show(p3)
}

Here we use two functions show(header) and getnode().
The 1st one shows the elements in the linked list pointed by header.
The 2nd one creates a node and return it's address to the pointer variable.


C Program For Polynimial Operation
1.Creation
2.Evaluation
3.Addition
4.Multiplication.
5.Show
6.Exit


Source Code:




#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node
{
 int coef;
 int exp;
 struct node *link;
};


struct node * getnode()
{
 struct node *t;
 t=(struct node *)malloc(sizeof(struct node));
 t->link=NULL;
 return t;
};

void create(struct node *P)
{
  struct node *trav,*t;
  int i,n,co,ex;

  printf("\nEnter number of terms:");
  scanf("%d",&n);
  for(i=1;i<=n;i++)
   {
     t=getnode();
     printf("\nEnter co-ef of term-%d :",i);
     scanf("%d",&co);
     printf("\nEnter expo of term-%d :",i);
     scanf("%d",&ex);
     t->coef=co;
     t->exp=ex;
     if(P->link==NULL)
      {
	 P->link=t;
	 trav=P->link;
      }
     else
      {
	 trav->link=t;
	 trav=t;
      }
   }
}
void show(struct node *P)
{
  struct node *trav;
  if(P->link==NULL)
   {
     printf("\nPolynomial not created.");
   }
  else
   {
     printf("\nThe polynomial is:\t");
     trav=P->link;
     while(trav!=NULL)
      {
	if(trav->exp==0)
	 {
	   printf("%d",trav->coef);
	 }
	else
	 {
	   printf("%dX^%d+",trav->coef,trav->exp);
	 }
	trav=trav->link;
      }
   }
}



void evaluate(struct node *P,int x)
{
  float s;

  struct node *trav,*t;
  if(P->link==NULL)
   {
     printf("\nList empty.");
   }
  else
   {
     s=0;
     trav=P->link;
     while(trav!=NULL)
      {
	 s=s+(trav->coef)*pow(x,trav->exp);
	 trav=trav->link;
      }
     printf("\nValue of the polynomial(for x=%d) =%g",x,s);
   }
}


void add(struct node *p1,struct node *p2)
{
  int r;
  struct node *m1,*m2,*t,*trav,*p3;
  p3->link=NULL;
  m1=p1->link;
  m2=p2->link;
  while(m1!=NULL && m2!=NULL)
   {
     if(m1->exp>m2->exp)
      {
	t=getnode();
	t->exp=m1->exp;
	t->coef=m1->coef;
	m1=m1->link;
      }
     else if(m1->expexp)
      {
	t=getnode();
	t->exp=m2->exp;
	t->coef=m2->coef;
	m2=m2->link;
      }
     else if(m1->exp==m2->exp)
      {
	r=m1->coef+m2->coef;
	if(r!=0)
	 {
	   t=getnode();
	   t->coef=r;
	   t->exp=m1->exp;
	 }
	else
	 {
	   t=NULL;
	 }
	m1=m1->link;
	m2=m2->link;
      }
     if(t!=NULL)
      {
	if(p3->link==NULL)
	 {
	   p3->link=t;
	   trav=t;
	 }
	else
	 {
	   trav->link=t;
	   trav=trav->link;
	 }
      }
   }
  while(m1!=NULL)
   {
     t=getnode();
     t->exp=m1->exp;
     t->coef=m1->coef;
     m1=m1->link;
     trav->link=t;
     trav=trav->link;
   }
  while(m2!=NULL)
   {
     t=getnode();
     t->exp=m2->exp;
     t->coef=m2->coef;
     m2=m2->link;
     trav->link=t;
     trav=trav->link;
   }
  show(p3);
}


void polymult(struct node *p1,struct node *p2)
{
  int c,e;
  struct node *m1,*m2,*trav,*save,*t,*p3;
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    m2=p2->link;
    while(m2!=NULL)
     {
	c=m1->coef*m2->coef;
	e=m1->exp+m2->exp;
	t=getnode();
	t->exp=e;
	t->coef=c;
	if(p3->link==NULL)
	 {
	   p3->link=t;
	 }
	else
	 {
	   trav=p3->link;
	   while(trav!=NULL && trav->exp>=t->exp)
	   {
	     save=trav;
	     trav=trav->link;
	   }
	   if(save->exp==t->exp)
	    {
	      save->coef=save->coef+t->coef;
	    }
	    else
	     {
	       save->link=t;
	       t->link=trav;
	     }
	  }
	 m2=m2->link;
     }
    m1=m1->link;
  }
  show(p3);
}



void main()
{
  int ch,ch1,x,ch4,ch3;
  struct node *p1,*p2,*p3;
  
  while(1)
  {
    printf("\n@ Polynomial operations:");
    printf("\n\t1.Creation.\n\t2.Evaluation\n\t3.Addition\n\t4.Multiplication.\n\t5.Show\n\t6.Exit");  
    printf("\nEnter your choice:");
    scanf("%d",&ch);
    switch(ch)
     {
       case 1:printf("\nCreate=>1.poly-1 2.poly-2");
              printf("\nEnter your choice:");
              scanf("%d",&ch4);
              switch(ch4)
              {
                case 1:
                       p1=getnode();
                       create(p1);
                       break;
                case 2:
                       p2=getnode();
                       create(p2); 
                       break;
              }
              break;
       case 2:
              printf("\nEvaluate=>1.poly-1 2.poly-2");
              printf("\nEnter your choice:");
              scanf("%d",&ch4);
              switch(ch4)
              {
                case 1:
                       printf("\nEnter the value of x :");
                       scanf("%d",&x);
                       evaluate(p1,x);
                       break;
                case 2:
                       printf("\nEnter the value of x :");
                       scanf("%d",&x);
                       evaluate(p2,x); 
                       break;
              }
              break;
              
       case 3:
	      add(p1,p2);

	      break;
       case 4:
	      polymult(p1,p2);

	      break;
       case 5:
	      printf("\nshow=>1.poly-1 2.poly-2");
	      printf("\nEnter your choice:");
	      scanf("%d",&ch3);
	      switch(ch3)
	      {
		case 1:

		       show(p1);
		       break;
		case 2:

		       show(p2);
		       break;
	      }
	      break;
       case 6:
	      exit(0);
     }
  }
}



 OUTPUT :
  
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:1

Create=>1.poly-1 2.poly-2
Enter your choice:1

Enter number of terms:3

Enter co-ef of term-1 :3

Enter expo of term-1 :2

Enter co-ef of term-2 :4

Enter expo of term-2 :1

Enter co-ef of term-3 :1

Enter expo of term-3 :0

@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:1

Create=>1.poly-1 2.poly-2
Enter your choice:2

Enter number of terms:2

Enter co-ef of term-1 :2

Enter expo of term-1 :1

Enter co-ef of term-2 :3

Enter expo of term-2 :0

@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:5

show=>1.poly-1 2.poly-2
Enter your choice:1

The polynomial is:      3X^2+4X^1+1
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:5

show=>1.poly-1 2.poly-2
Enter your choice:2

The polynomial is:      2X^1+3
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:2

Evaluate=>1.poly-1 2.poly-2
Enter your choice:1

Enter the value of x :2

Value of the polynomial(for x=2) =21
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:3

The polynomial is:      3X^2+6X^1+4
@ Polynomial operations:
        1.Creation.
        2.Evaluation
        3.Addition
        4.Multiplication.
        5.Show
        6.Exit
Enter your choice:4

The polynomial is:      6X^3+17X^2+14X^1+3



*************************Another Method Of Polynimial Operation*******************************

Source Code:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

struct node
{
    int coef;
    int expo;
    struct node *link;
};

struct node *create(struct node *);
struct node *insert_s(struct node *,float,int);
struct node *insert(struct node *,float,int);
void display(struct node *ptr);
void poly_add(struct node *,struct node *);
void poly_mult(struct node *,struct node *);
int main()
{
    struct node *start1=NULL,*start2=NULL;
    int c,ch;
    printf("Enter polynomial 1 :\n\n");
    start1=create(start1);

    printf("Enter polynomial 2 :\n\n");
    start2=create(start2);

    printf("Polynomial 1 is :  ");
    display(start1);
    printf("Polynomial 2 is :  ");
    display(start2);
    do
    {
	printf("****MENU****");
	printf("\n1. Addition");
	printf("\n2. multiplication");
	printf("\n3. Exit");
	printf("\nenter your choice(1-3):");
	scanf("%d",&c);
	switch(c)
	{
		case 1:  poly_add(start1, start2);
			 break;
		case 2:  poly_mult(start1, start2);
			  break;
		case 3:	exit(0);

		default:printf("wrong choice");
			break;
	}

	printf("do you wish to continue?(0/1):");
	scanf("%d",&ch);
    }while(ch==1);
    getch();
    return 0;
}//End of main()

struct node *create(struct node *start)
{
    int i,n,ex;
    float co;
    printf("Enter the number of terms : ");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
	printf("Enter coeficient for term %d : ",i);
	scanf("%f",&co);
	printf("Enter exponent for term %d : ",i);
	scanf("%d",&ex);
	start=insert_s(start,co,ex);
    }
    return start;
}//End of create()
struct node *insert_s(struct node *start,float co,int ex)
{
    struct node *ptr,*tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->coef=co;
    tmp->expo=ex;
    //list empty or exp greater than first one 
    if(start==NULL || ex > start->expo)
    {
	tmp->link=start;
	start=tmp;
    }
    else
    {
	ptr=start;
	while(ptr->link!=NULL && ptr->link->expo >= ex)
	    ptr=ptr->link;
	tmp->link=ptr->link;
	ptr->link=tmp;
    }
    return start;
}//End of insert()

struct node *insert(struct node *start,float co,int ex)
{
    struct node *ptr,*tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->coef=co;
    tmp->expo=ex;
    //if list is empty
    if(start==NULL)
    {
	tmp->link=start;
	start=tmp;
    }
    else    //Insert at the end of the list
    {
	ptr=start;
	while(ptr->link!=NULL)
	    ptr=ptr->link;
	tmp->link=ptr->link;
	ptr->link=tmp;
    }
    return start;
}//End of insert()

void display(struct node *ptr)
{
    if(ptr==NULL)
    {
	printf("Zero polynomial\n");
	return;
    }
    while(ptr!=NULL)
    {
	printf("(%dx^%d)", ptr->coef,ptr->expo);
	ptr=ptr->link;
	if(ptr!=NULL)
	    printf(" + ");
	else
	    printf("\n");
    }
}//End of display()
void poly_add(struct node *p1,struct node *p2)
{
    struct node *start3;
    start3=NULL;

    while(p1!=NULL && p2!=NULL)
    {
	if(p1->expo > p2->expo)
	{
	    start3=insert(start3,p1->coef,p1->expo);
	    p1=p1->link;
	}
	else if(p2->expo > p1->expo)
	{
	    start3=insert(start3,p2->coef,p2->expo);
	    p2=p2->link;
	}
	else if(p1->expo==p2->expo)
	{
	    start3=insert(start3,p1->coef+p2->coef,p1->expo);
	    p1=p1->link;
	    p2=p2->link;
	}
    }
    //if poly2 has finished and elements left in poly1
    while(p1!=NULL)
    {
	start3=insert(start3,p1->coef,p1->expo);
	p1=p1->link;
    }
    //if poly1 has finished and elements left in poly2
    while(p2!=NULL)
    {
	start3=insert(start3,p2->coef,p2->expo);
	p2=p2->link;
    }
    printf("Added polynomial is : ");
    display(start3);
}//End of poly_add()

void poly_mult(struct node *p1, struct node *p2)
{
    struct node *start3;
    struct node *p2_beg = p2;
    start3=NULL;
    if(p1==NULL || p2==NULL)
    {
	printf("Multiplied polynomial is zero polynomial\n");
	return;
    }
    while(p1!=NULL)
    {
	p2=p2_beg;
	while(p2!=NULL)
	{
	    start3=insert_s(start3,p1->coef*p2->coef,p1->expo+p2->expo);
	    p2=p2->link;
	}
	p1=p1->link;
    }

    printf("Multiplied polynomial is : ");
    display(start3);
}//End of poly_mult()


input-output:
Enter polynomial 1 :

Enter the number of terms : 3
Enter coeficient for term 1 : 4
Enter exponent for term 1 : 2
Enter coeficient for term 2 : 3
Enter exponent for term 2 : 1
Enter coeficient for term 3 : 6
Enter exponent for term 3 : 0
Enter polynomial 2 :

Enter the number of terms : 3
Enter coeficient for term 1 : 4
Enter exponent for term 1 : 3
Enter coeficient for term 2 : 6
Enter exponent for term 2 : 2
Enter coeficient for term 3 : 4
Enter exponent for term 3 : 1
Polynomial 1 is :  (4x^2) + (3x^1) + (6x^0)
Polynomial 2 is :  (4x^3) + (6x^2) + (4x^1)
****MENU****
1. Addition
2. multiplication
3. Exit
enter your choice(1-3):1
Added polynomial is : (4x^3) + (10x^2) + (7x^1) + (6x^0)
do you wish to continue?(0/1):1
****MENU****
1. Addition
2. multiplication
3. Exit
enter your choice(1-3):2
Multiplied polynomial is : (16x^5) + (24x^4) + (12x^4) + (16x^3) + (18x^3) + (24
x^3) + (12x^2) + (36x^2) + (24x^1)
do you wish to continue?(0/1):0



  

Algorithm:Circular Linked-List Operation

 Let us consider a circular linked list pointed by header.We have to
 Perform insertion,deletion,searching,traversal,sorting,inversion
 And merging operations in this linked list.

Insert_begining(header,item)
{
 In this case We have to insert an element item at the beginning of  
 the list such that it become the first node.

 t=getnode()            //getnode is a function which create a new node
                        (node has two part i) data ii) link 
                        of the linked list and return the address of node. 
 t->data=item         
 if(header->link=header)
 {
  header->link=t
 }
 else
 {
  t->link=header->link
  header->link=t
 }
}



Insert_end(header,item)
{
 In this case we want to insert an element item at the end of 
 the list such that it become the last node.

 t=getnode()
 t->data=item
 if(header->link=header)
 {
  header->link=t
 }
 else
 {
   trav=header->link              //trav points to 1st node
   while(trav->link≠header)       //until trav reaches the last node  
   {
    trav=trav->link               //trav moves to next node
   }
   trav->link=t                   //the node,t is added at the last 
 }                                  position of the list
}







Insert_any(header,key,item)
{
 In this case we have toinsert an element,item in this list after a
 node whose data is key. 

  t=getnode()
  t->data=item
  trav=header->link                      //trav points to 1st node
  while(trav->data≠key and trav≠header)  //until key not found and
  {                                        the trav becomes header
    trav=trav->link                      //trav moves to next node
  }
  if(trav=header)                        //checks if key not found
  {
   Print  "Insertion impossible"
  }
  else
  {
   t->link=trav->link        //t points to the node just after trav
   trav->link=t              //trav points to t
  }
}


Traversal(header)
{
 trav=header->link
 if(trav=header)
    print  "List empty"
 else
 {
  while(trav!=header)            //until trav becomes header
  {
   Print  "trav->data”
   trav=trav->link             //trav moves to next node
  }
 }
}


Delete_begining(header)
{
 In this case we have to delete the 1st node of the list.

 if(header->link=header)
   print  "List empty"
 else
 {
   x=header->link            //x points to the 1st node in the list
   header->link=x->link      //the link part of header points to the 
 }                             2nd node
}




Delete_end(header)
{
 In this case we have to delete the last node of the list.

 if(header->link=header)
   print  "List empty"
 else
 {
   ptr=header->link          //ptr points to the 1st node in the list 
   if(ptr->link=header)        /checks if there is only one node 
     header->link=header           present in the list
   else
   {
     trav=ptr->link               //trav points to the 2nd node
     while(trav->link≠header)     //until trav reaches the last node
     {
      ptr=trav                    //ptr points to trav
      trav=trav->link             //trav moves to next node
     }
     ptr->link=header        //the link part of the node just before 
   }                         the last node is made header
 }
}



Delete_any(header,key)
{
  In this case we have to delete a node from the list containing the  
  value,key.

  if(header->link=header)
    print  "List empty"
  else
  {
   ptr=header                //ptr points to header node
   trav=ptr->link           //trav points to the 1st node in the list
   while(trav->data≠key and trav≠header)   //until the key not found
   {                                        or trav becomes header                 
     ptr=trav                             //ptr points to trav  
     trav=trav->link                      //trav moves to next node         
   }
   if(trav=header)                     //checks if the key not found
   {
    Print  "Deletion impossible"
   }
   else
   {
     ptr->link=trav->link    //the link part of ptr points to the
   }                           node just after trav
  }
}





Search(header,item)
{
  In this case we have to search a node in the list containing the
  value,item.

  if(header->link=header)
    Print  “List empty"
  else
  {
    trav=header->link            //trav points to the 1st node
    j=0
    while(trav≠header)             //until trav becomes header   
    {
      if(trav->data=item)        //checks if the item is found 
      {
	  Print  "Element found in position j”
	  Return       
      }
      trav=trav->link         //if item not found,trav moves to  
      j=j+1                    next node
    }
    if(trav=header)            
      Print  "Element not found"
  }
}



Inversion(header)
{
  In this case we have to inverse the linked list such that the
  header node of the list points to the last node.
  
  if(header->link=header)
    printf  "List empty"
  else
  {
    p=header
    q=header->link         //q points to the 1st node
    while(q≠header)          //until q becomes header   
    { 
      r=q->link            //r points to the node just after q
      q->link=p
      p=q                  //p points to q  
      q=r                  //q points to r      
    }
    header->link=p         //link part of header points to p
  }
}





Sorting(header)
{
  In this case we have to sort the nodes of the list accoeding to
  the value of the nodes in ascending or descending order. 
  if(header->link=header)
    Print  "List empty"
  else
  {
    for(ptr=header->link;ptr->link≠header;ptr=ptr->link)  
    {
      for(trav=ptr->link;trav≠header;trav=trav->link)
      {
	if(option=ascending)
	{
	  if(ptr->data>trav->data)
	  {
	    t=ptr->data
	    ptr->data=trav->data
	    trav->data=t
	  }
      }
       else if(option=descending)
       {
	   if(ptr->datadata)
	   {
	     t=ptr->data;
	     ptr->data=trav->data
	     trav->data=t
	   }
       }
      }
    }
  }
}


Merge_unsorted(h1,h2)
{
  In this case we have to merge two unsorted linked lists pointed  
  by h1 and h2.
 
  trav=h1->link         //trav points to the 1st node of 1st list
  ptr=h2->link          //ptr points to the 1st node of 2nd list
  if(trav=header  &&  ptr=header)
     print  "Merging not possible"
  else
  {
    while(trav->link≠header)    //until trav reaches the last node
    {                             of 1st linked-list
      trav=trav->link          //trav moves to next node
    }
    trav->link=h2->link        //now trav points to the 1st node
  }                              of 2nd linked-list
}






Merge_sorted(h1, h2, h3)
{
 In this case we have to merge two linked lists in sorted order 
 pointed by headers h1 and h2.

 p1=h1->link                 //p1 points to the 1st node of 1st list
 p2=h2->link                 //p2 points to the 1st node of 2nd list   
 while(p1≠h1 && p2≠h2)   
 {
   t=getnode()
   if(p1->datadata)
   {
     t->data=p1->data
     p1=p1->link            //p1 moves to next node
   }
   else
   {
     t->data=p2->data
     p2=p2->link            //p2 moves to next node 
   }
   if(h3->link=h3)        
   {
    h3->link=t
    trav=t
   }
   else
   {
    trav->link=t
    trav=trav->link
   }
 }
   while(p1≠h1)
   {
    t=getnode()
    t->data=p1->data
    p1=p1->link
    trav->link=t
    trav=trav->link
   }
   while(p2≠h2)
   {
    t=getnode()
    t->data=p2->data
    p2=p2->link
    trav->link=t
    trav=trav->link
   }

}
C Program For Circular Linked List

Source Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct node
{
 int data;
 struct node *link;
};
struct node *header;

struct node * getnode()
{
 struct node *t;
 int item;
 t=(struct node *)malloc(sizeof(struct node));
 t->link=t;
 return t;
}

void traversal()
{
 struct node *trav;
 trav=header->link;
 if(trav==header)
    printf("\nList empty.");
 else
 {
 printf("\nLINK  LIST :\n\n");
 while(trav!=header)
 {
  printf("  %d",trav->data);
  trav=trav->link;
 }
 }
 printf("\n");
}

void insert_beg(int item)
{
 struct node *t;
 t=getnode();
 t->data=item;
 if(header->link==header)
 {
  header->link=t;
  t->link=header;
 }
 else
 {
  t->link=header->link;
  header->link=t;
 }
}

void insert_end(int item)
{
 struct node *trav,*t;
 t=getnode();
 t->data=item;
 if(header->link==header)
 {
  header->link=t;
  t->link=header;
 }
 else
 {
   trav=header->link;
   while(trav->link!=header)
   {
    trav=trav->link;
   }
   trav->link=t;
   t->link=header;
 }
}

void insert_any(int key,int item)
{
  struct node *trav,*t;
  trav=header->link;
  while(trav->data!=key && trav!=header)
  {
    trav=trav->link;
  }
  if(trav==header)
  {
   printf("\nInsertion impossible\n");
  }
  else
  {
   t=getnode();
   t->data=item;
   t->link=trav->link;
   trav->link=t;
  }
}

void delete_beg()
{
 struct node *x;
 if(header->link==header)
 {
   printf("\nList empty.\n");

 }
 else
 {
   x=header->link;
   header->link=x->link;
 }
}

void delete_end()
{
 struct node *trav,*ptr;
 if(header->link==header)
 {
   printf("\nList empty.\n");
 }
 else
 {
   ptr=header->link;
   if(ptr->link==header)
   {
     header->link=header;
   }
   else
   {
     while(ptr->link!=header)
     {
      ptr=ptr->link;
     }
     trav=ptr->link;
     while(trav->link!=ptr)
     {
      trav=trav->link;
     }
     trav->link=ptr->link;
   }
 }
}

void delete_any(int key)
{
  struct node *trav,*ptr;
  if(header->link==header)
  {
   printf("\nList empty.\n");
  }
  else
  {
   ptr=header->link;
   while(ptr->data!=key && ptr!=header)
   {
     ptr=ptr->link;
   }
   if(ptr==header)
   {
    printf("\nDeletion impossible.\n");
   }
   else
   {
    trav=ptr->link;
    while(trav->link!=ptr)
    {
     trav=trav->link;
    }
    trav->link=ptr->link;
   }
  }
}

void search(int item)
{
  int j;
  struct node *trav;
  if(header->link==header)
  {
    printf("\nList empty");
  }
  else
  {
    trav=header->link;
    j=1;
    while(trav!=header && trav->data!=item)
    {
      trav=trav->link;
      j++;
    }
    if(trav==header)
    {
      printf("\nElement not found.");
    }
    else
    {
      printf("\nElement found in position:%d",j);
    }
  }
}

void sorting(int s)
{
  struct node *trav,*ptr;
  int t;
  if(header->link==header)
  {
    printf("nList empty");
  }
  else
  {
    for(ptr=header->link;ptr->link!=header;ptr=ptr->link)
    {
      for(trav=ptr->link;trav!=header;trav=trav->link)
      {
	if(s==1)
	{
	if(ptr->data>trav->data)
	{
	  t=ptr->data;
	  ptr->data=trav->data;
	  trav->data=t;
	}
       }
       else if(s==2)
       {
	 if(ptr->datadata)
	{
	  t=ptr->data;
	  ptr->data=trav->data;
	  trav->data=t;
	}
       }
      }
    }
  }
}

void inversion()
{
  struct node *p,*q,*r;
  if(header->link==header)
  {
    printf("\nList empty");
  }
  else
  {
    p=header;
    q=header->link;
    while(q!=header)
    {
      r=q->link;
      q->link=p;
      p=q;
      q=r;
    }
    header->link=p;
    traversal();
  }
}

void merge_u(struct node *h1,struct node *h2)
{
  struct node *trav,*ptr;
  trav=h1->link;
  ptr=h2->link;
  if(trav==h1  &&  ptr==h2)
     printf("\nMerging not possible.");
  else
  {
    while(trav->link!=h1)
    {
      trav=trav->link;
    }
    trav->link=ptr;
    while(ptr->link!=h2)
    {
     ptr=ptr->link;
    }
    ptr->link=h1;
    h2->link=h2;
  }
}

void  merge_sort(struct node *h1,struct node *h2,struct node *h3)
{
 struct node *p1,*p2,*trav,*t;
 p1=h1->link;
 p2=h2->link;
 while(p1!=h1 && p2!=h2)
 {
   t=getnode();
   if(p1->datadata)
   {
     t->data=p1->data;
     p1=p1->link;
   }
   else
   {
     t->data=p2->data;
     p2=p2->link;
   }
   if(h3->link==h3)
   {
    h3->link=t;
    trav=t;
   }
   else
   {
    trav->link=t;
    trav=trav->link;
   }
 }
   while(p1!=h1)
   {
    t=getnode();
    t->data=p1->data;
    p1=p1->link;
    trav->link=t;
    trav=trav->link;
   }
   while(p2!=h2)
   {
    t=getnode();
    t->data=p2->data;
    p2=p2->link;
    trav->link=t;
    trav=trav->link;
   }
   trav->link=h3;

}
void main()
{
 int ch,ch1,ch2,item,key,ch3,s,ch4,ch5;
 struct node *h1,*h2,*h3;
 h1=getnode();
 h1->link=h1;
 h2=getnode();
 h2->link=h2;
 h3=getnode();
 h3->link=h3;
 clrscr();
 while(1)
 {

   printf("\nLinked List Operations:");
   printf("\n1.Linked list-1\n2.Linked list-2\n3.Merging\n4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch4);
   switch(ch4)
   {
     case 1:
	    header=h1;
 while(1)
 {
 start :
 printf("\nLINKED LIST-1 OPERATION :");
 printf("\n1.Insertion  2.Deletion 3.Traversal 4.Search\n5.Sorting  6.Inversion  7.Exit from LL-1");
 printf("\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
	  printf("\nINSERTION:");
	  printf("\n1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch1);
	  switch(ch1)
	  {
	  case 1:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_beg(item);
		 break;
	  case 2:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_end(item);
		 break;
	  case 3:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 printf("\nEnter the key:");
		 scanf("%d",&key);
		 insert_any(key,item);
		 break;
	  case 4:
		 break;
	  }
	  goto start;
   case 2:
	  printf("\nDELETION:");
	  printf("\n1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch2);
	  switch(ch2)
	  {
	  case 1:
		 delete_beg();
		 break;
	  case 2:
		 delete_end();
		 break;
	  case 3:
		 printf("\nEnter the data of the node to be deleted:");
		 scanf("%d",&key);
		 delete_any(key);
		 break;
	  case 4:
		 break;
	  }
	  goto start;
   case 3:
	  traversal();
	  goto start;
   case 4:
	  printf("\nSEARCHING:");
	  printf("\nEnter the element you want to search:");
	  scanf("%d",&item);
	  search(item);
	  goto start;
   case 5:
	  printf("\nSORTING:");
	  printf("\nSorting-> 1.Ascending order 2.Decending order");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch3);
	  switch(ch3)
	  {
	    case 1:
		   s=1;
		   sorting(s);
		   traversal();
		   break;
	    case 2:
		   s=2;
		   sorting(s);
		   traversal();
		   break;
	  }
	  goto start;
   case 6:
	  printf("\nINVERSION:");
	  inversion();
	  goto start;
   case 7:
	  goto end;
  }
  end : break;
 }
 break;
 case 2:
	header=h2;
 while(1)
 {
 start2 :
 printf("\nLINKED LIST-2 OPERATION :");
 printf("\n1.Insertion  2.Deletion 3.Traversal 4.Search\n5.Sorting  6.Inversion  7.Exit from LL-2");
 printf("\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
	  printf("\nINSERTION:");
	  printf("\n1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch1);
	  switch(ch1)
	  {
	  case 1:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_beg(item);
		 break;
	  case 2:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 insert_end(item);
		 break;
	  case 3:
		 printf("\nEnter the item to be inserted:");
		 scanf("%d",&item);
		 printf("\nEnter the key:");
		 scanf("%d",&key);
		 insert_any(key,item);
		 break;
	  case 4:
		 break;
	  }
	  goto start2;
   case 2:
	  printf("\nDELETION:");
	  printf("\n1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch2);
	  switch(ch2)
	  {
	  case 1:
		 delete_beg();
		 break;
	  case 2:
		 delete_end();
		 break;
	  case 3:
		 printf("\nEnter the data of the node to be deleted:");
		 scanf("%d",&key);
		 delete_any(key);
		 break;
	  case 4:
		 break;
	  }
	  goto start2;
   case 3:
	  traversal();
	  goto start2;
   case 4:
	  printf("\nSEARCHING:");
	  printf("\nEnter the element you want to search:");
	  scanf("%d",&item);
	  search(item);
	  goto start2;
   case 5:
	  printf("\nSORTING:");
	  printf("\nSorting-> 1.Ascending order 2.Decending order");
	  printf("\nEnter your choice:");
	  scanf("%d",&ch3);
	  switch(ch3)
	  {
	    case 1:
		   s=1;
		   sorting(s);
		   traversal();
		   break;
	    case 2:
		   s=2;
		   sorting(s);
		   traversal();
		   break;
	  }
	  goto start2;
   case 6:
	  printf("\nINVERSION:");
	  inversion();
	  goto start2;
   case 7:
	  goto end2;
  }
  end2 : break;
 }
 break;
 case 3:
	printf("\nMERGING:=>");
	printf("1.Unsorted 2.Sorted list");
	printf("\nEnter your choice:");
	scanf("%d",&ch5);
	switch(ch5)
	{
	  case 1:
		 header=h1;
		 merge_u(h1,h2);
		 traversal();
		 break;
	  case 2:

		 merge_sort(h1,h2,h3);
		 header=h3;
		 traversal();
		 break;
	}
	break;
 case 4:
	exit(0);
}
}
 getch();
}


 OUTPUT :
 
Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:1

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:1

Enter the item to be inserted:22

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:2

Enter the item to be inserted:44

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:2

Enter the item to be inserted:66

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:3

Enter the item to be inserted:88

Enter the key:44

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:3

LINK  LIST :

  22  44  88  66
  
LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:4

SEARCHING:
Enter the element you want to search:88

Element found in position:3
LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:6

INVERSION:
LINK  LIST :

  66  88  44  22

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:5

SORTING:
Sorting-> 1.Ascending order 2.Decending order
Enter your choice:1

LINK  LIST :

  22  44  66  88

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:5

SORTING:
Sorting-> 1.Ascending order 2.Decending order
Enter your choice:2

LINK  LIST :

  88  66  44  22

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:2

DELETION:
1.Delete begining 2.Delete end 3.Delete any pos 4.Break
Enter your choice:1

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:3

LINK  LIST :

  66  44  22

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:2

DELETION:
1.Delete begining 2.Delete end 3.Delete any pos 4.Break
Enter your choice:2

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:3

LINK  LIST :

  66  44

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:2

Enter the item to be inserted:22

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:2

Enter the item to be inserted:88

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:3

LINK  LIST :

  66  44  22  88

LINKED LIST-1 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-1
Enter your choice:7

Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:2

LINKED LIST-2 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-2
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:1

Enter the item to be inserted:33

LINKED LIST-2 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-2
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:2

Enter the item to be inserted:11

LINKED LIST-2 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-2
Enter your choice:1

INSERTION:
1.Insert begining 2.Insert end 3.Insert any pos 4.Break
Enter your choice:2

Enter the item to be inserted:55

LINKED LIST-2 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-2
Enter your choice:3

LINK  LIST :

  33  11  55

LINKED LIST-2 OPERATION :
1.Insertion  2.Deletion 3.Traversal 4.Search
5.Sorting  6.Inversion  7.Exit from LL-2
Enter your choice:7

Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:3

MERGING:=>1.Unsorted 2.Sorted list
Enter your choice:2

LINK  LIST :

  11  22  33  44  55  66  88

Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:3

MERGING:=>1.Unsorted 2.Sorted list
Enter your choice:1

LINK  LIST :

  66  44  22  88  33  11  55

Algorithm :Circular Double Linked-List Operation

Let us consider a circular double linked list pointed by header.
We have to Perform insertion,deletion ,searching ,traversal, sorting,
inversion and merging operations in this linked list.

Insert_begining(header,item)
{
  In this case We have to insert an element item at the
   beginning of the list such that it become the first node.

  t=getnode()           //getnode is a function which create a
                         new node(node has two part i) data ii) link
                         of the linked list and return the address
                         of node.
 t->data=item
 if(header->rlink=header)
 {
  header->rlink=t
  t->llink=header
 }
 else
 {
  trav=header->rlink
  t->rlink=trav
  trav->llink=t
  header->rlink=t
  t->llink=header
 }
}


Insert_end(header,item)
{
 In this case we want to insert an element item at the end of 
 the list such that it become the last node.

 t=getnode()
 t->data=item
 if(header->rlink=header)
 {
  header->rlink=t
  t->llink=header
 }
 else
 {
   trav=header->rlink            //trav points to 1st node
   while(trav->rlink≠header)      //until trav reaches the last node
   {
    trav=trav->rlink             //trav moves to next node
   }
   trav->rlink=t                 //the node,t is added at the last
   t->llink=trav                   position of the list   
 }                                  
}


Insert_any(header,key,item)
{
  In this case we have toinsert an element,item in this list after a
  node whose data is key. 
  
  trav=header->rlink                   //trav points to the 1st node
  while(trav->data≠key && trav≠header)  //until key is found or trav 
  {                                       reaches header
    trav=trav->rlink                   //trav moves to next node
  }
  if(trav=header)                        //checks if key not found
   Print  "Insertion impossible"
  else
  {
   t=getnode()
   t->data=item
   ptr=trav->rlink                  //ptr points the node just after
   trav->rlink=t                      key-containing node
   t->llink=trav
   t->rlink=ptr
   if(ptr≠header)                    //checks if the key-containing 
   {                                  node is not the last node
    ptr->llink=t
   }
  }
}


Forward_trav(header)
{
 trav=header->rlink                //trav points to the 1st node
 if(trav=header)
    print  "List empty"
 else
 {
 while(trav≠header)                  //until trav reaches header
 {
  Print  “trav->data”
  trav=trav->rlink                 //trav moves forward to next node
 }
 }
}


Backward_trav(header)
{
 trav=header->rlink           //trav points to the 1st node
 if(trav=header)
    print  "List empty"
 else
 {
  while(trav->rlink≠header)     //until trav reaches the last node
  {
   trav=trav->rlink           //trav moves to next node
  }
  while(trav≠header)          //until trav reaches the header node      
  {
   Print  “trav->data”
   trav=trav->llink           //trav moves backward to previous node 
  }
 }
}


Delete_begining(header)
{
 In this case we have to delete the 1st node of the list.

 if(header->rlink=header)
   print  "List empty"
 else
 {
   x=header->rlink               //x points to the 1st node
   ptr=x->rlink                  //ptr points to the 2nd node
   header->rlink=x->rlink        
   if(x->rlink≠header)           //checks if there’s not only 1 node                   
   {
    x->rlink->llink=header       //left-link part of 2nd node points
   }                               to header          
 }                             
}


Delete_end(header)
{
 In this case we have to delete the last node of the list.

 if(header->rlink=header)
   print  "List empty"
 else
  {
     trav=header->rlink           //trav points to the 1st node
     while(trav->rlink≠header)    //until trav reaches the last node
     {
      trav=trav->rlink            //trav moves forward to next node
     }
     trav->llink->rlink=header    //the right-link part of the node,
  }                                just before the last node is made
}                                  header



Delete_any(header,key)
{
  In this case we have to delete a node from the list containing the  
  value,key.

  if(header->rlink=header)
    print  "List empty"
  else
  {
   trav=header->rlink       //trav points to the 1st node in the list
   while(trav->data≠key and trav≠header)   //until the key is found
   {                                         or trav reaches header                 
     trav=trav->rlink              //trav moves forward to next node         
   }
   if(trav=header)                   //checks if the key not found
   {
    Print  "Deletion impossible"
   }
   else
   {
     f=trav->rlink    //f points to next node of key-containing node  
     r=trav->llink    //r points to previous node of key-containing  
     r->rlink=f                                               node
     f->llink=r
   }                           
  }
}


Search(header,item)
{
  In this case we have to search a node in the list containing the
  value,item.

  if(header->rlink=header)
    Print  “List empty"
  else
  {
    trav=header->rlink           //trav points to the 1st node
    j=0
    while(trav≠header)             //until trav reaches header   
    {
      if(trav->data=item)        //checks if the item is found 
      {
   Print  "Element found in position j”
   Return       
      }
      trav=trav->rlink         //if item not found,trav moves to  
      j=j+1;                     next node
    }
    if(trav=header)            
      Print  "Element not found"
  }
}



Inversion(header)
{
 In this case we have to inverse the linked list such that the
  header node of the list points to the last node.

  if(header->rlink=header)
    printf  "List empty"
  else
  {
    p=header
    q=header->rlink      //q points to the 1st node 
    while(q≠header)      //until q reaches header
    {
     r=q->rlink          //r points to the node just after q
     q->rlink=p          //right-link of q points to p
     q->llink=r          //left-link of q points to r
     p=q                 //p points to q  
     q=r                 //q points to r
    }
    header->rlink=p      //right-link of header points to last node
    p->llink=header      //left-link of last node points to header
  }
}



Sorting(header)
{
  if(header->rlink=header)
    print  "List empty"
  else
  {
    for(ptr=header->rlink;ptr->rlink≠header;ptr=ptr->rlink)
    {
      for(trav=ptr->rlink;trav≠header;trav=trav->rlink)
      {
   if(option=ascending)
   {
     if(ptr->data>trav->data)
     {
       t=ptr->data
       ptr->data=trav->data
       trav->data=t
     }
        }
       else if(option=descending)
       {
    if(ptr->datadata)
    {
      t=ptr->data
      ptr->data=trav->data
      trav->data=t
    }
       }
      }
    }
  }
}


Merge_unsorted(h1,h2)
{
 //trav points to the 1st node of 1st list
  ptr=h2->rlink          //ptr points to the 1st node of 2nd list
  if(trav=header  &&  ptr=header)
     print  "Merging not possible"
  else
  {
    while(trav->rlink≠header)    //until trav reaches the last node
    {                              of 1st linked-list
      trav=trav->rlink           //trav moves forward to next node
    }
    trav->rlink=ptr         //rlink of trav points to 1st node of h2
    ptr->llink=trav         
    h2->llink=header
    h2->rlink=header
  }                             
}



Merge_sorted(h1, h2, h3)
{
 p1=h1->rlink                       //p1 points to the 1st node of 1st list
 p2=h2->rlink                       //p2 points to the 1st node of 2nd list
 while(p1!=header && p2!=header)
 {
   t=getnode()
   if(p1->datadata)
   {
     t->data=p1->data
     p1=p1->rlink                   //p1 moves to next node
   }
   else
   {
     t->data=p2->data
     p2=p2->rlink                   //p2 moves to next node
   }
   if(h3->rlink=header)
   {
    h3->rlink=t
    t->llink=h3
    trav=t
   }
   else
   {
    trav->rlink=t
    t->llink=trav
    trav=trav->rlink
   }
 }
   while(p1≠header)
   {
    t=getnode()
    t->data=p1->data
    p1=p1->rlink
    trav->rlink=t
    t->llink=trav
    trav=trav->rlink
   }
   while(p2≠header)
   {
    t=getnode()
    t->data=p2->data
    p2=p2->rlink
    trav->rlink=t
    t->llink=trav
    trav=trav->rlink
   }
 }

C Program For Circular Double Linked List

1.Insertion 
2.Deletion 
3.Traversal 
4.Search 
5.Sorting
6.Inversion
7.Clrscr
8.Exit

Source Code:


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct node
{
 int data;
 struct node * llink;
 struct node * rlink;
};

struct node *header;

struct node * getnode()
{
 struct node *t;
 t=(struct node *)malloc(sizeof(struct node));
 t->rlink=header;
 t->llink=header;
 return t;
}

void fortrav()
{
 struct node *trav;
 trav=header->rlink;
 if(trav==header && header->llink==header)
    printf("\nList empty.");
 else
 {
 printf("\nLINK  LIST :\n\n");
 while(trav!=header)
 {
  printf("  %d",trav->data);
  trav=trav->rlink;
 }
 }
 printf("\n");
}

void backtrav()
{
 struct node *trav;
 trav=header->llink;
 if(trav==header)
    printf("\nList empty.");
 else
 {
 printf("\nLINK  LIST :\n\n");
 while(trav!=header)
 {
   printf("  %d",trav->data);
   trav=trav->llink;
 }
 }
 printf("\n");
}


void insert_beg(int item)
{
 struct node *t,*trav;
 t=getnode();
 t->data=item;
 if(header->rlink==header && header->llink==header)
 {
  header->rlink=t;
  header->llink=t;
  t->llink=header;
  t->rlink=header;
 }
 else
 {
  trav=header->rlink;
  t->rlink=trav;
  trav->llink=t;
  t->llink=header;
  header->rlink=t;
  trav->rlink=header;
 }
}

void insert_end(int item)
{
 struct node *trav,*t;
 t=getnode();
 t->data=item;
 if(header->rlink==header && header->llink==header)
 {
  header->rlink=t;
  t->llink=header;
  header->llink=t;
  t->rlink=header;
 }
 else
 {
   trav=header->rlink;
   while(trav->rlink!=header)
   {
    trav=trav->rlink;
   }
   trav->rlink=t;
   t->llink=trav;
   t->rlink=header;
   header->llink=t;
 }
}

void insert_any(int key,int item)
{
  struct node *trav,*t,*ptr;
  trav=header->rlink;
  while(trav->data!=key && trav!=header)
  {
    trav=trav->rlink;
  }
  if(trav==header)
  {
   printf("\nInsertion impossible\n");
  }
  else
  {
   t=getnode();
   t->data=item;
   ptr=trav->rlink;
   trav->rlink=t;
   t->llink=trav;
   t->rlink=ptr;
   ptr->llink=t;
  }
}

void delete_beg()
{
 struct node *x,*ptr;
 if(header->rlink==header)
 {
   printf("\nList empty.\n");
 }
 else
 {
   x=header->rlink;
   ptr=x->rlink;
   header->rlink=x->rlink;
   if(ptr->rlink!=header)
   {
    ptr->rlink->llink=header;
   }
 }
}

void delete_end()
{
 struct node *trav,*ptr;
 if(header->rlink==header && header->llink==header)
 {
   printf("\nList empty.\n");
 }
 else
 {
     trav=header->rlink;
     while(trav->rlink!=header)
     {
      trav=trav->rlink;
     }
     ptr=trav->llink;
     ptr->rlink=header;
     header->llink=ptr;

 }
}

void delete_any(int key)
{
  struct node *trav,*ptr,*f,*r;
  if(header->rlink==header && header->llink==header)
  {
   printf("\nList empty.\n");
  }
  else
  {
   trav=header->rlink;
   while(trav->data!=key && trav!=header)
   {
     trav=trav->rlink;
   }
   if(trav==header)
   {
    printf("\nDeletion impossible.\n");
   }
   else
   {
     f=trav->rlink;
     r=trav->llink;
     r->rlink=f;
     f->llink=r;
   }
  }
}

void search(int item)
{
  int j;
  struct node *trav;
  if(header->rlink==header)
  {
    printf("\nList empty");
  }
  else
  {
    trav=header->rlink;
    j=1;
    while(trav!=header)
    {
      if(trav->data==item)
      {
 printf("\nElement found in position=> %d",j);
 return ;
      }
      trav=trav->rlink;
      j++;
    }
    if(trav==header)
    {
      printf("\nElement not found.");
    }
  }
}

void sorting(int s)
{
  struct node *trav,*ptr;
  int t;
  if(header->rlink==header)
  {
    printf("nList empty");
  }
  else
  {
    for(ptr=header->rlink;ptr->rlink!=header;ptr=ptr->rlink)
    {
      for(trav=ptr->rlink;trav!=header;trav=trav->rlink)
      {
 if(s==1)
 {
 if(ptr->data>trav->data)
 {
   t=ptr->data;
   ptr->data=trav->data;
   trav->data=t;
 }
       }
       else if(s==2)
       {
  if(ptr->datadata)
 {
   t=ptr->data;
   ptr->data=trav->data;
   trav->data=t;
 }
       }
      }
    }
  }
}

void inversion()
{
  struct node *p,*q,*r;
  if(header->rlink==header)
  {
    printf("\nList empty");
  }
  else
  {
    p=header;
    q=header->rlink;
    while(q!=header)
    {
     r=q->rlink;
     q->rlink=p;
     q->llink=r;
     p=q;
     q=r;
    }
    header->rlink=p;
    p->llink=header;
  }
}

void merge_u(struct node *h1,struct node *h2)
{
  struct node *trav,*ptr;
  trav=h1->rlink;
  ptr=h2->rlink;
  if(trav==h1  &&  ptr==h2)
     printf("\nMerging not possible.");
  else
  {
    while(trav->rlink!=h1)
    {
      trav=trav->rlink;
    }
    trav->rlink=ptr;
    ptr->llink=trav;
    while(ptr->rlink!=h2)
    {
      ptr=ptr->rlink;
    }
    ptr->rlink=h1;
    h1->llink=ptr;
    h2->llink=h2;
    h2->rlink=h2;
  }
}

void  merge_sort(struct node *h1,struct node *h2,struct node *h3)
{
 struct node *p1,*p2,*trav,*t;
 p1=h1->rlink;
 p2=h2->rlink;
 h3->rlink=h3;
 h3->llink=h3;
 while(p1!=h1 && p2!=h2)
 {
   t=getnode();
   if(p1->datadata)
   {
     t->data=p1->data;
     p1=p1->rlink;
   }
   else
   {
     t->data=p2->data;
     p2=p2->rlink;
   }
   if(h3->rlink==h3)
   {
    h3->rlink=t;
    t->llink=h3;
    h3->llink=t;
    t->rlink=h3;
    trav=t;
   }
   else
   {
    trav->rlink=t;
    t->llink=trav;
    t->rlink=h3;
    h3->llink=t;
    trav=trav->rlink;
   }
 }
   while(p1!=h1)
   {
    t=getnode();
    t->data=p1->data;
    p1=p1->rlink;
    trav->rlink=t;
    t->llink=trav;
    t->rlink=h3;
    h3->llink=t;
    trav=trav->rlink;
   }
   while(p2!=h2)
   {
    t=getnode();
    t->data=p2->data;
    p2=p2->rlink;
    trav->rlink=t;
    t->llink=trav;
    t->rlink=h3;
    h3->llink=t;
    trav=trav->rlink;
   }

}
void main()
{
 int ch,ch1,ch2,item,key,ch3,s,ch4,ch5,c1;
 struct node *h1,*h2,*h3;
 clrscr();
 h1=getnode();
 h2=getnode();
 h3=getnode();
 h1->rlink=h1;
 h1->llink=h1;
 h2->rlink=h2;
 h2->llink=h2;
 h3->rlink=h3;
 h3->llink=h3;

 while(1)
 {

   printf("\nLinked List Operations:");
   printf("\n1.Linked list-1\n2.Linked list-2\n3.Merging\n4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch4);
   switch(ch4)
   {
     case 1:
     header=h1;
 while(1)
 {
 start :
 printf("\nLINKED LIST-1 OPERATION :");
 printf("\n\t1.Insertion  2.Deletion 3.Traversal 4.Search\n\t5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1");
 printf("\n\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
   printf("\n\nINSERTION:");
   printf("\n\t1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
   printf("\n\nEnter your choice:");
   scanf("%d",&ch1);
   switch(ch1)
   {
   case 1:
   printf("\nEnter the item to be inserted:");
   scanf("%d",&item);
   insert_beg(item);
   break;
   case 2:
   printf("\nEnter the item to be inserted:");
   scanf("%d",&item);
   insert_end(item);
   break;
   case 3:
   printf("\nEnter the item to be inserted:");
   scanf("%d",&item);
   printf("\nEnter the key:");
   scanf("%d",&key);
   insert_any(key,item);
   break;
   case 4:
   break;
   }
   goto start;
   case 2:
   printf("\n\nDELETION:");
   printf("\n\t1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
   printf("\n\nEnter your choice:");
   scanf("%d",&ch2);
   switch(ch2)
   {
   case 1:
   delete_beg();
   break;
   case 2:
   delete_end();
   break;
   case 3:
   printf("\nEnter the data of the node to be deleted:");
   scanf("%d",&key);
   delete_any(key);
   break;
   case 4:
   break;
   }
   goto start;
   case 3:
   printf("\nTraversal:");
   printf("\n\t1.Forward traversal  2.Backward traversal");
   printf("\nEnter yourchoice:");
   scanf("%d",&c1);
   switch(c1)
   {
   case 1:
   fortrav();
   break;
   case 2:
   backtrav();
   break;
   }
   goto start;
   case 4:
   printf("\n\nSEARCHING:");
   printf("\nEnter the element you want to search:");
   scanf("%d",&item);
   search(item);
   goto start;
   case 5:
   printf("\n\nSORTING:");
   printf("\nSorting-> 1.Ascending order 2.Decending order");
   printf("\n\nEnter your choice:");
   scanf("%d",&ch3);
   switch(ch3)
   {
     case 1:
     s=1;
     sorting(s);
     fortrav();
     break;
     case 2:
     s=2;
     sorting(s);
     fortrav();
     break;
   }
   goto start;
   case 6:
   printf("\n\nINVERSION:");
   inversion();
   fortrav();
   goto start;
   case 7:
   clrscr();
   goto start;
   case 8:
   goto end;
  }
  end : break;
 }
 break;
 case 2:
 header=h2;
 while(1)
 {
 start2 :
 printf("\n\nLINKED LIST-2 OPERATION :");
 printf("\n\t1.Insertion  2.Deletion 3.Traversal 4.Search\n\t5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2");
 printf("\n\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
   case 1:
   printf("\n\nINSERTION:");
   printf("\n\t1.Insert begining 2.Insert end 3.Insert any pos 4.Break");
   printf("\n\nEnter your choice:");
   scanf("%d",&ch1);
   switch(ch1)
   {
   case 1:
   printf("\nEnter the item to be inserted:");
   scanf("%d",&item);
   insert_beg(item);
   break;
   case 2:
   printf("\nEnter the item to be inserted:");
   scanf("%d",&item);
   insert_end(item);
   break;
   case 3:
   printf("\nEnter the item to be inserted:");
   scanf("%d",&item);
   printf("\nEnter the key:");
   scanf("%d",&key);
   insert_any(key,item);
   break;
   case 4:
   break;
   }
   goto start2;
   case 2:
   printf("\n\nDELETION:");
   printf("\n\t1.Delete begining 2.Delete end 3.Delete any pos 4.Break");
   printf("\n\nEnter your choice:");
   scanf("%d",&ch2);
   switch(ch2)
   {
   case 1:
   delete_beg();
   break;
   case 2:
   delete_end();
   break;
   case 3:
   printf("\nEnter the data of the node to be deleted:");
   scanf("%d",&key);
   delete_any(key);
   break;
   case 4:
   break;
   }
   goto start2;
   case 3:
   printf("\nTraversal");
   printf("\n\t1.Forward traversal 2.Backward traversal");
   printf("\n\nEnter yourchoice:");
   scanf("%d",&c1);
   switch(c1)
   {
   case 1:
  fortrav();
  break;
   case 2:
   backtrav();
   break;
   }
   goto start2;
   case 4:
   printf("\n\nSEARCHING:");
   printf("\nEnter the element you want to search:");
   scanf("%d",&item);
   search(item);
   goto start2;
   case 5:
   printf("\n\nSORTING:");
   printf("\nSorting-> 1.Ascending order 2.Decending order");
   printf("\n\nEnter your choice:");
   scanf("%d",&ch3);
   switch(ch3)
   {
     case 1:
     s=1;
     sorting(s);
     fortrav();
     break;
     case 2:
     s=2;
     sorting(s);
     fortrav();
     break;
   }
   goto start2;
   case 6:
   printf("\n\nINVERSION:");
   inversion();
   fortrav();
   goto start2;
   case 7:
   clrscr();
   goto start2;
   case 8:
   goto end2;
  }
  end2 : break;
 }
 break;
 case 3:
 printf("\n\nMERGING:=>");
 printf("1.Unsorted 2.Sorted list");
 printf("\n\nEnter your choice:");
 scanf("%d",&ch5);
 switch(ch5)
 {
   case 1:

   merge_u(h1,h2);
   header=h1;
   fortrav();
   break;
   case 2:

   merge_sort(h1,h2,h3);
   header=h3;
   fortrav();
   break;
 }
 break;
 case 4:
 exit(0);
}
}
 getch();
}


 OUTPUT :
 
Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:1

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:1

Enter the item to be inserted:22

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:
1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:66

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:44

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:3

Enter the item to be inserted:88

Enter the key:66

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice:1

LINK  LIST :

  22  66  88  44

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:4


SEARCHING:
Enter the element you want to search:66

Element found in position=> 2
LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:6


INVERSION:
LINK  LIST :

  44  88  66  22

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:5


SORTING:
Sorting-> 1.Ascending order 2.Decending order

Enter your choice:1

LINK  LIST :

  22  44  66  88

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:5


SORTING:
Sorting-> 1.Ascending order 2.Decending order

Enter your choice:2

LINK  LIST :

  88  66  44  22

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:2


DELETION:
        1.Delete begining 2.Delete end 3.Delete any pos 4.Break

Enter your choice:1

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice:1

LINK  LIST :

  66  44  22

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:2


DELETION:
        1.Delete begining 2.Delete end 3.Delete any pos 4.Break

Enter your choice:2

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice: 1

LINK  LIST :

  66  44

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:1

Enter the item to be inserted:22
LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:88

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice: 2

LINK  LIST :

  88  44  66  22

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice:1

LINK  LIST :
  22  66  44  88

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:2


DELETION:
        1.Delete begining 2.Delete end 3.Delete any pos 4.Break

Enter your choice:1

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice:1

LINK  LIST :

  66  44  88

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:2


DELETION:
        1.Delete begining 2.Delete end 3.Delete any pos 4.Break

Enter your choice:3

Enter the data of the node to be deleted:44

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice:1

LINK  LIST :

  66  88

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:44

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:62

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:3

Traversal:
        1.Forward traversal  2.Backward traversal
Enter yourchoice:1

LINK  LIST :

  66  88  44  62

LINKED LIST-1 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-1

Enter your choice:8

Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:2


LINKED LIST-2 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:1

Enter the item to be inserted:11


LINKED LIST-2 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:33


LINKED LIST-2 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2

Enter your choice:1


INSERTION:
        1.Insert begining 2.Insert end 3.Insert any pos 4.Break

Enter your choice:2

Enter the item to be inserted:55

LINKED LIST-2 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2

Enter your choice:3

Traversal
        1.Forward traversal 2.Backward traversal

Enter yourchoice:1

LINK  LIST :

  11  33  55


LINKED LIST-2 OPERATION :
        1.Insertion  2.Deletion 3.Traversal 4.Search
        5.Sorting  6.Inversion  7.Clrscr  8.Exit from LL-2

Enter your choice:8

Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:3


MERGING:=>1.Unsorted 2.Sorted list

Enter your choice:2

LINK  LIST :

  11  33  44  55  62  66  88

Linked List Operations:
1.Linked list-1
2.Linked list-2
3.Merging
4.Exit
Enter your choice:3


MERGING:=>1.Unsorted 2.Sorted list

Enter your choice:1

LINK  LIST :

  66  88  44  62  11  33  55