Linked list implementation and operations
Linked list operation
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct student
{
char name[20];
int roll;
struct student *link;
}student;
student *insbeg(student *head,char *name,int roll)
{
student *temp;
temp=(student *)malloc(sizeof(struct student));
temp->roll=roll;
temp->link=NULL;
strcpy(temp->name,name);
if(head==NULL)
{
head=temp;
return head;
}
temp->link=head;
head=temp;
return head;
}
student *insatend(student *head,char *name,int roll)
{
student *temp,*p;
temp=(student *)malloc(sizeof(struct student));
temp->roll=roll;
temp->link=NULL;
strcpy(temp->name,name);
if(head==NULL)
{
head=temp;
return head;
}
p=head;
while(p->link!=NULL)
p=p->link;
p->link=temp;
return head;
}
void search(student *head,char *name,int roll)
{
student *p=head;
int pos=1;
while(p)
{
if(p->roll==roll && !strcmp(p->name,name))
{
printf("\nItemp found with Name %s \tRoll %d ",p->name,p->roll);
return ;
}
p=p->link;
pos++;
}
printf("\nItemp not found");
}
student *insempty(student *head,char *name,int roll)
{
student *temp;
temp=(student *)malloc(sizeof(struct student));
temp->roll=roll;
temp->link=NULL;
strcpy(temp->name,name);
if(head==NULL)
{
head=temp;
return head;
}
printf("\nlist already contains some data");
return head;
}
void display(student *head)
{
student *p=head;
while(p!=NULL)
{
printf("\nName : %s \tRoll : %d ",p->name,p->roll);
p=p->link;
}
}
student *insertafter(student *head,char *name,int roll,char *nname,int nroll)
{
student *temp,*p=head;
while(p)
{
if(p->roll==roll && !strcmp(p->name,name))
{
printf("\nItemp found with Name %s \tRoll %d ",p->name,p->roll);
temp=(student *)malloc(sizeof(struct student));
temp->roll=nroll;
temp->link=NULL;
strcpy(temp->name,nname);
temp->link=p->link;
p->link=temp;
return head;
}
p=p->link;
}
printf("\nItemp not found");
return head;
}
student *insertbefore(student *head,char *name,int roll,char *nname,int nroll)
{
student *temp,*p=head,*q=head;
temp=(student *)malloc(sizeof(struct student));
temp->roll=nroll;
temp->link=NULL;
temp->link=NULL;
strcpy(temp->name,nname);
if(p->roll==roll && !strcmp(p->name,name))
{
printf("\nItemp found with Name %s \tRoll %d ",p->name,p->roll);
temp->link=p;
head=temp;
return head;
}
while(p)
{
if(p->roll==roll && !strcmp(p->name,name))
{
temp->link=p;
q->link=temp;
return head;
}
q=p;
p=p->link;
}
printf("\nItemp not found");
free(temp);
return head;
}
struct student *deletfirst(student *head)
{
student *temp=head;head=head->link;
free(temp);
return head;
}
student *deletbefore(student *head,char *name,int roll)
{
student *p=head,*q=head;
if(p->roll==roll && !strcmp(p->name,name))
{
printf("\nItem is the first node so can't delete ");
return head;
}
p=head->link;
if(p->roll==roll && !strcmp(p->name,name))
{
free(head);
head=p;
return head;
}
while(p)
{
if(p->link->roll==roll && !strcmp(p->link->name,name))
{
q->link=p->link;
free(p);
return head;
}
q=p;
p=p->link;
}
printf("\nItemp not found");
return head;
}
student *deletafter(student *head,char *name,int roll)
{
student *p=head,*q;
while(p->link)
{
if(p->roll==roll && !strcmp(p->name,name))
{
q=p->link;
p->link=p->link->link;
free(q);
return head;
}
p=p->link;
}
if(p->roll==roll && !strcmp(p->name,name))
{
printf("\nthis is the last item so deletion can't be performed of a node after this");
return head;
}
printf("\nItemp not found");
return head;
}
student *deletkey(student *head,char *name,int roll)
{
student *p=head,*q;
if(p->roll==roll && !strcmp(p->name,name))
{
head=p->link;
free(p);
return head;
}
while(p)
{
if(p->roll==roll && !strcmp(p->name,name))
{
q->link=p->link;
free(p);
return head;
}
q=p;
p=p->link;
}
printf("\nItemp not found");
return head;
}
void main()
{
int roll,ch,nroll;
char name[20],nname[20];
student *head=NULL,*p=head;
printf("\n1.insertion at begining\t2.insertion at end\n3.insertion in empty\t4.insertion in between\n5.display\t\t6.search item\t7.insert after item\t8.insert before item\t9.delet first node\t10.delet before\t11.delet after\t12.delet key\t13.exit");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
head=insbeg(head,name,roll);
break;
case 2: printf("Enter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
head=insatend(head,name,roll);
break;
case 3: printf("Enter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
head=insempty(head,name,roll);
break;
case 5: printf("\nContent of list ");
display(head);
break;
case 6: printf("Enter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
search(head,name,roll);
break;
case 7: printf("After whom \nEnter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
printf("To who\tEnter Name :");
fflush(stdin);
gets(nname);
printf("Enter Roll :");
scanf("%d",&nroll);
head=insertafter(head,name,roll,nname,nroll);
break;
case 8: printf("Before whom \nEnter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
printf("To who\tEnter Name :");
fflush(stdin);
gets(nname);
printf("Enter Roll :");
scanf("%d",&nroll);
head=insertbefore(head,name,roll,nname,nroll);
break;
case 9 :head=deletfirst(head);
break;
case 10:printf("\nbefore whom");
printf("\nEnter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
head=deletbefore(head,name,roll);
break;
case 11:printf("\nAfter whom");
printf("\nEnter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
head=deletafter(head,name,roll);
break;
case 12:printf("\nTo whom");
printf("\nEnter Name :");
fflush(stdin);
gets(name);
printf("Enter Roll :");
scanf("%d",&roll);
head=deletkey(head,name,roll);
break;
case 13: exit(1);
}
}
while(head)
{
p=head->link;
free(head);
head=p;
}
}
program for reversing linked list
#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct student { char name[20]; int roll; struct student *link; }student; student *revers(student *head) { student *curhead,*s=curhead=head,*q=curhead->link,*r=q->link; while(r) { q->link=curhead; s->link=r; curhead=q; q=r; r=r->link; } q->link=curhead; s->link=NULL; return q; } student *insbeg(student *head,char *name,int roll) { student *temp; temp=(student *)malloc(sizeof(struct student)); temp->roll=roll; temp->link=NULL; strcpy(temp->name,name); if(head==NULL) { head=temp; return head; } temp->link=head; head=temp; return head; } void display(student *head) { student *p=head; while(p!=NULL) { printf("\nName : %s \tRoll : %d ",p->name,p->roll); p=p->link; } } void main() { int roll,ch; char name[20]; student *head=NULL,*p=head; printf("Enter 1 to insert 2 to display 3 to reverse linked list 4 to exit"); while(1) { printf("\nEnter your choice : "); scanf("%d",&ch); switch(ch) { case 1: printf("Enter Name :"); fflush(stdin); gets(name); printf("Enter Roll :"); scanf("%d",&roll); head=insbeg(head,name,roll); break; case 2: printf("\nContent of list "); display(head); break; case 3: head=revers(head); break; case 4: exit(1); } } while(head) { p=head->link; free(head); head=p; } }Program to implement Doubly linked list and operation
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct student
{
int info;
struct student *next;
struct student *prev;
}student;
student *insbeg(student *head,int info)
{
student *temp;
temp=(student *)malloc(sizeof(struct student));
temp->info=info;
temp->prev=NULL;
temp->next=NULL;
if(head==NULL)
{
head=temp;
return head;
}
temp->next=head;
head->prev=temp;
head=temp;
return head;
}
void display(student *head)
{
student *p=head;
while(p!=NULL)
{
printf("\nInfo : %d ",p->info);
p=p->next;
}
}
void displayrev(student *head)
{
student *p=head;
while(p->next)
p=p->next;
while(p!=NULL)
{
printf("\nInfo : %d ",p->info);
p=p->prev;
}
}
student *insatend(student *head,int info)
{
student *temp,*p;
temp=(student *)malloc(sizeof(struct student));
temp->info=info;
temp->next=NULL;
temp->prev=NULL;
if(head==NULL)
{
head=temp;
return head;
}
p=head;
while(p->next!=NULL)
p=p->next;
p->next=temp;
temp->prev=p;
return head;
}
void search(student *head,int info)
{
student *p=head;
int pos=1;
while(p)
{
if(p->info==info)
{
printf("\nitem found with Info : %d and position %d ",p->info,pos);
return ;
}
p=p->next;
pos++;
}
printf("\nItemp not found");
}
student *insempty(student *head,int info)
{
student *temp;
temp=(student *)malloc(sizeof(struct student));
temp->info=info;
temp->next=NULL;
temp->prev=NULL;
if(head==NULL)
{
head=temp;
return head;
}
printf("\nlist already contains some data");
return head;
}
student *insertafter(student *head,int info,int ninfo)
{
student *temp,*p=head;
while(p)
{
if(p->info==info)
{
printf("\nItemp found with Info : %d",p->info);
temp=(student *)malloc(sizeof(struct student));
temp->info=ninfo;
temp->next=NULL;
temp->prev=NULL;
temp->next=p->next;
temp->prev=p;
if(p->next)
{
p->next->prev=temp;
}
p->next=temp;
return head;
}
p=p->next;
}
printf("\nItemp not found");
return head;
}
student *insertbefore(student *head,int info,int ninfo)
{
student *temp,*p=head;
temp=(student *)malloc(sizeof(struct student));
temp->info=ninfo;
temp->next=NULL;
temp->prev=NULL;
if(p->info==info)
{
printf("\nItemp found with Info : %d",p->info);
temp->next=p;
p->prev=temp;
return temp;
}
while(p)
{
if(p->info==info)
{
printf("\nItemp found with Info : %d",p->info);
temp->prev=p->prev;
temp->next=p;
p->prev->next=temp;
p->prev=temp;
return head;
}
p=p->next;
}
printf("\nItemp not found");
free(temp);
return head;
}
struct student *deletfirst(student *head)
{
student *temp=head;head=head->next;
head->prev=NULL;
free(temp);
return head;
}
student *deletbefore(student *head,int info)
{
student *p=head,*q=head;
if(p->info==info)
{
printf("\nItem is the first node so can't delete ");
return head;
}
p=head->next;
if(p->info==info)
{
free(head);
head=p;
p->prev=NULL;
return head;
}
while(p)
{
if(p->info==info)
{
q=p->prev;
p->prev->prev->next=p;
p->prev=p->prev->prev;
free(q);
return head;
}
p=p->next;
}
printf("\nItemp not found");
return head;
}
student *deletafter(student *head,int info)
{
student *p=head,*q;
while(p->next)
{
if(p->info==info)
{
q=p->next;
if(p->next->next)
p->next->next->prev=p;
p->next=p->next->next;
free(q);
return head;
}
p=p->next;
}
if(p->info==info)
{
printf("\nthis is the last item so deletion can't be performed of a node after this");
return head;
}
printf("\nItemp not found");
return head;
}
student *reverse(student *head)
{
student *curhead,*s,*q,*r;
curhead=head;
s=head;
q=s->next;
r=q->next;
while(r)
{
q->next=curhead;
q->prev=NULL;
s->next=r;
r->prev=s;
curhead->prev=q;
curhead=q;
q=r;
r=r->next;
}
q->next=curhead;
q->prev=NULL;
curhead->prev=q;
s->next=NULL;
return q;
}
student *deletkey(student *head,int info)
{
student *p=head;
if(p->info==info)
{
head=p->next;
p->next->prev=NULL;
free(p);
return head;
}
while(p)
{
if(p->info==info)
{
p->prev->next=p->next;
if(p->next)
p->next->prev=p->prev;
free(p);
return head;
}
p=p->next;
}
printf("\nItemp not found");
return head;
}
void main()
{
int ch,info,ninfo;
student *head=NULL,*p=head;
printf("\n1.insertion at begining\t2.insertion at end\n3.insertion in empty\t4.insertion in between\n5.display\t\t6.search item\t7.insert after item\t8.insert before item\t9.delet first node\t10.delet before\t11.delet after\t12.delet key\t13.reverse list\t14.exit");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter info to insert at the begining : ");
scanf("%d",&info);
head=insbeg(head,info);
break;
case 2: printf("Enter info to insert at the end : ");
scanf("%d",&info);
head=insatend(head,info);
break;
case 3: printf("Enter info to insert in empty list:");
scanf("%d",&info);
head=insempty(head,info);
break;
case 5: printf("\nContent of list ");
display(head);
printf("\nprinting from back : ");
displayrev(head);
break;
case 6: printf("Enter the info to be search : ");
scanf("%d",&info);
search(head,info);
break;
case 7: printf("\nEnter info after which to insert");
scanf("%d",&info);
printf("\nEnter info to be insert");
scanf("%d",&ninfo);
head=insertafter(head,info,ninfo);
break;
case 8: printf("\nEnter info before which to insert");
scanf("%d",&info);
printf("\nEnter info to be insert");
scanf("%d",&ninfo);
head=insertbefore(head,info,ninfo);
break;
case 9 :head=deletfirst(head);
break;
case 10:printf("\nEnter info before which to delet: ");
scanf("%d",&info);
head=deletbefore(head,info);
break;
case 11:printf("\nEnter info after which to delete : ");
scanf("%d",&info);
head=deletafter(head,info);
break;
case 12:printf("\nEnter info to be deleted: ");
scanf("%d",&info);
head=deletkey(head,info);
break;
case 13:printf("reversing linked list");
head=reverse(head);
break;
case 14:exit(1);
}
}
while(head)
{
p=head->next;
free(head);
head=p;
}
}
No comments:
Post a Comment