Singly Linked List
Program for various operations that can be done on a Singly Linked List is given below:
/*Program for Singly Linked List*/
/*Operations on Linked List*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct list
{int n;
struct list *next;
}list;
list *createnode()
{list *temp;
temp=(list*)malloc(sizeof(list));
return temp;
}
list *makenode(int x)
{list *temp;
temp=createnode();
temp->n=x;
temp->next=NULL;
return temp;
}
/*11 13 15 17*/
/*Sorted search on a list sorted in ascending order*/
void sortedsearch(list *head,int val)
{
list *temp;
if(head==NULL)
{printf(“List is empty.”);
return;
}
temp=head;
while((temp->n!=val) && (val>temp->n) && (temp!=NULL))
temp=temp->next;
if(temp->n==val)
printf(“nNumber found.”);
else
printf(“nNumber not found.”);
}
/*UnSorted search on an unsorted list*/
void unsortedsearch(list *head,int val)
{
list *temp;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
temp=head;
/*searches for equality until number is found*/
/*best case is when first number is the required number*/
/*worst case is number does not exist*/
/*or number is present at last position in list*/
while(temp!=NULL)
{if(temp->n==val)
{printf(“nNumber found.”);
return;
}
temp=temp->next;
}
printf(“nNumber not found.”);
}
/*Insertion at beginning*/
list *insertbegin(list *head,int x)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{ptr->next=head;
head=ptr;
}
return head;
}
/*Insertion at end*/
list *insertend(list *head,int x)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
return head;
}
/*Insertion after given element/node*/
list *insertafternode(list *head,int x,int node)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{printf(“nGiven node does not exist. List empty”);
}
else
{temp=head;
while(temp->n!=node)
temp=temp->next;
if(temp==NULL)
{printf(“nGiven node not found in list.”);
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
return head;
}
/*Insertion before given element/node*/
list *insertbeforenode(list *head,int x,int node)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{printf(“nGiven node does not exist. List empty”);
}
else
{if(head->n==node)
{ptr->next=head;
head=ptr;
return head;
}
else
{temp=head;
while(temp->next->n!=node)
temp=temp->next;
if(temp==NULL)
{printf(“nGiven node not found in list.”);
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}
return head;
}
/*function to delete first node*/
list *delfirstnode(list *head)
{list *temp;
if(head==NULL)
{printf(“nList is empty!”);
return head;
}
temp=head;
head=head->next;
free(temp);
return head;
}
/*function to delete last node*/
list *dellastnode(list *head)
{list *ptr,*temp;
if(head==NULL)
{printf(“nList is empty!”);
return head;
}
if(head->next==NULL)
{temp=head;
head=NULL;
free(temp);
return head;
}
temp=head;
if(temp->next->next==NULL)
{ptr=temp->next;
temp->next=NULL;
free(ptr);
return head;
}
while(temp->next->next!=NULL)
temp=temp->next;
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
return head;
}
/*function to delete node after a given node*/
list *delafternode(list *head,int node)
{
list *temp,*ptr;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
/*locate given node in the list*/
for(temp=head;((temp->n!=node) && (temp!=NULL));temp=temp->next);
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
return head;
}
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
return head;
}
/*function to delete node before a given node*/
list *delbeforenode(list *head,int node)
{
list *temp,*temp1,*ptr;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->n==node)
{printf(“nCannot delete before first node.”);
return head;
}
/*locate given node in the list*/
temp=head;
while((temp->next->n!=node) && (temp!=NULL))
{temp1=temp;
temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
return head;
}
ptr=temp1->next;
temp1->next=ptr->next;
free(ptr);
return head;
}
/*In-order traversal*/
void displaylist(list *head)
{
list *temp;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
temp=head;
while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}
printf(“bb “);
}
/*Reverse order traversal*/
void displaylistreverse(list *head)
{
list *temp;
int i,j,count=0;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
for(temp=head;temp!=NULL;temp=temp->next,count++);
for(i=1;i<=count;i++)
{temp=head;
for(j=1;j<=count-i;j++)
{temp=temp->next;
}
printf(“%d->”,temp->n);
}
printf(“bb “);
}
/*Reversing list*/
list *reverselist(list *head)
{
list *temp,*head1=NULL,*ptr,*temp1;
int i,j,count=0;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
for(temp=head;temp!=NULL;temp=temp->next,count++);
for(i=1;i<=count;i++)
{temp=head;
for(j=1;j<=count-i;j++)
{temp=temp->next;
}
printf(“%d->”,temp->n);
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
if(head1==NULL)
{head1=ptr;
}
else
{temp1=head1;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
printf(“bb “);
temp=head;
while(temp!=NULL)
{ptr=temp;
temp=temp->next;
free(ptr);
}
return head1;
}
/*Disposing linked list*/
list *dispose(list *head)
{
list *ptr,*temp;
printf(“nDisposing the linked list.”);
printf(“nPress any key to continue…”);
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}
/*Concatenating list*/
list *concatenate(list *head1,list *head2)
{
list *temp=head1;
while(temp->next!=NULL)
temp=temp->next;
temp->next=head2;
return head1;
}
/*Splitting from middle*/
void splitmiddle(list *head)
{
list *head1=NULL,*temp;
int i,count=0;
for(temp=head;temp!=NULL;temp=temp->next)
count++;
temp=head;
/*i is 1 since temp is already at first node*/
for(i=1;i<count/2;i++)
temp=temp->next;
head1=temp->next;
temp->next=NULL;
printf(“nSplitting list task over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}
/*Splitting alternate nodes*/
void splitalternatenodes(list *head)
{
list *head1=NULL,*head2=NULL,*temp,*temp1,*ptr;
int i;
for(i=1,temp=head;temp!=NULL;temp=temp->next,i++)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
/*creating odd list*/
if(i%2!=0)
{if(head1==NULL)
head1=ptr;
else
{temp1=head1;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
else /*creating even list*/
{if(head2==NULL)
head2=ptr;
else
{temp1=head2;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
}
printf(“nAlternate node Splitting list task over.”);
printf(“nDisplaying first list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head2;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}
/*Splitting after a given node*/
void splitafternode(list *head,int node)
{list *temp,*head1=NULL;
temp=head;
while((temp!=NULL)&&(temp->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->n==node)
{head1=temp->next;
temp->next=NULL;
}
printf(“nSplit task after given node is over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}
/*Split before given node*/
void splitbeforenode(list *head,int node)
{list *temp,*head1=NULL;
temp=head;
/*if there is only one node*/
if(temp->n==node)
{head1=temp;
head=NULL;
}
else
{
while((temp!=NULL)&&(temp->next->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->next->n==node)
{head1=temp->next;
temp->next=NULL;
}
}
printf(“nSplit task before given node is over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}
list *merge(list *head1,list *head2)
{list *head=NULL,*temp1,*temp2,*ptr,*tmp;
temp1=head1;
temp2=head2;
while((temp1!=NULL)&&(temp2!=NULL))
{if(temp1->n<temp2->n)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp1=temp1->next;
}
else
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp2->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
}
while(temp1!=NULL)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp1=temp1->next;
}
while(temp2!=NULL)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp2->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
return head;
}
void main()
{
list *head=NULL;
list *head1=NULL,*head2=NULL;
int ch,num,node;
while(1)
{
clrscr();
printf(“nLinked List Menu”);
printf(“nn1. Insert at beginning”);
printf(“n2. Insert at end”);
printf(“n3. Insert after given node”);
printf(“n4. Insert before given node”);
printf(“n5. In-order display”);
printf(“n6. Reversal display”);
printf(“n7. Sorted Search”);
printf(“n8. Unsorted Search”);
printf(“n9. Delete first node”);
printf(“n10. Delete last node”);
printf(“n11. Delete after node”);
printf(“n12. Delete before node”);
printf(“n13. Reverse list”);
printf(“n14. Dispose list”);
printf(“n15. Create first list”);
printf(“n16. Create second list”);
printf(“n17. Concatenate list”);
printf(“n18. Display concatenated list.”);
printf(“n19. Split list from middle.”);
printf(“n20. Split alternate nodes.”);
printf(“n21. Split after given node.”);
printf(“n22. Split before given node.”);
printf(“n23. Merge two lists.”);
printf(“n24. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter any number?”);
scanf(“%d”,&num);
head=insertbegin(head,num);
break;
case 2: printf(“nEnter any number?”);
scanf(“%d”,&num);
head=insertend(head,num);
break;
case 3: printf(“nEnter any number?”);
scanf(“%d”,&num);
printf(“nEnter the node after which to insert?”);
scanf(“%d”,&node);
head=insertafternode(head,num,node);
break;
case 4: printf(“nEnter any number?”);
scanf(“%d”,&num);
printf(“nEnter the node before which to insert?”);
scanf(“%d”,&node);
head=insertbeforenode(head,num,node);
break;
case 5: printf(“nIn-order display:”);
displaylist(head);
break;
case 6: printf(“nReverse order display:”);
displaylistreverse(head);
break;
case 7: printf(“nEnter number to search?”);
scanf(“%d”,&num);
sortedsearch(head,num);
break;
case 8: printf(“nEnter number to search?”);
scanf(“%d”,&num);
unsortedsearch(head,num);
break;
case 9:
head=delfirstnode(head);
break;
case 10:
head=dellastnode(head);
break;
case 11:
printf(“nEnter the node after which to delete?”);
scanf(“%d”,&node);
head=delafternode(head,node);
break;
case 12:
printf(“nEnter the node before which to delete?”);
scanf(“%d”,&node);
head=delbeforenode(head,node);
break;
case 13:
head=reverselist(head);
break;
case 14:
head=dispose(head);
break;
case 15:
printf(“nEnter number?”);
scanf(“%d”,&num);
head1=insertend(head1,num);
break;
case 16:
printf(“nEnter number?”);
scanf(“%d”,&num);
head2=insertend(head2,num);
break;
case 17:
printf(“Concatenating lists.”);
printf(“Press any key to continue…!”);
head1=concatenate(head1,head2);
break;
case 18:
printf(“nConcatenated list:”);
displaylist(head1);
break;
case 19:
splitmiddle(head);
break;
case 20:
splitalternatenodes(head);
break;
case 21:
printf(“nEnter the node after which to split?”);
scanf(“%d”,&node);
splitafternode(head,node);
break;
case 22:
printf(“nEnter the node before which to split?”);
scanf(“%d”,&node);
splitbeforenode(head,node);
break;
case 23:
printf(“nMerging two sorted lists.”);
printf(“nPress any key to continue…”);
head=merge(head1,head2);
break;
case 24:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}