Single Linked List Operation

Wrote by Post Comment 




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

Tags:

Share:

0 comments