re CS8291 — Dory SrrvewrR es. UNITI LINEAR DATA STRUCTURES ~ LIST 9 Abstract Data Types (ADTs) — List ADT — array-based implementation — linked list implementation —singly linked lists- circularly linked lists- doubly-linked lists - applications of lists ~Polynomial Manipulation — All operations (Insertion, Deletion, Merge, Traversal). Doo S RITURES’, Sake Srrudune wa way, oy collec y ond Ora tea a 4 ae" By Aote wow WAX dad we ean Ppeajovm operation on the data m oO eFfeedive wa a | a J ineday nowt linea Lob, Looked List, stage, Vee, Gvagh , Ques Has ADI- PestRact Dew Vere: Py abstyad ola type & dhe wa we lesk ob ; whab ib ae aed eae ti vd tanovi ; Ub job a ‘are 4 how tt doesJast Apt bish W sequential, collection of Zlomen bs OF some Aype- Jt can be iwplond wong arya’ and Linked Lisb- Lint rd anvrany’ Av away wa collection of clomon by oy eteniloy decay pe Mok ane eteved w convegutive locadiaw Operations: ~ Create — Went - Delete — Fadl - Pivot He define Se 10 tok aw Léigey tolno ; Creme: Vid create Cea oD TL ttt, f Cage jor Cire; ¢ Lo t+) 4 seangoréd” J oxrt it):Twrestion - opelebel [eo] Sh Rak Sb sat obs Po] [i Oo.) 2 2 4 co 6 Trwertira a now element to dhe specified, Posttien yequives all she clements after wh to lee moved one positio vight. TA abso vequived fo chock Lat & Full ov vol: void, nee Cob pos, tot vas) y tt t uf CHd sige OS pes'£0) L Jore t any ly posiat’) ore Li4i} = orl] oxy Tos} = vals Sao, ~ premdy O Lik jul!DeEvetion Peledd on whemend From Ved vequives No check whaler tho lit o& ewpby. TR also sequires Ane elemans afer Ano postlten te be deleted Sw moved one postlien gt “ENE [sbfelide fell Ol ASE Paativg ho Toey {0| 20|30 |i7> |6o | Jo oa >So oo Mer deleting ho void delete ¢ tot val) L Lob Usposs~is if Coy pr c Cro, Lan 5044) is Cowy Ci) == va) Lo possi, 4 breaks, 3Jor Ctepos y Lenytaa ow Li]= awl ly); Ne0-\5 3 abe e me ~ vy, pints CVEst & emphy >; 4 Yiod: ; Tho operation te geandy Wether Nino. given clumoort & present ww lit ov oot: void Find Clot vab Lob ty Cnyo> jor Circo, len; iad) ce CaxaLt] 22 vob Vantec shaen CS lament ‘ound abpesition 7h no) 4 ea Yeu: J Prot} C Element not Feund” ); else peotgO pat & cxuplySDisplay ‘ vod display a bot ft. i L Cony dS | evCt co; len; 44) | 7 ? L pe only cd Ww H aw ti}; 4 ele. Printf CMLL & enuphy>; dace Diradvartage>: - A w ined, a $ of waster, if alloted sige & nob ws — Insertion d Deletion vequiires wovewont OF clomertts - Foscilole Qurction: ie Explaio how Wirt b& wwplemend ~ owany. a Whol &® an ava How it Ww accessed. 3 whol one Ane dinadyon oF Ara 2 % wWhed & Ure ned jor uel? te Define ADT -@ hanven st: ’ & fired biel & oF finan dota eluctine Which comuls o, oF nodes which Vogetlnen vaqwoeel we Tres: — 4 Looked Lob - & Looked Lat — Cheullds Linked Livt- bing Jivked Lisr- Sings Linked Lisl comsirts oF collection of voder « Neder comstnn oy oo ports date and pototen. The pointes pots addrees of dhe next pode. value bo Addvess & a pede. Operation. Deletion Wovenrsal esA node w vepresented, Ow slruck ede tot dade; Shyucl node «next; 3 xhoad, Roe Yeaestation : bel 4-844 ra {ad Fit Node as \eoden. weth data. Seperate rode ‘on \wacer. Insertion . Adds a new elamenl to Ane Vt: Based on Aho postion oF insertion “tb us categorizes as — Inert ab Finck — \mat ab hak — Insert oft a specific necesFrvertiogy a ode wequites eee of new nede and, aneigning petntens appropriately, Iment ol Fret. Cia ei} Liltxse) fd > rowed a, aa Unsere Clot val) Auck node anonnede > malloc CeyearC naonede —>cladtas val; sbyuctveded); newoede —> next =head —snoxt, \oad —snoxt = naonode : 5 Tread ar lash: Insert at fost position veguives dwovensal Lill the Rosk redevoid inrentlast Cint val) L Sbruct node 4 nawonede = malloc Cetge oF C poe «gy ato. av Struck veda}; “whee real een alee I= joi) | tenip = temp Prax ; Rawnode —praxb = NULL; — >noxl anawnede, 5. Poet. CHa. Me a newnode Tonerd ob a Specftc posilion . Tnsexdt an clament ab s “ ees os | posidion vaquives Lvaversall } From Furst alawent bo dhe specific element and changing, potn Gn onstgn mont appropriatdy.veld inserlaf ter C bob seams, tel val) 2 Shuck ode + tap ; Soruck pede * nownede = malloc C Sige ef Cébruck node; Aen = hand; | y | a Clemup vrdela | = searcl SN Aewp -rnoxt| =rouLt> Aaaup —y minxebo= r dew pebemp-7 tant ; UF Cdemp ty clade = = Seaach) nuwndde data = val, nasoteds. > hard 2 dewp —praxt; ’ hemp —> next = rawnede; Loe , “ Pinko” specified elgment not Found"); THe 2 head Geet eyélh wd noode. Sten Weeating Ao.baacking.. Wed search C tnt vail) Suck node atemp ; = head > next; while Cewp| =u)» Q ¥ Clemp —rdota == val) v perf Elmo jour" »% Yel, % Despoy,: Display xy element vequives Arovensal From Jost clement te last clamor vod Asnplorye > Sire node xtomg, 2 head next; a k Crem) nun probly Cvyde”) dated; 3 ones Lenore) _> work 1Pelelion of elemosL: fo dilibe an clemart. Flom list, Ake position of Une clement raed te be Found and de podria OF prevtons pods. nod bo oe altenced . repay | ‘pres ; vid doletecint val) v Auch wode atom, % prey ; 2 head 7 text; silo Clemp dale bau SL texp] sro) sone pealet ; texep > wax, 3 Champ a=rdeta =nr0b) pren = neck = famp runt 5 7 JrenChemp); ele prioty Cs Blonant nob én List”); 3 Deletion PF an clement ia done by, changing Ake pointer to point ty le pou Aw Node Aelated node. a OF theAdvantages . ~ Dnaayte- manor, allocate: facilitates adding and duldig oF elements - ne wastage, oF MeMory., ~ Fmreatio and delete Us cosy. Nlo movement F Chemonty ir vequived. C | Disodvontagen | - Radyives more space because Ch also stevens the address oF vaxt node along. well dao — To access Unc elements dvownsal ws done From Mae hood] Frist node. 7 Only Jprosand. Lwowensal > posetbele. Applicatcon : a Representation oy Polynomoal _ \wplementacien oF oer doce shyuclune Like stacl dy Quelons: RE my Define Linked Lisb - | ae a AF ference loebvenn Onvan, and 3 Speetfy Hae advantages sdiodvanliages oF su | Ay Explain Sing ly hinked Lik por.Creer lee har. Th cireuler Linked List tne las node contolins Ov porter to Ane Jost node ST head po : Opercdiions oo Auch node — WWsentiory, jG ci ~ a ab sLruct node arort , — Wouers Ahead ; Trrention Trsertiom wy clreulan Sankad Ut can be clone a position . —\wortion al & ani. =—\wortion at last = \mertion oF bin specific node.Tred at Loni TO insert an clomont, create a nrwonoele and woke the heads poiotea points be dhe now Node. Vid inserk Frel Cint vals y slruch nede. meng, xnanode.: newned2 = malloc Cetggo§ Couch nodes) ); newnode. —y cata val; hee Uf Chead nex ==nvurd AEN, 7 next = noonode ; ase newnede —y noxtshead mytext, Wwad’ next = Reonode,tr Mne Vist hos only one clomert jhe nox pototes will potnt te tLeels Tnsert ofler a specified neal. To iment oa nede af a specific node, dhe node vw located bys Arawensings from re Jost node: i iol 4 20] 420) i hel -—pel lo 20 {>| 30| head ~ eT Hosened void: ined _aftan ink search, int val) Suck node x ) Anewnodeyeprey; Newrode = malloc CetgeoF Cobruck nodded >; tem = head, next while an —>naxt | ahead -noxt 24 t prev Henup np > data| = Seoncl) 3 temp 2 lamp eet ;ieee —> data = = search) newrede—ynoxt = —ynoxty tem next = navonode j 4 Vene- hemp porobs to dhe specified node. and nawrede is dhe nownode to be lnsentad- Trnert dart: To iwent on elomont at end, Ane \SL need ko be dvavensed ALL Ane Look cama - ace aaa (n votd insextlast (dnt val) v struck node xnawnede ; 2 Mead next; nownede = noabloe Cetgeop Cotruct node); while Ctenp} a> noxk | = head —>noxt) enpe eng raat:nownoda —ynaxt = temp —rnext; Lemp = next = neonode, 5 | Deletion. | To delete an clement, te element is Sound by traversing, From Ana. haad node. oe fom ed head __ | vord dalete Ctnh val) a. Syruch node atomp, travel, ® prev j —> nab; wh a Pl head next ad “j *ensp-adata | aval) wv pYev = 4 ben = tewp —rhext 5 iy Ctemp — data = =val) pen % Prev —> next = te. nat ; yy eo C oe ebe 2 printf C'Eloman not Jéund"),Here tan eaus bo Abe node Ao bee dalled and prey Ree be Aas previews node af Deletiom & done lox, change Abe porntes oy Aewup Xe pont bo Abo noxt node oF doleted node. Deplay, vod display Cc) ahuad 7 tex; whole © heap —rnoxt | ehaad -rext) i prinly oz), hemp dated); vena kemp —enext ; 5 4. To -disday Uke Vit, ane clemart O “ Lwovonsek From Jost to hut rede, Awe la . Ane hola pat oF cocl rode. ‘ a"Find] Seanch 7 vet, Seonelo C ist geome) Lv Lamp = Waad at wile Ctempy next] head next 43 emp dota, = search) Aewp 2 rex; Ye wrdoter == sea) peng CY Elasmonl Sound! Sy a peenty cs Elamant not Found 3; 5. The Wt & jvonensed unbl are elemant Jona. ov Ane end oF tre lit © veochad.Dovery \ ween her : b Aout Linked, a » oop oF vedts vwhide booties vepruent a sequance. ‘ven node Nas Moves pools — Pate yidd nat sores Wne date: -~A porter Ahot pools to the previous wos. - A petaler thot potas be the naxt vede. Prev dota! | Syevevure Or Nove Sbeuck pede 1 vat dala; Shuck vedo & prev; Slyck pede x nek, 4 ahead, Opernarion — Tmertion — Deletion — Seaxc\y = Dopey.pe lel fet ot el etl) = head. = Hene Ahe ysl weode & Aha header necks. Trrertion . Based on the pocttion ey imention, tk b categorized Oo ~ Trent ab Fock — Insert at bask — Ineent of ts a specific wih Trsert ab Finest : To inseal ab Jost, oO now node in creaded headin node points dp the nas node and naw node potas to dhe Second Node . lead CAE Set et pl hood a Ay! to inerting, Ao utvoidl tnsentieeint valy Siruck node * Nano 7 | Nownode = malloc Corgeok ( struct Neda) | newnede —> datas val. pownede —> PY = wor. F Chead 22 no newnedae —> noxrt SNOLL 5 | naopo de —y prey NOH, Ev = Nano o else v remy choad; nawnede. Sr naxb ehaod, oad anawnede ; temp —7 prev = nownede » 5 y. PTder insertion the nawnede \econen dhe heacer nede- tne bell dhe prev and nox Porntes road to lee asstynod appepiiiakely@ ul de He vod insertloak Cint vald u Sbruck node x Lempernonade ; choad, wowneda= malloc Csige of Cstvuck node) ; nowode. JT datas val; uF Choad. = now) Y ead = nownede, \ead -ynort= ous haad —> Prev > NULL, sue u wile C: =r naxt | ero) z hemp ar rext: —noxt eronede ; newnode +r pray = hemp ; navsnode —yrext = SOLE; a 4.\Z the lab & , Ake neonade will becom» Ane headen node - he previous. and Noxk porter a 7 . AF Ane Vid has clomants , & Abe Last clomant wh the lists The prey and nat poctin one asetgnad agproprisdely., Trsexch, Ofte a, specific node. To insert 0 OO spect. : v located, | ie pectic node, 4 Avavensh was yoet alamath. a hem ao Afles Insenting do pid Ke bl ee el Oh] Ane Wt ie draverseA until the clowent % Found ey worl dhe end oF lot yaoclud ond insertion t dona eloment we Jound -; & void Vrbert af bes Cint seandy, int val) Suck node atoup, Anewnodlegrent, | ahead, | rwoile Clemgl =rsonr AA emp ardeta | =seanch) a next, 3 Cheng data == Seanch) ones malloc Csi. rrnede > dala _ newnede > nog — oye os Nhwnede > prev = np 7 noxtic wa? —Frrext = naonodley, iy Cnoxtil = povEb) next, > prey = wurde ; *7. Coty node) ; else printy O Specified element nob wm list"); Here nawnode tr the node bo be inserted, aA *» Ahe Speci) ved node and nob) ts Ve noxt node oF temp. Tha Wertion ts done between femp and next)Deletion To dalete an clement Yo clement vo located, by traversing From Me Furst claw) Afler Finding Ake element, Abe next poirten oF Previous way, of alee te ene bo pout to Ahe noxtnode We prev pointes oF nxt node wade to point to previows node of doleted Yode- Pees FOSS “head void dilebe Cint val L Atruch pode x Lewpapaan, nat ten z before Lemp clad: oF Lreap | >NULD t whileCremp| = NULL Sbhenp >deda (aall) heaps hemp SaeeneYC temp > data zzval) i ‘les. tomy 7 Pre 5 Aten = teup rhaxt ; | Jp sono 4b aftes ==noD head = vLL, gee Cen) ' a L before —F next 2 temp noxt; te zk wy , Meee ero 3 else PREC’ Ehomand nob in at! », Dvplay, void dina a L Suck 6 Oo item; = head, wenn Champ) s nuLLD Printy C val 7 —ydala, 4 4 vende: temp ysFind, ‘ To Sind an clament, Aho Vis dravensed yor For umlil the element & found Os WL Ae end oF lot & vealed. | veld Find c inh Seomen) | Y such node redone choad; while Ctemyp \sroun Ab tarp 2rdote\ =senach) ‘emp zhoup > next; aT (Aone > data == Seon) prtotyC® Elament Found. Fo Gat? d; ebe F protec’ Element oot Found. >; 4. Yoseible Questions: tb How o node iW repreerted ww DL? 2- Define dowrly licked lowe 3 Apecify Ane advortoge> 3.chinodvamrtagcs 2) DLL A Exglalo DLL apt jw detail with ‘Fobynomiad Manipulation . ea expression) cay) be vepreserbe wing Boked Lat . The nedis cantar Nyree parte coegpietent, exponant and pointe te Ane waxt node. Abructune of pode: buck poly 1 tov cog; \ee Lot exp, struck ply anoxty 4 Ex: ax? 2S +7 GEHL @2 AP Mae exponents ane nok equal, choose dhe polynomial Noda Ahad Iho» opreater exponent value, copy the node b veuthant Lib- BP a, \a\3 ata P L The exponents anc -nole eal, vi We vode Krol bos Vopr exponent value B3: \sis\4 Ropeat Sheps 2 ord 3 until it veache Dae end or pollo Uno \ob- In Ane next slop Prand Pro's exponants ane compared, the exponant ane not equal. : Po aia % Geld Ge@) To the next ctepe Are exponent ane a binee Uren one equal Ahein coeFFtaan ane added. » Galea er e\s\ 4 fal2|4 vel FL aro fe: si tebkldskihn Agen AMe exponents one vob qual, Abe nde voitly hegheat exyonent WwW Laken. » GhlS-PH il aera Por BELG Gh © GEL Lee re and of \od) w veached, Ae 2lomans oF \oto Ww civedtly copied - es [els HEBEL EeSoruch poly & Poysda Catruck poly re, Struck, pay xP a Sud node * Te, bewp Wot cof, exp, P22 malloc Catgeof cotruct poly) y =pe while Cry amore Lb L Fo) =mvud For > pas P27 exp) Ps weg Vrcoey +F2 woes; 73 > exp = P) exp, Pi = TS nexrj Poe Po ~prext. eloe & CPhi—> exp > f2a—7ap> Pa—> Corp = Ry coey; Pasa Ae ai\narat ONNi PLS —proxt; 5 else v Ps > ef 202 > coef, 3 > expe Pr exp; Po = Po next;Aengemallo.cstse Csbuck Ply, deme, Arnext = yuLL; PS next= hemp a wrile CP) our} P2\ =yuELd LF cry benvrr) P2—> P= Pi exp, 92 > carck = Pj rtoef ; Nah ehext ebe Ps > exp= Fa veap, Pa 7 Ook = Pa > Conf, Proh > Next; = Menpic malloc Cetge oF Cobruct poly), ly rext = QvLL, 93 —pnext =templ, 3 Yeduon Aewup 7youd, dinglay © Such pehiph & ps) primty Cl The sum ia 7; while Cpaly y= 0ud ) prime yd, Nh dt” Pd 7 OF, P37 exp; Pac Pa > next > 3. The ingly oy ply nomial. Ww don “3 he Hravensing From Furst bo last elamant we Ake feszible Quote . & How Pelsynorntas. RS ve prencsritad wares linked. int? 2. Explain. polynomial wonipulation with. velevant cxaple and cotey. ey bk tee + Pea domi c oD. (\ Coe ory Ceexdinator