Linked List_07

Page 1 of 17

LINKED LIST Q. To create a linked list, and to insert (in front, in end, before a specific element, after a specific element), to delete (from front, from end, a specific element), search and display. The linked list may be empty or may have one node. ANS. Algorithm:

Function insert_after end begin end P←getnode if(start←∆) then Function insert_before begin begin Underflow input n return P←getnode() end if(start=∆) then if(info(last)=n) then begin begin Underflow link(last)←temp return link(temp)←∆ end last←temp if(info(start)=n) then end begin else link(temp)←start begin start←temp prev←start end repeat untill(link(prev)≠∆) else begin begin if(link(prev)=n) then prev←start begin before←link(prev) link(temp)←link(prev) repeat untill(before≠∆) link(prev)←temp begin return if(info(before)=n) then end begin else link(temp)←link(prev) prev←link(prev) link(prev)←temp end return

Page 2 of 17 end else begin before←link(before) prev←link(prev) end end end end Function insert_end begin P←getnode() if(start=∆) then begin start←temp last←temp end else begin link(last)←temp last←temp link(last)←∆ end end Function insert_front begin P←getnode() if(start=∆) then begin start←temp last←temp link(last)←∆ end else begin link(temp)←start start←temp end end Function del_front

begin if(start=∆) then begin Underflow return end else if(start=last) then begin start←∆ last←∆ return end else begin temp←link(start) free(start) start←temp end end Function del_end begin if(start=∆) then begin Underflow return end else if(start=last) then begin start←∆ last←∆ end else begin temp←start del←link(start) repeat untill(link(del)≠∆) begin temp←link(temp) del←link(del) end link(temp)←∆ free(del) last←temp

Page 3 of 17 end end

begin Underflow return end disp←start repeat untill(disp≠∆) begin print info(disp) disp←link(disp) end end

Function del_specific begin input n if(start=∆) then begin Underflow return end temp←start if(info(start)=n) then Function search begin begin temp←link(start) input n, pos←0, flag←0 free(start) if(start=∆) then start←temp begin end Underflow else return begin end prev←start else repeat untill(temp≠∆) begin begin temp←start temp←link(prev) repeat untill(temp≠∆) if(info(temp)=n) then begin begin pos←pos+1 link(prev)←link(temp) flag←flag+1 link(temp)←∆ if(info(temp)=n) then free(temp) begin break printf pos end flag←0 else end begin temp←link(temp) temp←link(temp) end prev←link(prev) end end if(pos=flag) then end printf Element not found end end end Function display begin if(start=∆) then

Page 4 of 17

Program in language C: /********************Linked List Assignment*******************/ #include<stdio.h> #include<process.h> #include #include /*****************************************************************/ struct node { int info; struct node *next; }; /*****************************************************************/ typedef struct node N; /*****************************************************************/ N *start, *last, *temp, *disp, *del, *prev, *after, *before; /*****************************************************************/ void insert_after() { int n; printf("Enter the element in the linked list you want to insert after:\t"); scanf("%d", &n); printf("\nEnter the new element:\t"); temp=(N*)malloc(sizeof(N)); scanf("%d", &temp->info); if(start==NULL) { printf("\nUnderflow. Press any key to continue..."); getch(); return; } if(last->info==n) { last->next=temp; temp->next=NULL; last=temp; } else { prev=start; while(prev->next!=NULL) { if(prev->info==n) { temp->next=prev->next; prev->next=temp;

Page 5 of 17 return; } else prev=prev->next; } } } /*****************************************************************/ void insert_before() { int n; printf("Enter the element in the linked list you want to insert after:\t"); scanf("%d", &n); printf("\nEnter the new element:\t"); temp=(N*)malloc(sizeof(N)); scanf("%d", &temp->info); if(start==NULL) { printf("Underflow. Press any key to continue..."); getch(); return; } if(start->info==n) { temp->next=start; start=temp; } else { prev=start; before=prev->next; while(before!=NULL) { if(before->info==n) { temp->next=prev->next; prev->next=temp; return; } else { before=before->next; prev=prev->next; } } } } /*****************************************************************/ void insert_end()

