ned tee TM pe = Linked. list isa linear alate. tructure awh A _CHlection of data elements or pies = Successive elements jn LL are — -Lnihe | by pointer and the last het Sleiay int to ‘null.” aa t= rere Je a specia) node called ‘head’ < | b fstart? node which always pants te | AP the fist: é | Head /atart | E. I Peele x Bo 4o- * Basie terms jn Le: Bes Node ele. in LLis called node. as = Ne. consists OF 2 parts. first fame tS info-/data part & second part js neato’ |__ pointer part - ! : —Page No| NULL inter: -When' the Le js emp or nd, node in tt , then ee Os ™ EM Nutt value is sel 1d pointer. jre [PTR= MULL] f ed Empty list: - Wien there is no node ina linked ist» then \t__ \ js c/a etn Jinked lish? \ Dvartages eee Lier \ \ Linted V Nist provides as ae +o jnsert Brel i, delete nodes a oe User can increase or Y decrease the size of list a i Maser or Bee a node. Linked] list follows an efPiclent memory aillecation | BE Geh as vidites Aqtaiars not MWVieoneemie contjgiou.s memory location like an: array. Here’ nodes Vare Stored random) Thats why it re duce the was f jemory -space. 1 =a Cal Ne need to pre- define the size of Jinked lFineertion. ane deletion is ee optimal in Jinked Jist: Unlike an array , we neeel not shift or chang | : the position of an¥ item,ry allocation: LMA _W eqn aljocite 4 memor LD State 0: v = Mlemor: Is jg allocated eluxin compile +ime can't (allocate and _cleallecate ‘memory eluring execution . Ef | — Here, Stack date structure js nites i Static MA is less efficient than ofynesnlc A _ Memo e | ei 04 amie MA: | = Timer is abt at runtime : Allocatton cind de- allocation can be Toe using ‘stlibsh - ad allocates memory from heap ° So that it brary function _o{Date J cocci ce + Ubrary Functions ofor meniorg alloation : ih a: Majjoe CMA) malloc CY) = It allocate single blek of | requested mertory of Specified mae = : i Suntan = void * mMdlloe Csize ) J Here, size > block size 4 eee eet = Cine) malloc (6xsize4 Cint)) for nas Senin yore eo bate i TE 2c bye available | 2+ Calloce (continous allocgthon ) caivecc> — I+ performs same operation like malloc bat 5 differene js that it initializes each black with elefault value zero penne -T+ has 2 parameters as compared to malloc. Santen ss wal * cajloc (omeieen) -ptr= Lint * ) calloe Cn, eizeOf Cint) ) > e-4 =! 5yy —> 4 bufesforit LAL Als 1A 3. Free function >freec ) It is used te de-allocate memory space which is allocated by malloc & callocy funetion. - Malloc and calloc function are unable +0 de-all memory by their own ~ Whenever de-allecation js done by using fre it helps to reduce wa op mr free} .cleat free Lint ie —— oo pire Cio * Dicalloe Caslelz2OF Cin ) Sreleased J] 4 Realloc 2af6 change memory allocation of Previously Memory Pealloc fuietlen | Is used — = ae memory allocated by alloc ane maloc function {5 insubficiend then realloc function js used to reallocate menor Aynamical)y. Syntan na ptr realloc Cptr, newsize)s = ae = mae Pere reathoe (| Memory representation using LL: i - List ele. dre store arbitary order - Ana rep” ives sto data; \ but LL uses an layout to__store the lata.* | Garbage collection : | We can maintain linked list in memory by assumin ithe possibilities of inserting new node inte the list: | For that we. Wank some memory space se that we can | inserE new nede in the fieeaea 4 | Alse if _we want +o delele any node frm list» then that memory Space is ysed fo future purpose So, theve js q Special Space in aq niemon which a consis of unused memory cell which is call “ available s Space.” ¥ n(a rc See e__+technig collect 1)_deleted 2p pace into ree storaye list js called as “ PMTPRE rhage coljectjon. takes place in sug way Habe irst " computer runs through all the list, markin al\_the cel) those are turrenty used so dala [marks the free Space in the ~ memo _. Overflow : eri RS = When new data \e sere nto the fist + but _ there js no available space ie free Storane listts expt then‘ overflod ’ occurs -We an handle this situation ba adeling the space when we ’re woor king with lata uctyre Underf low: Sle When we want to delete aT data from the list and _ the Ilet jc empty the ‘situation is called as ‘underflow’ ee oh [inked list: raversing : - To couht the number of elements: ac nead Lo Lys] 4-14 Jo 20 20 30 30 49 PIR= start ilips. ia fT = 42 EY SInfObPtR] =A. ting Fre > ana TRI eitthi for +traversin Ai Seb pres ster jen Repeat step 2 & 4 ynti) PIE ANU 3: APPLY PROCESS To anNFoLrereg Step: Set Pre > LINK leTRI al Steps: Bit Searchin Be L Saran le ls used) to find out the Joca-ti on the node where item First ap pear in list . 4 Unsorted list - C = leb> we've o list 5 bub the data in fel list iat mot sorted & If we want to search any parkigular: element in the Jist , then we? ve te traverse in a list using pointer variable ae fleorithm : a Seatch (INFO, Next, ptr) a Step £3. Seb prs Start : ei Step 2 Repeat Steps until pte ¢nuw 4 If stew > INFO [Ptr] then Set (ae Link Cet].Unsorted list 43 oi 2Seb per owe | 2. car * Sorted list - ae__A)aorj}thw : Search CINFO, Next, Ptr) Step 4° Sof Ptr= Start Shep 2: Repest step 8 til) Ptrl= NULL Step 3: if zen. 222 INFO C peas see toc] Prep else Pees cbink: DPEr) vekep +: ExitBEthsertion. —“Insettion” refers to: the eration of als element in the existing linked list. “ = Insertion of new elemént jin the list a Ne, Pa @ ways.-@ In the oe ot list U @ At the given pes @® he the Yast position Insertien in Sorted het Start es peel a Fee eimai: Head—r fw => e ae? for 20 30 S° 4o sper Avai) Me nv pweds | ead Frew t 7q ae ae a > =) x i =a " oe aso 7 280 oo X 1 Arar Hate FAver{] : = Je insert the new element ints the existin Po} ou} a Sains should be alone - f e SDMNEating AS ew node for neo clement fon the abkilable list - 2 fissignin data a new element . ed 3) file ¢ the goiter:a Th Maonthm : srk be (Info, New ,ttem, Link, Avail, start) oil 5 Step 4: if start = NULL then exit Step 2: if pvail=Nurt then overflow octure and exit \ Step B: Set Avai|- New \ \ ae Set Avaj) = link LAvail] Ss 4: Set info L New] = them Step 5: Link [New] = Head 6: Head- New >? Exit Peeudocod e : t Snsert+ _ beg Cstruct node” Head , intdata) i Ee Struct node * new = || I new = (struct node) malloc (size OF (struct node) ) | new —>clata= stem how —> Next = Hedd Head = new 7 i Return Head<< Jove 2200, 2000 Bove t | visting item sass. 5 | neu item + a6 hae F 2% Pier we (Head, Link» nto ) | Step 4 Avail = NULL | write overland exit Step 2: set nea Avat | and Avai\ = Link Cavasi] go: Se Infol Naw] - them yStep 4 iF LOC=NULL then ° Set Link ENew] = Head and Head . New else Link E New) = tink [L0cq : Link L101 - Naw cles Exit-Scr Me Deletion! \refdrs 461 ye operation piremovina lal nade N ee ie | | Deletion can be lone in @ ways i- i) Delete a node from the 4st pos”. D node | from the ven oc”. last noele from the list’ \ \ \ \ \ \ \ N Pseurdocod 2 > ie del_1** Cstruet_node* head) i Sc! Struct node* ptr 5 if (head -~ Nutr) i i A inet eddy Aeai) | Prarie sre js eu DS Zoo = Avai| i 4 ~ Avai| - ; elee’ = Loe ie ae ( ead = heasd > next) -200 } = Tree (p41); = relum head.Sa st Algorithm: ; Algo - pel 4st ( Info, ptt a step 4: jp head = NYLL ‘ write. underflow and ask Step>- Seb _ptr= head Sepa, Sok ead = Linkt head J Step 4: bok Cloe1/Lhead] = ULL Avail Ava\le Loe Steps: Exik ac Pseuqocede + del. last_C struct node , * 7 head) struct snole* teem pb, * prev if a NUD f ae List iis emp mB) else pb (hend—> next> Nur) A t freeChead eas POL fas ony tert head = NULLstep 2: Set ip Vink [head] NULL ; link Dhead] = Avail © head = Nuje ares set ptt = head 3 7 Repeat Step Ss urd} fink Eptr) fone Set prev = pir Seb pir = link Cptr] Set fink rev] = -Nubb link pares Avail Avaj} = Loe Exiteee — Copy | clone single psorplerity ee ao sco mplenily oun) GA eta sie eee . linked list: > |. Here, we? ve. “he “dea) with two polivers = one ts “nexpy ae which pei fo the next element in te 7 random ? pointer which points te any node j in I jenna st a cloning the LL, jt takes O(n) time . ; pointer: pins ts the next node is Bea ee haven 't 238540 a add” 40 _randém Poiter. a a, sian te follow sume sLl i e next po; ext nede _ ii ow. 4 >) ohh je a anata ele inom to Yas abs Toop node b of original liek. es nip { ootolog: AB ARE Ven ow, rovide the link to random pojpter, we U: the stmt. ' = Clone—> r= clne—>r—>r nex oat. For aach node in 4 Sepied Ee al held , Bee @ Consider, Pade. a. from scape a Mmnananeteteh the address of node ain " original wLL- Ww 2 Or = are Se next rine CspandS te net F cle 7H “Randora pointer of nofe a in orjginal LL held the add" of c | then the next of & held the add° i ode c from Clone LL. «- dene of @ hold add’oP eines |@_ consider , node b frem copied LL which held ey eat add” of node b in oy incu} BLS bares 2 OF" wae bore br > a— next ane ow Random pointer of node b in ont ina) lined fist, e, thelds the add’ of a, then the next of « hold the Tot node a trom clone LL-® Consider node c from coppied Li which hold gow PF h bstd a address of node c¢ jn orjainal LL- er = cre > next Random painter) oF node < in origina LL_ hold! 4am Betesenet 2 dithenithe Next of e hold the adder of node e frm clone LL- @ consider, node qd from copied LL which hole the_| address of node ids in original LL- ae gtd dare dS Fle next = Random pointer of nede_q in original LL hold’ laddh of co then! the neat of © held the addres oF node ¢ from clone LL.© Coneider node e from copied LL which hold the address of node e in a ‘original Be emr - 2 Shp, Saeoneee Random pointer of mde e in original LL held the address of 4 then the neat ‘of _d held the Address of node d trem clone LL- Head ea] EEE a ae Jd} ela el% Elle G elsPik etre oN Ste ee rel Ele fic So 2 ; vay Prev. = Bek i (eV = 40] ‘Head = oar : bi SH = 40 > next Pee 4 eh ae Curr = ak / wor EAS te ae + Nabe ot Curr —> next = Prev 7 Le im) Head = Head—snext 20—> next a. ws | | os[baa , A @neatenation of linked list: N ~~ © Gnewtenation of aigle LL’? means append Men new jist = they etlistne list: N Head - li + 4 nN N A 4fe] —e c [ x ‘ to 20. 20 80 «35 Yo XY Head y 2 . [x] f l | Algorithm + i “4 N ae then ; weturn Lo y S Glep 2: if la= Nule then ti . seturn 14. 3 | 3 T step 2: Set ptr = head (14) 4; do traversing in list la 6 "Es Arply ae To nfo [P | : set pins head (L»\sei€ ho = print (“List 2 is empty raha while C por —* neve! = ull) i prr= ptr > next Be r Pir —> n ert Sho ¥ a easCee —— a = e eer = aye Jaimople / linear ta “| Tjpes ot linked jist ee 4.| CTreular linked list = - dna sipgle Jick 5 we can move from a poe any. other Vinode in one divection only 3 bE in ciMuular!ulinkedo |isb githe link eld of last node aleoey point ‘Le the head inede-- a - Heres nal) poled \s not presen a ch a See + Operations of cirewlar LL: i : @_| “Traversing: Seat nal DAE Le atort (Same OR single eS) i T c va ® | Searching : Ceame as single LLD @ | Sheertion : — i) Insertion jn the bgjincing. Headb \ Setistart NULL then exit if avail = Null then overflow oceyrs and exit Set avail= NEw set aval] = linkCavaif] Set link [New] = start start = NEW link C Lest _] = NEW es here herr hte lise ee rte cre ated: (coe! TT)