Linear Data Structures - List Se ‘Syllabus Abstract Da List ADT - Array-Based Impl Contents 31 Introduction to Data Structure 3.2. Abstract Data Types (ADT). 33 List aDT 34 Array - Based Implementation 35 Linked Uist TECHNICAL PUBLICATIONS? «an uptist for knowedgebasic types - Primi es of data structures. Data structure Tinear data ‘Non inear dala structures structures Exampie lsts, Exampia trees, sacks, queues ‘raph Fig. 3.1.4 Classification of data structure inear data structures are the data structures in which data is arranged in a list or in a straight sequence. For example Arrays, List Non linear data structures are the data structures in which data may be arranged in hierarchical manner. SS TECHNICAL PUBLICATIONS? - an up-trust for krowiedge pales Data Types (ADTs) we problems the necessary 7 the unnecessary . {is called abstraction aa fact view to the problem. Thus if and that | baad roar Fig. 32:1 Abstract modeling 5 Modification : This operation modifies the desired element’ va ADT Data Structures This part describes the that can ious data st TECHNICAL PUBLICATIONS"{Crogramming Examples oona | Leona LUstof sequent Cee -Diee }-feae-a lements wh associated Poms wo an ptt or brome TECHNICAL PUBLICATIONS® - an Umi poles x sims 9088 aes he ress net fe 2 ung rent fe ist We have to fis laced and then input the pair : data and next rst enter the location in an array where t ig, 34: Stat inked Ht hat can be performed on stat inked St ae ~ Enter the index for fst node"), seant("%a”8); 1 3 any element inthe list moons terminate’? ithe lish, 4 5 ed element inthe list. "wn Enter the data and index ofthe frst element’); - eration one by one. ‘ed %a" ali data fall next), Let sun h operation one 4. Creation The fields ‘data’ and ‘next’ pointer. We need to give the address be place in the aray a TECHNICAL PUBLICATIONS® an uptvstlr rowindge | a TEGHIICAL PUBLICATIONS? - an ypu for knowledge —In Insert function, consider that we have already created a list (10, 20, 30, 40) as - au | net a 1 |» 6 2 + 4 10 1 = ‘ a 6[_» 7 7{_ «0 1 5 s —_ }CAL PUBLICATIONS® «an vt or Inowiedgele copy 6 of previous 20 comes before ce we will copy actual al2|data is lg. 344 (a) Botore deletion ECHNICAL PUBLICATIONS? ~ an upant oe ‘ning r F st or LUnear Dat Stractte Lit (Node is deleted ot feta #include ° #include TECHNICAL PUBLCATIONS® ov win hy romeLinea Data Strate igand Data Structures ‘Al ta field if vaua is -1 hen tind that ie locaton s empty “This for oop iniatze re data fils of fot ali) data==-1) printi(""); else { printi(" %d_, ",alil.data); y =ali] next; case 4Deletel); } break; printf(" NULL)"}; case 5Search)) } breaks void Insert() ase S:e1t(0); } { int imew_data,temp; rnsi("\n Do you Wish to go to Main Menu?") Drint{("\n Enter the new data which is to be inserted"); ans=getch(); ‘scanf("2a" enew_data): Jwhile(ens=='y'|anse="y), wn Enter the data after which you want to insert”); etch, temp); for(i=0;i< 1084+) { ‘Mali data==temp) break; Mier the index for frst node"); } TeCHICAL PuBLicaTioNS® "© Pts to tnoniadge TECHNICAL PUBLICATIONS® « an upetvust for know>» lal next==-1) 4 alildata=-1y/*writing -1 means deleting the element*/ marking the index of an array at which record is placed*/ rnext;/*storing the next pointer value at that index*/ void Search() { int itemp.fag=0; + print{("ta Enter the node to be searched "), Techical PusLicanong® 4 +0 Ups br hnoniedge temp) /"fag 1 means tho element is present*/ nag==1) print{("\n The %d node is present in th list” temp); 3. Insertion of element in the list 4, Deletion of eloment from the list _ 8. Searching of element from the list Enter the data and index of the first eloment10 1 Enter the data and index of the first element20 6 Enter the data and index of the first element30 7 Enter the data and indox of the first eloment40 -1 Do you Wish to go to Main Menu? Main Menu 1. Creation, 2. Display 3. Insertion of element in the list 4. Deletion of element from thelist 5. Searching of element from the ist 6. Bait Enter Your choice2 (0, 20, 30, 40, NULL) 19, 20, 90, ao, wu) Femi RRUEATNG at naean Ben? of Element tn aray Step 1: Enter the number of elements present in the array. Also enter the elemonts in arnay. printi"\n How many elements are present in the artay?"); | scant("%a" An) ‘rinti"\n Enter the elements(Type -99 for empty location): "); forle=0ccne++) ‘scant("kd”farayic)) Se TECHNICAL PUBLICATIONS® «an up-nust for bnowiodgo tho Key Element at that p sp loft and right to this Key Element Insott Key_Eloment at Key Position else goto step 8 ) Stop 6 : If Loft ElementCount > RightElementCount then, 1 Search for empty location in this right sublist. If empty location is present then move the elements to the right by creating space at Key Position thon eee TECHNICAL PUBLICATIONS® - an upitiust for knowlecy ifend of linked list only one link, to point to next node or the Tast element points to nothing itis linear 4s NULL which means that there is no further list. The Fig. 252 A link list of integers, °C’ Representation of Linked List typedef struct node st data; /" data field */ struct node * next; * link feld */ TECHNICAL PuBLicaTions® +t uptinsfor inoniedge ap-eo-eo-ers] next element and this list is type of linked list only one link is used to point ‘means that the last node's link field points to the fi example after 40 the next number will be 10. So called doubly because each node has two pointers previous and nevt pointers The pointer points to previous node and next pointer points TECHNICAL PUBLICATIONS® - an uptrust for Knowsoe 2 New =get_node() if ( New == NULL) LL and last node's jously NU printé("\nMemory isnot allocated) New -> data = val; ti if (ag==TRUE) /* Executed only for the aoe first t head = New; tomp = head; /*head is a frst node suLt/ ors fag = FALSE; temp=( node *) malloc{ sizeof{node) }: temp->next=NULL; £ retum temp; , print{("\nEnter the Element"), TEGHMICAL PUBLICATIONS® TECHNICAL PUBLICATIONS® - an upstwst for knowtedoe + an opts for knowledge3a em Ket Say for value 30 the senario, St BP] opmveres Noe Ot rose() TS BR oe ie 7 S-ES-y] TC [EIT] te temp Now = get_node () eta llacato fr oa O- 20] —}- Popo [era] pe) Lele -— rinses PTE SHED] torn tor ewan ang Sew potent 50 thon (ol S-LS- 2 S+- ES +-Bee Tempiow t ress of head node to the display routine and calling head as the inked list is not created then hheadstemp node will be NULL. is empty “ will be ce 2s aS ee SSE Tae oem temps moved ‘ahead atrscr(); return; } While (temp != NULL ) Pan © TECHNICAL PUBLICATIONS® - an up-trst for knowledge TECHNICAL PUBLIGATIONS® - an up-tust for anTecneicn. PiasrenTione™ tas 2 he adieData Structures —— peas Dass ter The element - which lew->data); {You want to insert") Finding end ofthe linked list Fee temp wil be a last node at /__printf("\n Enter The element after wi a eee ae —scant(“%a" key), _ temp=head: do 1p->data==key) New->next=temp->next; ‘temp->next=New; temp=temp->next: while(templ=NULL}, “if we want to insert 31 in he inked ist which i aeady crested We want to insert this after fiode containing 90 then PSS eS [Pw] i” will search forthe value 30, key = 30, [ol ELS poe EEs)temp = *head, (temp == NULL) prey -> next = temp->nert; free (temp), TECHNICAL PUBLICATIONS - a else { thead = temp —>next, free(temp): Wwe wart o deleto read node (Men set adjacent node aa new head nade and ton dealiocate the prewous head rode =] +S -l>- Se ‘we will search the node containing 30, using fe to be deleted as temp. Then we will obtain 18 Bet_prev () function. Mark previous node as prev a S-LS-6S- o] -P + - -eper ow we will free the temp node using free function. Then the linked list will be ~ if we want to delete a head node then - Ee eSie temp data WAL B enp ->data 2 tay No GS 8S6S 4S temp data 2 head: fomp == NULL ) anked List is empty\n") key oes the message "The Element is present in the list tion the entire lis can be scanned in search of desired nove. And still, FALSE: obtained then we have to print the message: jomp |= NULL && found= =FALSE) smp->data = key) mp = temp ~> nest found = TRUE, i if (found==TRUE } Program to perform various operations such. ‘and display on singly link ists. include include include #define TRUE 1 #define FALSE 0 typedef struct SLL TECHNICAL PUBLICATIONS - an eptiatfrknowedyecase 4: head=insert{head), break; case 5: dele(&head), breaks case 6: exit(O); dofaultclrsex(); rint{(“Invalid Choice, Try agains), etch); } }onhle(choice I= 6); } node" create() { node “temp, “New, *head; int val, lag: char ans='y'; node “get_nodet); temp = NULL; flag = TRUE; /* fag to indicate whether a new node is created for the frst time or not */ do { printf("\aEnter the Element :"); scanf(“ta", &val) /* allocate new node */ New =get_node(); if (New == NULL) print{("\aMemory is not allocated”); New -> data = val; if (lag==TRUE) /* Executed only for the frst time */ { head = New; temp=head; /*head is a first node in the SLL*/ flag = FALSE; ~ } you want to search"); TECHHICAL PUBLICATIONS”. an ups fr inoatedge cee ” .pnint{("\aThe Element is present in the list\n"); getch():ret Dat Seratres nt ‘New head i retired from funston insert ead). case Theat insert head(heads eoak: case Dinsert ast vovd mnsert_after(node *head) { int key, node *Now, "temp; y /" Insertion of node at fret position*/ f (oad = =NULL) f hhead= Now: | se ‘ { ‘\n Enter The element after which you want to insert the node”); ae ka fake) Now->noxt=tom: fies head New: tomp->data==key) { Now->next=temp->noxt temp->next=New: TENA PATO meas aw Conca LEAT attemp=temp-0e8 Jwtilttemp!=NULL) } y ” aot val) node" get_previnede "Beads etrscx0: prnt{("\aEnter the Element you want to delete: “) scani("4d", Bikey): temp = search(*head.key), if (temp '= NULL) { prev = get_prev("bead key): if ( prev = NULL) 4 prev -> next = temp->next; free (temp); Program to Perform Various operations on Linked List Lcreate 2Displaysat 20 . or more erements?(9/00F nt 30 is more elements?(y/0)¥ nt 40 erylay enter more elements? Enter the Eleent $0 Do you Want to enter more Toe Sag Linked is gs on Linked List rogram to Perform Various operat create 2Display ‘Search for an item 4\Insest an element in a list ‘5Delete an element from list 6Out Enter Your Choice (1-6) 2 10> 20-> 90-> 40-> 50-> NULL ‘Program to Perform Various operations on Linked List 1.Create 2Display Search for an item insert an element ina list 5.Delete an element trom list 6Qut Enter Your Choice ( 1-6) Enter the element you want to search 40 ‘The Element is present inthe list Program to Perform Various operations on Linked List 1.Create crx Display 8 a head node insert a node as a last node 3. Insert a node at intermediat ® Position in the liked lst Enter the your choice for insertion of nade + Enter The element which you wane to user 9 Program to Perform Various operations on Linked List 1.Create 2Display 3.Search for an item 4.Insert an element in a list 5.Delete an element from list 6.duit Enter Your Choice ( 1-6) 2 9-> 10-> 20-> 30-> 40-> 50-» NULL. Program to Perform Various operations on Linked List 1.Creato 2Display ‘Search for an item 4.Insert an element in a ist S.Delete an element from list, 6.duit Enter Your Choice ( 1-6) 4 4. Insert a node as a head node 2. Insert a node as a last node 3. Insert a node at intermediato position in the linked ist Enter the your choice for insertion of node 2 Enter The element which you want to usert 60 Program to Perform Various operations on Linked List Lcreata 2Display 3.Search for an item TECHNICAL PUBLICATIONS? - an upd fr noweapo TECHNICAL PUBLICATIONS® «an upmust fv Knowlefour Cnoice (1-8) _> 6o-> NULL Your CD01 (go> 50-7 OO et = 2 fnions on Linked Lis Program to Perform Various oP 1.Create 2psplay {3.Search for an ite 4ulnsert an element 108 Uist Delete an element fom Lst tout Sour cane 4 Frade vane" SES ase 2 eta ie edt psn tei rinerion ot? Sona one 3D 2 et oa te ae 30 nas operations on Linked List Enter The element Program to Perform Vario 1Create 4.Insert an element in a list 5 Delete an element from list Qu Enter Your Choice ( 1-6) 2 9-> 10-> 20-> 90-> 31-> 40-> 50-> 60-> NULL Program to Perform Various operations on Linked List 1.Create 2Display Search for an item 4.Jnsert an element in a ist 5 Delete an element from list Quit Enter Your Choice ( 1-6) 5 Enter the Element you want to delete: 40 aS E—-re ss SS Tecrovca. PusucaTions® + an upstrust for knowledge 2Display 3Search for an item 4.Insert an element in a list 5.Delete an element from list * 6.Quit Enter Your Choice ( 1-6) 2 9-> 10-> 20-> 90-> 31-> 50-> 60-> NULL [sis] more Programs on Linked List In this section we will discuss vatious o aus eperatns that canbe performed om the inked st 2 wl dus only functions performing ready cae, The cre and spay Ex. 35.2: Counting the nodes of linked list. Sol. = ‘void count() { node ‘temp; int o=0; temp=head; if{temp==NULL) { print{(“\n The list is empty"); return; } ‘while(temp!=NULL)/*visiting each node*/ { e=c+1;/*c is for counting the node*/ temp=temp->next; + rint{("\nThe Total number of nodes are : *d".¢); getch(); + —— eee TECHNICAL PUBLICATIONS® « an up-trst for knowiedze‘temp2=temp2->next/* moving one node ahead */ tempt =templ->neat; } temp2=NULL./"set the next pointer of last node of second list to NULL*/ printf("\n The list is copie \n") ‘hilo iead2->-next!=NULL) t ‘printing the socond list Le. copied list*/ enemy { temp =tomp->next/"vemapt bs dectater rode *prov_nodol,*next_noda2,"hesd, (temp1==NULL) { tempt =tomp2: head=tomp2i a ifluemp1->data data) head=tomp!; lee head=temp2; ‘whilo(tomp1l=NULL && tomp2!=NULL) { Philo data of Let lst is smaller thon traverse*/ ‘while((temp1—>datadata) && (temp1!=NULL)) TEGHRUCAL PUBLICATIONS” «an yptnust fr hnowiodgo TECHNICAL PUBLICATIONS” «a9 up-Ovust fr knowinnosed, temp2=next tempal=NULL) [attach fom nodes of S12°/ ppt =NULLA free podel->next=teme2: rev pode! =temp2 temp2=temp2->nest } } return Bea } east 4 -RLo- Ee veo? =} elma] |= wos 7 aa SL -EL}-eo Ex. 35.7: Retuming the position of an element X in a list L Sol.: The routine is as given below - Return _postiion(node *head int key) { ee ane EE Eee TECHNICAL PUBLICATIONS® «an apts for -lement X is not present Ex. 958: Write a C function to display the sum of all the elements in a singly linked lst, sol: eid su(node *hoad) { nove “temp: int #=0, temp=heod: twho(tempI=NULL) { srestomp->aats, Fecip=temp-next } ne a } E359: Assume a singly linked list where each node contains rollno and percentage of marks, Write a °C" function COUNTO and count how many students have obtained more than 60° Sol. : The data structure can be ~ struct student { char *name; eee ® TECHNICAL PUBLICATIONS® - an upttrust fr Knowledgeqmoxt=p: a=; y ) peazhoad: ‘whilo(¢next!=NULL) { pep-onoxt; q=a-mext; if(qmext!=NULL) ‘q=q-mext: roy than 60 Percontago’, Count); pave obtained beste forlp=head.p!=NULL:p=p-next) printi(niba"sp-sdata), { if(p—datal=q—data) { P=ponext; a= q-mnext; } else if(p—xtata==q-sdata) { pomext=q—next: a: (noxt; SSS _—___— TECHNICAL PUBLICATIONS® = an uptrvst fr Anowinie eer pumicaTions® ~ + an ptt fr knowledge) returhead). ) > Ex 35.12 Suppose the maximum elem itemp->data>Macval) © spaevat=temp->date > temp=temp->next, Jt Maximum Vaio 8 Mass » {i) To find the product ofall numbers in the linked Hist: } Review Questions 1. Write C code for singly tked nt, delete, display operations using strat TECHNICAL PUBLICATIONS? an ups er knowledge can be accesed 2) Insertion and is time consuming, ) In linked list, e elements easily and iti less time eo ray and 6 ry. Fist we have to declare allocates memory at declaration TECHCAL PUBLICATIONS® - an up-rt fr knowFig. 274 Noe stare Ppp pee waar Blatt pone pects Toste cndlbh> eemnhe poste THUR 1 poston FALSE 0 eypeted struct DLL 4 wn data: seruct DLL "oe, struct DLL “pre, TECHUCAL PUBLICATIONS + an up that for bowled TECHNICAL PUBLICATIONS” - an up-Onust br irowesie7 print{(\nEnter the Element», sscanf(%d", val) /* allocate now node */ New =get_node(), if(New == NULL) print{(\nMemory is not allocated’, New -> data = val; if (Qag==TRUE) /* Executed onty fo tho frst ume */ ‘ head = New; temp=head; /*head is a first node in the DLL“/ ‘fag = FALSE; , else case bead=insert(head): break: case Sidele( tinea), oak oops track of the most recently wd node */ tomp ->next = New; New->prev=temp: temp = New; printi("\n Do you Want to enter mare elements7(y/n ans=getche() Jwwhile(ans=='y); a rintf(\oThe Doubly Linked List is created\n"; ‘The create function etch); ” celrser() return head; } p. "New, *head: node *get_node() a Jwwhlle(choice I= 6); » rode" creste() Tee RauCToND wom TECHNICAL PUBLICATIONS® - a upehst for knowsroad dusplartzade “Bead ‘ pede a temp = bead: (emp == NULL) { past iTae ust empty etch cect) eva List in Forward direction is An" ale (temp I= NULL ) { pati Ke ~> *,emp->data} temp = temp -> next: ) prntfC NULL): temp=head: ‘whule(temp->next!=NULL) temp=temp->nexty//reaching at the last node prntf(\n List in Reverse direction is .\2") ‘le (temp '= NULL) { TEOHCAL PUOLEATIONS™ an pat roe fe search function “Lay vserelote haute £ pode "tem: spt found temp = bead: (temp == NULL) ‘ printi(The Linked List is empty'n’ etch essex return NULL: , found = FALSE; while ( temp != NULL && found==FALSE) { 1f( temp->data I= key) temp = temp -> next; ze found = TRUE; ) it (found==TRUE ) { print((\nThe Element is present inthe lst" ‘etch() return temp; bse { TECHNICAL PUBLICATIONS® - an upitrt fr know* toserticn of node at frst position*/ node "insert head{nede *head) ede “New. “temp, void insert_last(node *head) { node *Now,*temp; New=get_node(); print{("yn Enter The element which you want to insert’) seant(‘Sd",&INew-> data); sf{head==NULL) head=New; else { temp=head; while(temp->next!=NULL) temp =temp->neat; temp->next=New; Now->prev=temp; New->next=NULL; } } ‘(Insertion of node at intermediate position"/ void insert_after(node *head) { int key: TECHICAL PLBLICATIONS® « an upsteus for nowiedge TECHNICAL PUBLIEATIONG® on win br inom” void dele(node **head) { tomp heat do smp->aata= Key) Now-> next =temp->n0xt: (omp->next)-> prov=Nowr temp->next=Now: New->prev=tomp; smp=temp->neat Je(templ=NULL): Parameter Passing Method : call by value TECHNICAL PUBLICATIONS® - an up:imust for knowledge oR )->pIo¥ = prov node; Ph “head = temp —>next; (thead)-> proy=NULL; freo(temp); output Program to Perform Various operations on Linked List Create 2Display TECHNICAL PUBLICATIONS an apstast for bromideeperations on Linked List ‘rogram to Perform Varios 2pssplay 3 Search for an iter “AInsert an element in alist ‘Delete an element from list aut Eater Your Choice (1-6) 2 List in Forward direction is 10-> 20-> 90-> 40-> NULL List in Reverse direction is 40-> 90-> 20-> 10-> NULL ‘rogram to Perform Various operations on Linked List Create 2Display nnn TECHNICAL PUBLICATIONS? - an up-trust fr knowledge eh 30 Choice (1-6) 4 1, Insert a node as 2, Ingert a node as a li 43, Insert a node at Enter the your choice Enter The element which you want to insert 9 Program to Perform Various operations on Linked List 1.Create Display ‘Search for an item 4insert an element in alist ‘Delete an element from list 6.Quit Enter Your Choice ( 1-6) 2 List in Forward direction is 9-> 10-> 20-> 30-> 40-> NULL List in Reverse direction is ._ eS TECHNICAL PUBLICATIONS” - an up-tvust fr Anodecant to delete: 20 Element you Natt “The Element is present s the Us ‘The Element is deleted program to Perform Vanous operations on Lane List Create 5 Delete an element fom hist 6 Enter Your Choice (1-6) 2 List in Forward dizection is 9-> 10-> 30-> 40-> NULL List in Reverse direction is 40-> 30-> 10-> 9-> NULL Logic explanation of DLL program 1. Creation of doubly linked list ‘TRUE Th rst_node, _ pele l T 2 [ue Taal Ter = Peele Tt Te pm) PNT nee sup 3+ If user wants to insert anode witha value xy 0 them ea Hoare) pee) ~ aa mo New getinoce() Gel SE Ta Se) eee read me = ime ma] 10 [ai TTT] tore = New Teed Nes aro Continuing in this fashion doubly linked can be crested 2. Display of DLL. {As each of DLL contains two link fields ~ Previous link and next link. Hence we can display DLL in forward as well as in reverse direction, Suppose we have created a DLL as TECHHICAL PUBLICATIONS® an up-thust for knowledge TECHNICAL PUBLICATIONS® - on upttvust fr knowintemp tevnmes NULL we will come out af the while Joop. TECINCAL PUSUCATIONS® an pera oY oecareer. a | Tow Tw © Pree renee arse nese © pepe ws sm New» rev = temp: eae T= er] temp —>next= New: TECHCAL PUBLICATIONS - an upitt fr Anowedbe % TECHNICAL PUBUCATIONS® «an apis rowsee Yo = Jon 2F SEAN Ia ae ge Ore fd GUMS 1 AEM FIO peer noe AOS owe MEM eT mallac(sizeafietuct nage) NULL, nmi New),/*ereated node 8 retumd to calling Ransto"emg + nent = Hew, (ee le a)-6S)New=get_sode() pastf"in Enter The element which you want to insert“) TEOWICAL PLBLCATINS® «an wnt er hronledin tomp->next=New ext head, ‘The node 1s inserted!) loment which you want to inser“), jew>data) tfoead==NULL) t rnoad=New: ) else ‘ prmi(“\n Enter The element after which you want to insert the node “) seani("%d".BKey) romp=head: eo ‘ stemp->data==key) q Now->next=temp->next; temp->next=New: pnant{("\n The node is inserted") evar: » else temp=temp->nex: Jwhte(temp!=nead), , TECHUCAL PUBLEATIONS® «a wpitrt tr onanToe Se Ns (eter — ist tre wan to inset a New nae [so] NULL q3e3 2 [ws a Slo TC ter node 30 then, tf we want to insert an element 35 after node 30 qS-E-2- ES} oe Tess ‘ane nd temp» csta= 29 aso New -f-+EE-EC} pEeIh ene hess ‘er Lfsy 4 TECHNICAL FUBLICATIONS® - on upsst fr knowledge tet —_ ao Caeaeannente { Ss ee ce eee , { bccn: veer nat one a Sedan pees rad print{("\n The node is deleted”), ) TECHNICAL PUBLICATIONS? - an upitst for krownd>ei =] TecHnvCAL PUBLICATIONS? tempt = temp + nox, temp + nest = tempt; eal tempt ie want to delete noce tempt = temp + not: + 09 upstust frkooniodge seruct node “te temp=head: we(emp->nex!=neaa) to. temp->data == mum) retum tempi odes found/ temp=temp->next Yinciude #include TECHNICAL PUBLICATIONS® - an upstnst for knwo. MS Vi gemeey nt tnt cave 4 head ~Delete(hna ee tae tree Lat weruct mote cae ; * a ae ) aunt"\n The node is peseat”) eke printti"\n The ode is not peesenn”y me Peesest". Baym treses B45" - Se imtteer niet tenpabent ‘nbs egy Saat t= Daath siting he st Soe ARCO oe ROME RRO a4 break: struct node “Nev Taloc(sizeotitruct nod) 1 retur(New);/"ereated node is ) sevamed to calling function"/ struct node insert_headl(struct node ‘head) void Dspla(stuct node “head u { struct node “temp: struct node “got_node() Caos struct node “New. “temp: spemnp == NLT) New=get_nodel) Cl hc rtalentiia }——_print("\n Enter The eloment which you want to inser“), a seanf("%d" New» data} ‘ stquead= =NULL) e hhead=News: 7 else priny("Aa\etomp-> data) i ae ee temp=head; pete ao Gurr tne ty a ~— temp-Paee-tew f - New->next=head: set ode aed xt) eee sot chotee, 1 mi Th ae eas struct node ‘insert_head(node *): pe as ee ERs TESTES Tad Peg TE TaTaE ad PnnPaDTaE DOT TOT TO UnEDNSDNDDOEDNornerOneE nsSeESnEOEE , Feeinweat pusticariond® sw Gane VCAL PUBLIGATIONS® an upon for snow TECHNICAL PUBLICATIONS? TECHICAL on uptime or knowiodgech you want to insert “D temp=head; ‘wule(temp-»next!=head) temp =tomp-> next: uct node *Search(node *head.jnt nu) vemp-2next=News New->next=head; struct node “temp; print{(“\n The node is inserted!" temp=head: } wnhile(temp->next!=head) } void insert_after(struct node *head) { int key: struct node *New,"temp; tomp=temp->next; New= get_node() » pnnti("\a Enter The element which you want to insert "); retum NULL: scanf("d",&New->data); } iffhead==NULL) struct node *Delete(struct node *head) 1 head=New, } else { pninti("\n Enter The element after which you want to ened il{temp—>data= =key)/"If header node is to be deleted"/ ‘scant("a" &ckey); { temp=head, temp1=temp->next; TECHRICAL PUBLICATIONS® «an upitnst for rowiodge TECHNICAL PUBLICATIONS® - an vn for Aromtne“me node Is doloted” forthe last node"! ho ato is deleted") pant" The nod late node is to be doloteat*/ pris The oe is eet teu stems wots Dow, TSO NCA ALCAN” ar ann or mee ‘Do you want to enter mote nodes? Enter The Element Do you want to enter more nodes? Do yout wat fo goto Mass Menu? Program For Cuculat Linked List 1. Insertion of any node 2, Display of Cucular List 3. Insomtion of a novo in Cucutae Uist 44 Deletion of ay node 5, Searching a Particular Element ig The List 8 wt Enter Your Choise 2 w 2 ww Do you want t go Mass Program For Cuewar Latkes Lnsertoa of any nodein Me List To Be Searched 20 4 Deletion of any node 5, Searching a Pasticular Element in 6 Ext Enter Your Choice 2 an im Circular List 1 2 9 3 40 — . salar Linked List Program For Cucular Linked ‘Sint 4. Insertion of any node 2 - the List Enter Your Choice § 4, Deletion of any node Eire Eh eae 5, Searching a Particular Element in The List " esene Do you want to go to Main Menu? Program Fer Gixcular Linked List 1 Insertion of any node 2. Display of Circular List 3, Insertion of a node in Circular List 4. Deletion of any node 8. Searching a Particular Element in The List 6. Eset Do you want to go to Main Menu? Program For Cucular Linked List 1. Insertion of any node 2. Display of Circular List 3, Insertion of a node in Circular List 4. Deletion of any node 5. Searching a Particular Element in The List 6 Bat Enter Your Choice 2 TECHNICAL PUBLICATIONS® «an upstt fr knowledge TECHNICAL PUBLICATIONS « an vow Kr woe‘The stack data structure can ‘The queue dlata structure can be impl 3.10 | Two Marks Questions with Answers Qi Explain the term data structure. ‘Ans. The data structure can be which are requ fan be defined as a data structure ‘of axioms A. This triple (0, F, A) denotes the data structure d. 2 Whot do you mean by non linear data structure ? Give examples. ‘Ans. : The non linear data structure is the kind of data structure in which the dats jal fashion. For example ~ Trees and graphs. may be arranged in hiera 3 What do you mean by linear data structure ? Glee example. ‘Ans. The linear data structure is a kind of data structure in which the data is line or example - Stacks, queues, linked list TECHNICAL PUBLICATIONS® - an ups for knowledge om aor? oa 4. Database management system - management systems. Sorting and data 4, Numerical analysis package - The array is used to perform the au . fon the given set of data Perform the numerical analysis 5. Graphies - The array a 7. Networking - The graph is used for finding the shor ‘hwo computers that are connected in a LAN n= The queie is used for simulation and modeling, Inked list ? oo Ans. : A linked list is a set of nodes where each node has tho fields ‘data’ and “ink field is used to store actual piece of information and link tied ss used address of next node, TECHNICAL PUBLICATIONS? - an upstate anowinasetn tnked eps 10, moss & moe AS Wye owen the ters sable pol 1g dynamic memory then itis called ki of ctreular tists over doubly 10 State the adcontoges next pointer. The main advantage of circular o ean access head node quickly. Hence some an er field is reserved, 11 Whot are the advantages of doubly linked iked list has two point k field 10 pointer fields we can access any node eff Jd is there which stores forward pointer, ‘Ans. : The doubly and another Because of the inked list only one pointer accessing of any node difficu uz Ans. The can allocate or de allocate the memory 3s per array makes use of the static memory location. i memory for alloca makes use 13 Whot Is circular linked lst ? Ans. : TECHNICAL PUBLICATIONS? - an uptirust for knowledge What Is advantoge of an ADT ? ass ‘The advantages of ADT a ans ‘Change : The implement the client program that uses 1 4. Flexibility fais Should arrays of linked lists be used forthe following type of applectons your answer. cecreemanee ) Many search operations in sorted lst. 1) Many search operations in unsorted lst, ns. list is sorted then ply by moving forward can be searched, then using arrays the desired element can be searched. The ys access to random element 17 What are abstract data type ? oon OR Define ADT ECTS Ans: Refer Q5, 18 What Is statte linked lst ? The linked list struct TECHNICAL PUBLICATIONS® - an epitst fr krowidevoid “realloc (void *ptr, size_t si insu en to expand the memory block, realloc() is used, 20 Wht are the disadvantages of linked list over arrays. Om, ‘Ana. 1) In linked list, we can access elements in sequence. So it is very dif ¢ amount of memory gets wasted in storing the next node's address inex, nodes. TECHNICAL PUBLICATIONS