Page 6 of 17 { char ch; do { temp=(N*)malloc(sizeof(N)); printf("\n Enter the number:\t"); scanf("%d",&temp->info); if(start==NULL) { start=temp; last=temp; } else { last->next=temp; last=temp; last->next=NULL; } printf("\n Continue? Tap [Y] to continue...: "); ch=getche(); }while(ch=='y'||ch=='Y'); } /*****************************************************************/ void insert_front() { char ch; do { temp=(N*)malloc(sizeof(N)); printf("\n Enter the number:\t"); scanf("%d",&temp->info); if(start==NULL) { start=temp; last=temp; last->next=NULL; } else { temp->next=start; start=temp; } printf("\n Continue? Tap [Y] to agree...: "); ch=getche(); }while(ch=='y'||ch=='Y'); } /*****************************************************************/ void del_front() {

Page 7 of 17 if(start==NULL) { printf("Underflow. Press any key to continue..."); getch(); return; } else if(start==last) { start=NULL; last=NULL; return; } else { temp=start->next; free(start); start=temp; } } /*****************************************************************/ void del_end() { if(start==NULL) { printf("Underflow. Press any key to continue..."); getch(); return; } else if(start==last) { start=NULL; last=NULL; } else { temp=start; del=start->next; while(del->next!=NULL) { temp=temp->next; del=del->next; } temp->next=NULL; free(del); last=temp; } } /*****************************************************************/ void del_specific()

Page 8 of 17 { int n; if(start==NULL) { printf("Underflow. Press any key to continue..."); getch(); return; } printf("\nInsert the element to delete:\t"); scanf("%d", &n); temp=start; if(start->info==n) { temp=start->next; free(start); start=temp; } else { prev=start; while(temp!=NULL) { temp=prev->next; if(temp->info==n) { prev->next=temp->next; temp->next=NULL; free(temp); break; } else { temp=temp->next; prev=prev->next; } } } } /*****************************************************************/ void display() { if(start==NULL) { printf("Underflow. Press any key to continue..."); getch(); return; } disp=start; printf("\nThe elements in the Linked List are:- ");

Page 9 of 17 while(disp!=NULL) { printf("\t%d",disp->info); disp=disp->next; } getch(); } /************************************************/ void search() { int n, pos=0, flag=0; if(start==NULL) { printf("\nThere are no elements."); getch(); return; } else { printf("\nEnter the element:\t"); scanf("%d", &n); temp=start; while(temp!=NULL) { pos++; flag++; if(temp->info==n) { printf("\n\tElement found in position %d.", pos); flag=0; } temp=temp->next; } } if(pos==flag) printf("\n\tThe element could not be found in the list."); getch(); } /*****************************************************************/ void main() { int ch; back: clrscr(); printf("\n\tMENU\n"); printf("\n\t\t0> Exit."); printf("\n\t\t1> Insert frm front."); printf("\n\t\t2> Insert from end."); printf("\n\t\t3> Insert after a specific element.");

Page 10 of 17 printf("\n\t\t4> Insert before a specific element."); printf("\n\t\t5> Delete frm front."); printf("\n\t\t6> Delete frm end."); printf("\n\t\t7> Delete specific."); printf("\n\t\t8> Search an element."); printf("\n\t\t9> Display.\n\t"); printf("Choice: "); scanf("%d",&ch); if(ch==1) insert_front(); if(ch==2) insert_end(); if(ch==3) insert_after(); if(ch==4) insert_before(); if(ch==5) del_front(); if(ch==6) del_end(); if(ch==7) del_specific(); if(ch==8) search(); if(ch==9) display(); if(ch==0) exit(0); goto back; } /*****************************************************************/

Output of the program in C:

Page 11 of 17

Page 12 of 17

Page 13 of 17

Page 14 of 17

Page 15 of 17

Page 16 of 17

Page 17 of 17