- Click below to download Unit 1 programs in pdf file: -
Unit 1
/* 1. Write program to implement following operations using
Singly link list
• Insert at first
• Insert at Last
• Insert at specified location (Before or After the Node)
• Delete from first
• Delete from last
• Delete any specified node
• Traversal
• Sorting
• Splitting
• Merging
• Counting Operations( Total no. of nodes, even and odd no. of nodes)
*/
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
} *first=NULL;
void create()
{
struct node *curr;
int i,val;
printf("\nEnter Number of Nodes:");
scanf("%d", &val);
if(val < 1)
{
printf("Invalid Argument:");
return;
}
for(i=1;i<=val;i++)
{
if(first==NULL)
{
first=(struct node *)malloc(sizeof(struct node));
curr=first;
}
else
{
curr->next=(struct node *)malloc(sizeof(struct node));
curr=curr->next;
}
printf("Enter Value:");
scanf("%d", &curr->data);
curr->next=NULL;
}
}
/** Traversal **/
void display()
{
struct node *curr;
if(first==NULL)
{
printf("Link-List is Empty:");
return;
}
curr=first;
while(curr!=NULL)
{
printf("%d-->", curr->data);
curr=curr->next;
}
}
/** Insert at Last **/
void insatend(int val)
{
struct node *new1, *curr;
if(first == NULL)
{
printf("Link-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data=val;
new1->next=NULL;
curr=first;
while(curr->next!=NULL)
curr=curr->next;
curr->next=new1;
}
/** Insert at first **/
void insatbeg(int val)
{
struct node *new1;
if(first == NULL)
{
printf("Link-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data=val;
new1->next=first;
first=new1;
}
/** Insert After **/
void insaft(int key, int val)
{
struct node *curr, *new1;
if(first==NULL)
{
printf("\nLink-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data=val;
new1->next=NULL;
curr=first;
while(curr!=NULL && curr->data!=key )
curr=curr->next;
if(curr==NULL)
{
printf("\nKey does not Exists:");
return;
}
new1->next=curr->next;
curr->next=new1;
}
/** Insert Before **/
void insbfr(int key, int val)
{
struct node *curr, *prev, *new1;
if(first == NULL)
{
printf("\nLink-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data =val;
new1->next =NULL;
curr=first;
if(first->data==key)
{
new1->next=first;
first=new1;
return;
}
while(curr!=NULL && curr->data!=key)
{
prev=curr;
curr=curr->next;
}
if(curr==NULL)
{
printf("\nKey does not Exists:");
return;
}
prev->next=new1;
new1->next=curr;
}
/** Delete from first **/
void deleteFirstNode()
{
struct node *toDelete;
if(first == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = first;
first = first->next;
printf("\nData deleted = %d\n", toDelete->data);
free(toDelete);
printf("SUCCESSFULLY DELETED FIRST NODE FROM LIST\n");
}
}
/** Delete from last **/
void deleteLastNode()
{
struct node *toDelete, *secondLastNode;
if(first == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = first;
secondLastNode = first;
while(toDelete->next != NULL)
{
secondLastNode = toDelete;
toDelete = toDelete->next;
}
if(toDelete == first)
{
first = NULL;
}
else
{
secondLastNode->next = NULL;
}
free(toDelete);
printf("SUCCESSFULLY DELETED LAST NODE OF LIST\n");
}
}
/** Deleting node **/
void delnode(int val)
{
struct node *curr, *prev;
if(first==NULL)
{
printf("\nLink-List is Empty:");
return;
}
curr=first;
if(first->data==val)
{
first=first->next;
free(curr);
return;
}
while(curr!=NULL && curr->data != val)
{
prev=curr;
curr=curr->next;
}
if(curr==NULL)
{
printf("\nValue doesn't Exists:");
return;
}
prev->next = curr->next;
free(curr);
}
/** Sorting **/
void sortlnklst()
{
struct node *i, *j;
int tmp;
if(first == NULL)
{
printf("\nLink-List is Empty:");
return;
}
i=first;
while(i->next !=NULL)
{
j=i->next;
while(j!=NULL)
{
if(j->data < i->data)
{
tmp=i->data;
i->data=j->data;
j->data=tmp;
}
j=j->next;
}
i=i->next;
}
}
void main()
{
int val, key, ch;
struct node *tmp;
do
{
printf("\n|--------MENU--------|");
printf("\n 1. Create:");
printf("\n 2. Display:");
printf("\n 3. Insert At End:");
printf("\n 4. Insert At Begin:");
printf("\n 5. Insert After:");
printf("\n 6. Insert Before:");
printf("\n 7. Delete from first :");
printf("\n 8. Delete from last :");
printf("\n 9. Delete any specified node:");
printf("\n 10. Sorting :");
printf("\n 11.Exit:");
printf("\n|--------------------|");
printf("\n Enter Your Choice:");
scanf("%d", &ch);
if(ch==1)
{
create();
}
else if(ch==2)
{
printf("\n");
display();
}
else if(ch==3)
{
printf("\nEnter Value:");
scanf("%d", &val);
insatend(val);
}
else if(ch==4)
{
printf("\nEnter Value:");
scanf("%d", &val);
insatbeg(val);
}
else if(ch==5)
{
printf("\nEnter Key:");
scanf("%d", &key);
printf("\nEnter Value:");
scanf("%d", &val);
insaft(key, val);
}
else if(ch==6)
{
printf("\nEnter Key:");
scanf("%d", &key);
printf("\nEnter Value:");
scanf("%d", &val);
insbfr(key, val);
}
else if(ch==7)
{
deleteFirstNode();
}
else if(ch==8)
{
deleteLastNode();
}
else if(ch==9)
{
printf("\nEnter Value to DELETE:");
scanf("%d", &val);
delnode(val);
}
else if(ch==10)
{
sortlnklst();
}
else if(ch==11)
{
printf("\nGood Bye:");
break;
}
else
{
printf("\nInvalid Choice:");
}
}while(ch!=10);
}
/* 2. Write program to implement following operations using
Doubly link list
• Insert at first
• Insert at Last
• Insert at specified location (Before or After the Node)
• Delete from first
• Delete from last
• Delete any specified node
• Traversal
• Sorting
• Splitting
• Merging
• Counting Operations( Total no. of nodes, even and odd no. of nodes)
*/
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
} *first=NULL, *second=NULL;
void create()
{
struct node *curr;
int i,val;
printf("\nEnter Number of Nodes:");
scanf("%d", &val);
if(val < 1)
{
printf("Invalid Argument:");
return;
}
for(i=1;i<=val;i++)
{
if(first==NULL)
{
first=(struct node *)malloc(sizeof(struct node));
curr=first;
}
else
{
curr->next=(struct node *)malloc(sizeof(struct node));
curr=curr->next;
}
printf("Enter Value:");
scanf("%d", &curr->data);
curr->next=NULL;
}
}
/** Traversal **/
void display()
{
struct node *curr;
int ch;
printf("Enter Number of Link-List to be displayed(1-2):");
scanf("%d", &ch);
if(ch==1)
curr=first;
else
curr=second;
if(curr==NULL)
{
printf("Link-List is Empty:");
return;
}
while(curr!=NULL)
{
printf("%d-->", curr->data);
curr=curr->next;
}
}
/** Insert at Last **/
void insatend(int val)
{
struct node *new1, *curr;
if(first == NULL)
{
printf("Link-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data=val;
new1->next=NULL;
curr=first;
while(curr->next!=NULL)
curr=curr->next;
curr->next=new1;
}
/** Insert at first **/
void insatbeg(int val)
{
struct node *new1;
if(first == NULL)
{
printf("Link-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data=val;
new1->next=first;
first=new1;
}
/** Insert After **/
void insaft(int key, int val)
{
struct node *curr, *new1;
if(first==NULL)
{
printf("\nLink-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data=val;
new1->next=NULL;
curr=first;
while(curr!=NULL && curr->data!=key )
curr=curr->next;
if(curr==NULL)
{
printf("\nKey does not Exists:");
return;
}
new1->next=curr->next;
curr->next=new1;
}
/** Insert Before **/
void insbfr(int key, int val)
{
struct node *curr, *prev, *new1;
if(first == NULL)
{
printf("\nLink-List is Empty:");
return;
}
new1=(struct node *)malloc(sizeof(struct node));
new1->data =val;
new1->next =NULL;
curr=first;
if(first->data==key)
{
new1->next=first;
first=new1;
return;
}
while(curr!=NULL && curr->data!=key)
{
prev=curr;
curr=curr->next;
}
if(curr==NULL)
{
printf("\nKey does not Exists:");
return;
}
prev->next=new1;
new1->next=curr;
}
/** Delete any specified node **/
void delnode(int val)
{
struct node *curr, *prev;
if(first==NULL)
{
printf("\nLink-List is Empty:");
return;
}
curr=first;
if(first->data==val)
{
first=first->next;
free(curr);
return;
}
while(curr!=NULL && curr->data != val)
{
prev=curr;
curr=curr->next;
}
if(curr==NULL)
{
printf("\nValue doesn't Exists:");
return;
}
prev->next = curr->next;
free(curr);
}
/** Sorting **/
void sortlnklst()
{
struct node *i, *j;
int tmp;
if(first == NULL)
{
printf("\nLink-List is Empty:");
return;
}
i=first;
while(i->next !=NULL)
{
j=i->next;
while(j!=NULL)
{
if(j->data < i->data)
{
tmp=i->data;
i->data=j->data;
j->data=tmp;
}
j=j->next;
}
i=i->next;
}
}
/** Reverse Link-List **/
struct node * reverselnklst(struct node *d)
{
struct node *tmp;
if(d->next ==NULL)
{
first=d;
return d;
}
tmp=reverselnklst(d->next);
tmp->next=d;
return d;
}
/** Splitting **/
void split(int val)
{
struct node *curr, *prev;
if(first==NULL)
{
printf("Link-List is Empty:");
return;
}
curr=first;
while(curr!=NULL && curr->data!=val)
{
prev=curr;
curr=curr->next;
}
if(curr==NULL)
{
printf("\nValue does not Exists:");
return;
}
second=curr;
prev->next=NULL;
}
/** Merging **/
void join()
{
struct node *curr;
if(first==NULL || second ==NULL)
{
printf("\nJoin is not possible:");
return;
}
curr=first;
while(curr->next!=NULL)
curr=curr->next;
curr->next=second;
second=NULL;
}
void main()
{
int val, key, ch;
struct node *tmp;
do
{
printf("\n|--------MENU--------|");
printf("\n 1. Create:");
printf("\n 2. Display:");
printf("\n 3. Insert At first:");
printf("\n 4. Insert At last:");
printf("\n 5. Insert After:");
printf("\n 6. Insert Before:");
printf("\n 7. Delete any specified node:");
printf("\n 8. Sort:");
printf("\n 9. Reverse:");
printf("\n 10.Split:");
printf("\n 11.Join:");
printf("\n 12.Exit:");
printf("\n|--------------------|");
printf("\n Enter Your Choice:");
scanf("%d", &ch);
if(ch==1)
{
create();
}
else if(ch==2)
{
printf("\n");
display();
}
else if(ch==3)
{
printf("\nEnter Value:");
scanf("%d", &val);
insatend(val);
}
else if(ch==4)
{
printf("\nEnter Value:");
scanf("%d", &val);
insatbeg(val);
}
else if(ch==5)
{
printf("\nEnter Key:");
scanf("%d", &key);
printf("\nEnter Value:");
scanf("%d", &val);
insaft(key, val);
}
else if(ch==6)
{
printf("\nEnter Key:");
scanf("%d", &key);
printf("\nEnter Value:");
scanf("%d", &val);
insbfr(key, val);
}
else if(ch==7)
{
printf("\nEnter Value to DELETE:");
scanf("%d", &val);
delnode(val);
}
else if(ch==8)
{
sortlnklst();
}
else if(ch==9)
{
tmp=reverselnklst(first);
tmp->next=NULL;
}
else if(ch==10)
{
printf("\nEnter value to split:");
scanf("%d", &key);
split(key);
}
else if(ch==11)
{
join();
}
else if(ch==12)
{
printf("\nGood Bye:");
break;
}
else
{
printf("\nInvalid Choice:");
}
}while(ch!=12);
}
0 Comments