Double Linked List

Wrote by Unknown 02:10 Post Comment




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

Tags: Linked List

Share:

0 comments