[Speel van musiek] 

DOUG LLOYD: OK, so op hierdie punt in die kursus, Ons het 'n groot deel van die basiese beginsels van C. gedek Ons weet 'n baie oor veranderlikes, skikkings, wysers, alles wat goeie dinge. Dit is al die soort van gebou in te sien as die grondbeginsels, maar ons kan meer reg doen nie,? Ons kan dinge kombineer saam in 'n interessante maniere. 

En so laat doen, laat ons begin tot tak uit wat C gee ons, en begin om ons eie data te skep strukture gebruik van hierdie gebou blokke saam om iets te doen regtig waardevol, nuttig. Een manier waarop ons kan dit doen, is om te praat oor versamelings. So Tot dusver het ons een soort data het struktuur verteenwoordig versamelings van hou waardes, dieselfde waardes. Dit sou 'n verskeidenheid wees. Ons het versamelings van heelgetalle, of versamelings van karakters en so aan. 

Strukture word ook soort van 'n data struktuur vir die insameling van inligting, maar dit is nie vir die insameling soos waardes. Dit meng gewoonlik verskillende tipes data saam binnekant van 'n enkele vak. Maar dit is nie self gebruik om ketting saam of maak saam soortgelyke items, soos 'n skikking. Skikkings is groot vir element kyk, maar onthou dat dit baie moeilik in te voeg in 'n skikking, tensy ons die inbring by die einde van daardie skikking. 

En die beste voorbeeld Ek het want dit is invoeging soort. As jy ons video onthou op invoeging soort, daar was 'n baie koste wat betrokke is in wat af te haal elemente, en skuif uit die manier om iets te pas in die middel van jou skikking. Skikkings ook ly van 'n ander probleem, wat is onbuigsaamheid. Wanneer ons verklaar 'n skikking, ons kry een skoot op dit. Ons kry om te sê, ek wil hierdie elemente. Kan wees 100, kan dit wees 1000, kan dit wees x waar x is 'n getal wat die gebruiker het ons op 'n vinnige of by die opdrag lyn. 

Maar ons kry net een skoot op dit, ons kry nie dan sê oh, eintlik ek nodig 101, of ek x plus 20 nodig. Te laat, het ons reeds verklaar dat die skikking, en as ons wil om te kry 101 of x plus 20, ons het om te verklaar 'n heeltemal ander skikking, kopieer al die elemente van die skikking oor, en dan het ons genoeg. En wat as ons verkeerd is weer, wat As ons werklik nodig het 102, of x plus 40, ons moet dit weer te doen. Sodat hulle is baie onbuigsaam vir die grootte van ons data, maar as ons saam 'n paar te kombineer van die basiese beginsels wat ons reeds geleer het oor wysers en strukture, in die besonder die gebruik van dinamiese geheue toekenning met malloc, ons kan hierdie stukke saam te stel om 'n nuwe data structure-- n skep enkel geskakelde lys ons dalk say-- wat ons toelaat om te groei en krimp 'n versameling van waardes en ons sal nie enige gemors ruimte. 

So weer, hierdie idee noem ons, hierdie idee, 'n geskakelde lys. In die besonder, in hierdie video ons praat oor enkel gekoppel lys en dan nog 'n video sal ons praat oor dubbeld geskakelde lyste, wat is net 'n variasie op 'n tema hier. Maar 'n enkel geskakelde lys bestaan ​​uit nodes, nodes om net 'n abstrakte term-- dit is net iets wat ek roep dit is 'n soort van struktuur, basies, ek is? Net gaan om dit 'n node-- en dit noem node het twee lede, of twee velde. Dit het data, gewoonlik 'n heelgetal, 'n karakter float, of kan 'n ander tipe data wees wat jy met 'n soort gedefinieer def. En dit 'n verwysing na bevat 'n ander node van dieselfde soort. 

So het ons twee dinge binnekant van hierdie knoop, data en 'n wyser na 'n ander knoop. En as jy begin om te visualiseer hierdie, kan jy dink oor dit soos 'n ketting van nodes wat saam verbind. Ons het die eerste node, dit bevat data en 'n wyser na die tweede knoop, wat bevat data, en 'n verwysing na die derde knoop. En so dit is hoekom ons noem dit 'n geskakelde lys, is hulle met mekaar verbind. 

Wat beteken hierdie spesiale node struktuur lyk? Wel, as jy onthou van ons video op definieer persoonlike tipes, met tipe def, kan ons 'n structure-- definieer en tik definieer 'n struktuur soos hierdie. tyepdef struct sllist en dan is ek die gebruik van die woord hier waarde arbitrêr om enige tipe data regtig aan te dui. Jy kan slaag op 'n heelgetal of float, jy kan hê wat jy wil. Dit is nie beperk tot net heelgetalle, of iets soos dit. So waarde is net 'n arbitrêre tipe data, en dan 'n wyser na 'n ander node van dieselfde soort. 

Nou, daar is 'n bietjie catch hier met die definisie 'n struktuur wanneer dit 'n self referensiële struktuur. Ek het 'n tydelike het naam vir my struktuur. Aan die einde van die dag het ek duidelik wil om dit te noem SLL node, dit is uiteindelik die nuwe noem deel van my tipe definisie maar ek kan SLL node gebruik nie in die middel van hierdie. Die rede hiervoor is, ek het nie het 'n soort genoem SLL node totdat ek getref hierdie laaste punt hier. Tot op daardie punt, ek het om te hê 'n ander manier om te verwys na hierdie tipe data. 

En dit is 'n self referensiële tipe data. Dit; s 'n data tipe van 'n struktuur wat 'n data bevat, en 'n verwysing na 'n ander struktuur van die dieselfde tipe. So ek moet in staat wees om te verwys na hierdie tipe data ten minste tydelik, so gee dit 'n tydelike naam van struct sllist laat my toe om dan sê ek wil 'n wyser na 'n ander struct sllist, 'n struct sllist ster, en dan nadat ek die definisie voltooi het, Ek kan nou noem hierdie tipe 'n SLL knoop. 

So dit is waarom jy sien daar is 'n tydelike naam hier, maar 'n permanente naam hier. Soms jy kan sien definisies van struktuur, byvoorbeeld, wat nie self referensiële dat nie 'n specific naam nie hier. Dit sou net sê typedef struct, oop krullerige brace en definieer dit. Maar as jy struct is self referensiële, soos hierdie een is, wat jy nodig het om 'n spesifiseer tydelike tik naam. Maar uiteindelik, nou dat ons dit gedoen het, kan ons net verwys na hierdie nodes, hierdie eenhede, as SLL nodes vir die doeleindes van die res van hierdie video. 

Alle reg, sodat ons weet hoe om skep 'n geskakelde lys knoop. Ons weet hoe om te definieer 'n geskakelde lys knoop. Nou, as ons gaan om te begin gebruik van hulle inligting in te samel, daar is 'n paar van die bedrywighede ons moet verstaan ​​en mee te werk. Ons moet weet hoe om te skep 'n geskakelde lys uit die lug. As daar geen lys reeds ons wil een te begin. So moet ons in staat wees om om 'n geskakelde lys te skep, ons nodig het om seker te soek deur die skakel lys om 'n element wat ons soek. Ons moet in staat wees om in te voeg nuwe dinge in die lys, ons wil ons lys om in staat wees om te groei. En insgelyks, ons wil in staat wees om dinge uit ons lys te verwyder, ons wil ons lys om in staat wees om te krimp. En aan die einde van ons programme, veral As jy onthou dat ons dinamiese toekenning geheue om hierdie lyste tipies bou, ons wil almal dat die geheue te bevry wanneer ons klaar is besig met dit. En so het ons moet in staat wees om 'n verwyder hele geskakelde lys in een misluk ophef. So laat ons gaan deur sommige van hierdie bedrywighede en hoe ons hulle kan visualiseer, praat in pseudokode kode spesifiek. So wil ons 'n te skep geskakelde lys, so miskien kan ons wil 'n funksie te definieer met hierdie prototipe. SLL node ster, skep, en ek verby in een argument, sommige arbitrêre data tik weer van 'n paar arbitrêre data tipe. Maar ek returning-- hierdie funksie moet terug te keer na my 'n wyser, om 'n enkel geskakelde lys knoop. Weereens, ons probeer om te skep 'n geskakelde lys uit die lug, so ek moet 'n verwysing na dat die lys wanneer ek gedoen het. 

So, wat is die stappe wat hier betrokke? Wel, die eerste ding wat ek gaan doen, is dinamies toeken ruimte vir 'n nuwe knoop. Weereens, ons skep dit uit dun lug, so ons moet malloc ruimte vir dit. En natuurlik, onmiddellik nadat ons malloc, kyk ons ​​altyd om seker te maak dat ons pointer-- ons nie terug te kry null. Want as ons probeer onderdanigheid n null pointer, ons gaan 'n ly segfault en ons wil nie dat. 

Dan wil ons in die veld te vul, ons wil die veld waarde inisialiseer en inisialiseer die volgende veld. En dan wil ons aan- uiteindelik as die funksie prototipe indicates-- ons wil om 'n wyser terug na 'n SLL knoop. So, wat maak hierdie lyk visueel? Wel, die eerste gaan ons dinamiese toeken ruimte vir 'n nuwe SLL knoop, sodat ons malloc-- dis 'n visuele voorstelling van die node ons net gemaak. En ons gaan om seker te maak dit is nie null-- in hierdie geval, die prentjie wil nie hê getoon het as dit nie was null, Ons het uit die geheue sou hardloop, so ons is goed om daarheen te gaan. So nou is ons op te tree C, inisialiseer die veld nodes waarde. Wel, gebaseer op die funksie noem ek hier in met, lyk soos ek wil om te slaag in 6, So ek sal 6 in die veld waarde. Nou, inisialiseer die volgende veld. Wel, wat ek gaan om daar te doen, daar is niks volgende, regs, dit is die enigste ding wat in die lys. So, wat is die volgende ding in die lys? 

Dit moet nie wys om enigiets, reg. Daar is niks anders is daar, so wat is die konsep wat ons ken wat nothing-- verwysings na niks nie? Dit moet dalk wil ons 'n null pointer daar te vestig, en Ek sal die nul verteenwoordig aanwijzer as net 'n rooi boks, ons kan nie verder gaan nie. Soos ons sal sien 'n bietjie later, sal ons uiteindelik kettings pyle verbind hierdie nodes saam maar wanneer jy druk op die rooi boks, dit is null, ons kan nie verder gaan nie, dit is die einde van die lys. 

En laastens, ons wil net om terugkeer 'n wyser na hierdie knoop. So sal ons dit noem nuwe, en sal 'n nuwe terugkeer sodat dit gebruik kan word in Watter funksie het dit geskep. So is daar gaan ons, het ons 'n enkel geskep geskakelde lys node uit die lug, en nou het ons 'n lys wat ons kan werk. 

Nou, laat ons sê dat ons reeds het 'n groot ketting, en ons wil iets in dit vind. En ons wil 'n funksie wat gaan waar of vals terugkeer, afhangende op die vraag of 'n waarde bestaan ​​in die lys. 'N Funksie prototipe, of verklaring vir daardie funksie, kan lyk this-- Bool vind, en dan wil ons slaag in twee argumente. 

Die eerste is 'n verwysing na die eerste element van die geskakelde lys. Dit is eintlik iets wat jy wil altyd om tred te hou, en eintlik dalk iets wees dat jy kan selfs in 'n globale veranderlike. Sodra jy 'n lys te skep, jy altyd, altyd wil om tred te hou van die baie eerste element van die lys. Die manier wat jy kan verwys na al die ander elemente deur net na die ketting, sonder om wenke te hou ongeskonde elke enkele element. Jy moet net om tred te hou van die eerste hou een as hulle almal saam vasgeketting. 

En dan is die tweede ding ons weer verby in is arbitrêr some-- watter tipe data ons soek, want daar is die binnekant van hopelik een van die nodusse in die lys. So, wat is die stappe? Wel, die eerste ding wat ons doen, is skep ons 'n dwarsleggende wyser verwys na die lyste kop. Wel, hoekom doen ons dit doen, ons het reeds 'n wyser op die lyste kop, Daarom het ons nie beweeg net dat een rond? Wel, soos ek nou net gesê, dit is werklik belangrik vir ons om altyd hou van die heel eerste element in die lys. En so dit is eintlik 'n beter om 'n duplikaat van die skep, en die gebruik dat rondom, sodat ons nooit beweeg per ongeluk weg te beweeg, of ons altyd 'n wyser op 'n punt wat reg op die eerste element van die lys. So dit is beter om 'n te skep tweede een wat ons gebruik om te beweeg. 

Dan het ons net te vergelyk of die veld waarde op daardie node is wat ons soek, en as dit nie, ons het net skuif na die volgende knoop. En ons hou doen wat oor en oor en oor, totdat ons óf vind die element, of ons getref null-- ons het die einde bereik van die lys en dit is nie daar nie. Dit behoort hopelik lui 'n klokkie aan jou as net lineêre soek, ons net replicerende in 'n enkel geskakelde lys struktuur in plaas van die gebruik van 'n verskeidenheid om dit te doen. 

So hier is 'n voorbeeld van 'n enkel geskakelde lys. Hierdie een bestaan ​​uit vyf knope, en ons het 'n verwysing na die hoof van die lys, wat lys genoem word. Die eerste ding wat ons wil doen, is weer, skep dat traversal wyser. So het ons nou twee pointers daardie punt om dieselfde ding. 

Nou, sien ook hier, ek het nie moet 'n ruimte vir trav malloc. Ek het nie gesê trav gelyk malloc iets wat node bestaan ​​reeds, dat die ruimte in die geheue bestaan ​​reeds. So al wat ek eintlik doen, is skep 'n ander wyser om dit te. Ek is nie 'n bykomende mallocing ruimte, net nou twee pointers verwys na dieselfde ding. 

So is 2 wat ek is op soek na? Wel, nee, so in plaas ek is gaan skuif na die volgende een. So basies sou ek sê, trav gelyk trav volgende. 3 wat ek soek, no. So ek bly om te gaan deur, totdat uiteindelik kry om 6 en dit is wat ek soek vir gebaseer op die funksie oproep Ek het op die top daar en so ek gedoen het. 

Nou, wat as die element Ek is soek, is nie in die lys, dit is nog steeds gaan om te werk? Wel, sien dat die lys hier is subtiel verskillende, en dit is 'n ander ding wat belangrik om met geskakelde lyste, jy hoef nie te bewaar hulle in 'n bepaalde orde. Jy kan as jy wil, maar jy dalk al opgemerk dat ons nie hou van watter getal element is ons by. 

En dit is soort van 'n handel dat ons met geskakelde lys verse skikkings, is dit ons het nie ewetoeganklike nie. Ons kan nie net sê, ek wil om te gaan na die 0 element, of die 6 element van my skikking, wat ek kan doen in 'n skikking. Ek kan nie sê ek wil om te gaan na die 0 element, of die 6 element, of die 25 element van my geskakelde lys, daar is geen indeks wat verband hou met hulle. En so is dit nie regtig saak as ons ons lys te bewaar ten einde. As jy wil om jou kan seker nie, maar daar is geen rede waarom hulle nodig het om bewaar in enige volgorde. So weer, laat ons probeer vind 6 in hierdie lys. Wel, ons begin by die begin, het ons nie vind 6, en dan voortgaan ons nie vind 6, totdat ons uiteindelik hier. So nou trav punte na die node met 8 en ses is nie daar. 

So die volgende stap sou wees om te gaan na die volgende wyser, so sê trav gelyk trav volgende. Wel, trav volgende, aangedui deur die rooi boks, is van nul. So daar is nêrens anders om gaan, en so op hierdie punt kan ons aflei dat ons bereik het die einde van die geskakelde lys, en 6 is nie daar. En dit sou teruggestuur valse in hierdie geval. 

OK, hoe kan ons voeg 'n nuwe nodus in die lys? So het ons in staat om te skep nie 'n geskakelde lys van nêrens, maar ons wil waarskynlik bou van 'n ketting en nie skep 'n klomp van die verskillende lyste. Ons wil 'n lys te hê wat het 'n klomp van die nodes in dit, nie 'n klomp van die lyste met 'n enkele knoop. So kan ons nie net te hou met die skep funksie ons vroeër gedefinieer, nou is ons wil plaas in 'n lys wat reeds bestaan. 

So hierdie geval, ons gaan om te slaag in twee argumente, die wyser na die hoof van daardie gekoppel lys wat ons wil om te voeg by. Weereens, dit is hoekom dit so belangrik dat ons altyd hou van dit, want dit is die enigste manier waarop ons regtig het om te verwys na die hele lys is net deur 'n wyser na die eerste element. So ons wil om te slaag in 'n wyser na daardie eerste element, en alles wat waarde wat ons wil byvoeg by die lys. En uiteindelik die funksie gaan 'n wyser terug om die nuwe hoof van 'n geskakelde lys. 

Wat is die stappe wat hier betrokke? Wel, net soos met die skep, ons nodig het om dinamiese toewys ruimte vir 'n nuwe node, en kyk om te maak dat ons nie uit die geheue loop, weer, want ons is met behulp van malloc. Dan wil ons vul en voeg die node, so het die getal, ongeag Val is, in die knoop. Ons wil die node voeg by die begin van die geskakelde lys. 

Daar is 'n rede dat ek dit wil doen, en dit die moeite werd om 'n tweede kan wees om die video hier breek, en dink oor die rede waarom ek wil voeg aan die begin van 'n gekoppelde lys. Weereens, ek vroeër genoem dat dit nie regtig saak as ons bewaar word in enige orde, so miskien is dit 'n leidraad. En jy sien wat gaan gebeur as ons wou aan- of net 'n tweede gelede toe ons gaan deur 'n soektog wat jy wat kan sien nie, mag gebeur as ons probeer te voeg aan die einde van die lys. Omdat ons nie 'n het wyser na die einde van die lys. 

So die rede dat ek wil te voeg aan die begin, is omdat ek dit dadelik kan doen. Ek het 'n wyser aan die begin, en ons sal sien dit in 'n visuele in 'n tweede. Maar as ek wil voeg aan die einde, Ek moet begin by die begin, deurkruis al die pad na die einde nie, en ryg dit op. So dit sou beteken dat invoeging aan die einde van die lys sou 'n o van N geword operasie, gaan terug om ons bespreking van rekenkundige kompleksiteit. Dit sou 'n O van n operasie, waar geword as die lys het groter en groter, en groter word, sal dit meer geword en meer moeilik om iets te ryg op aan die einde. Maar dit is altyd baie maklik om te ryg iets aan die begin, jy altyd aan die begin. 

En ons sal nie weer sien 'n visuele hiervan. En dan wanneer ons klaar is, een keer ons het die nuwe node ingevoeg, wil ons ons wyser terug na die nuwe hoof van 'n geskakelde lys, wat aangesien ons die inbring by die begin, sal eintlik 'n verwysing na die knoop ons net gemaak. Kom ons visualiseer dit want ek dink dit sal help. 

So hier is ons lys, dit bestaan ​​uit vier elemente, 'n knoop met 15, wat dui op 'n node bevat 9, wat dui op 'n node met 13, wat dui op 'n node met 10, wat die nul het wyser as sy volgende wyser so dit is die einde van die lys. So wil ons 'n plaas nuwe node met die waarde 12 aan die begin van hierdie lys, wat doen ons? Wel, die eerste malloc ons ruimte vir die knoop, en dan sit ons 12 daar. 

So nou het ons bereik 'n besluit punt, reg? Ons het 'n paar van die wysers wat ons kon beweeg, wat 'n mens moet ons eers beweeg? Moet ons 12 punt om die nuwe hoof van die list-- of verskoon my, moet ons 12 verwys na die ou hoof van die lys? Of moet ons sê dat die lys begin nou op 12. Daar is 'n onderskeid daar, en ons sal kyk wat gebeur met beide in 'n tweede. 

Maar dit lei tot 'n groot onderwerp vir sidebar, wat is dat een van die moeilijkste dinge met geskakelde lyste is om die wysers te reël in die korrekte volgorde. As jy dinge beweeg buite orde, kan jy per ongeluk beland orphaning die res van die lys. En hier is 'n voorbeeld. So laat ons gaan met die idee of-- Wel, ons het net geskep 12. Ons weet 12 gaan wees die nuwe hoof van die lys, en so hoekom doen ons nie net beweeg die lys wyser om daar te wys. 

OK, so dit is goed. So nou waar kom 12 volgende punt? Ek bedoel, visueel kan ons sien dat dit sal wys tot 15, as mense dit regtig duidelik aan ons. Hoe weet die rekenaar? Ons het niks wys na 15 nie, reg? 

Ons het 'n vermoë om te verwys na 15 verloor het. Ons kan nie 'n nuwe pyltjie langs gelykes sê iets, daar is niks daar. In werklikheid, het ons gelaat die res van die lys deur dit te doen, het ons toevallig gebreek die ketting. En ons wil beslis nie om dit te doen. 

So laat terug te gaan en probeer weer. Dalk is dit die regte ding om te doen is tot 12 se volgende wyser stel om die ou hoof van die lys, dan kan ons die lys beweeg oor. En in die feit dat die korrekte sodat ons moet volg wanneer ons werk met enkel geskakelde lys. Ons wil altyd die verbinding nuwe element in die lys, voordat ons daardie soort van te neem belangrike stap van die verandering van waar die hoof van die geskakelde lys is. Weereens, dit is so 'n fundamentele ding, ons wil nie om tred te hou van dit verloor. 

So wil ons seker maak dat alles saam vasgeketting, voordat ons dat wyser. En so sou dit die korrekte volgorde wees, wat is om aan te sluit 12 op die lys, dan sê dat die lys begin 'n 12. As ons sê die lys begin op 12 en dan probeer om aan te sluit 12 op die lys, ons het reeds gesien wat gebeur. Ons verloor die lys per ongeluk. 

OK, so een ding om oor te praat. Wat as ons wil ontslae te raak van 'n hele gelyktydig geskakelde lys? Weereens, ons mallocing al hierdie spasie, en so het ons nodig het om dit te bevry wanneer ons klaar is. So nou wil ons verwyder die hele geskakelde lys. Wel, doen wat ons wil doen? 

As ons die nul wyser bereik het, het ons wil om te stop, anders, net verwyder die res van die lys en dan bevry my. Verwyder die res van die lys, en bevry dan is die huidige knoop. Wat beteken dat die klank soos, Watter tegniek het ons gepraat oor voorheen Klink dit? Verwyder almal anders, dan kom terug en my verwyder. 

Dit is rekursie, het ons die probleem 'n bietjie kleiner, ons sê almal verwyder anders, dan kan jy vir my verwyder. En verder af in die pad, wat node sal sê, almal anders te verwyder. Maar uiteindelik sal ons die kry punt waar die lys is null, en dit is ons basis geval. 

So laat ons neem 'n blik op hierdie, en hoe dit kan werk. So hier is ons lys, dit is dieselfde ons lys is net te praat oor, en daar is die stappe. Daar is 'n baie van die teks hier nie, maar Hopelik sal die visualisering sal help. 

Sodat ons have-- en ek het ook getrek up ons stapel rame illustrasie van ons video op die oproep stapels, en hopelik al hierdie saam sal jou wys wat aangaan. So hier is ons pseudokode-kode. As ons 'n nul bereik wyser, stop, anders, verwyder die res van die lys, bevry dan is die huidige knoop. So nou, list-- die wyser dat ons verby in om punte te vernietig 12. 12 is nie 'n nul pointer, so ons is gaan na die res van die lys verwyder. 

Wat is die verwydering van die res van ons wat betrokke is? Wel, dit beteken om 'n bel om te vernietig, sê dat 15 is die begin van die res van die lys wat ons wil vernietig. En so het die oproep om te vernietig 12 is 'n soort van op te hou. Dit is daar gevries, en wag vir die bel om te vernietig 15, om sy werk te voltooi. 

Wel, 15 is nie 'n nul pointer, en so dit gaan om te sê, alles reg, Wel, verwyder die res van die lys. Die res van die lys begin op 9, en so ons sal net wag totdat jy al verwyder wat dinge, kom dan terug en my verwyder. Wel 9 gaan om te sê, goed, Ek is nie 'n nul pointer, so verwyder die res van die lys van hier. En so probeer en vernietig 13. 13 sê, ek is nie null pointer, dieselfde ding, dit gaan die bok. 10 is nie null pointer, 10 bevat 'n null pointer, maar 10 is nie op sigself 'n null nou Pointer, en so is dit verby die bok ook. 

En nou is daar 'n lys van punte, is dit regtig wys some-- as ek het meer ruimte in die beeld, dit sou wys om 'n paar random ruimte dat ons nie weet wat dit is. Dit is die nul pointer al is, die lys is letterlik nou ingestel dis waardes null. Dit wys dat die reg binne rooi boks. Ons het 'n nul pointer, so ons kan stop, en ons gedoen het. 

En sodat pers raam is now-- by die top van stack-- dit is die aktiewe raam, maar dit is gedoen. As ons 'n null pointer bereik het, te stop. Ons het nie iets te doen, ons kan nie bevry n null pointer, ons het nie enige malloc ruimte, en so het ons klaar. Sodat funksie raam vernietig, en ons resume-- ons haal waar ons opgehou af met die volgende hoogste een, wat is dit donker blou raam hier. Sodat ons haal reg waar ons opgehou het. Ons verwyder die res van die lys reeds, so nou is ons gaan die huidige nodes te bevry. So nou kan ons bevry van hierdie knoop, en nou ons het die einde van die funksie bereik. En sodat funksie raam is vernietig, en ons haal by die lig blou. 

So dit says-- Ek het reeds done-- die verwydering van die res van die lys, so bevry die huidige knoop. En nou het die geel raam is terug op die top van die stapel. En so soos jy sien, ons is nou die vernietiging van die lys van regs na links. 

Wat sou gebeur het, al is, as ons dinge gedoen het die verkeerde manier? Net soos wanneer ons probeer om 'n element te voeg. As ons deurmekaar die ketting, as ons het nie die wysers koppel in die korrekte volgorde, as ons net die eerste element bevry, as ons net bevry die hoof van die lys, nou is ons het geen manier om te verwys na die res van die lys. En so sal ons moet gelaat alles, ons sou gehad het, wat is bekend as 'n geheue lek. As jy onthou van ons video op dinamiese geheuetoekenning, dit is nie 'n baie goeie ding. 

So as ek gesê het, is daar is verskeie operasies wat ons nodig het om te gebruik om te werk met geskakelde lys effektief. En jy dalk opgemerk het ek uitgelaat een verwydering van 'n enkele element van 'n gekoppelde lys. Die rede waarom ek dit gedoen het is dit eintlik soort moeilik om te dink oor hoe om te verwyder 'n enkele element van 'n enkel geskakelde lys. Ons moet in staat wees om oor te slaan iets in die lys, wat beteken ons kry 'n point-- ons wil hierdie node-- verwyder maar om dit so te maak ons nie enige inligting nie verloor nie, ons nodig het om hierdie verbinding node oor hier, hier. 

So ek het waarskynlik wat verkeerd uit 'n visuele perspektief. So ons is aan die begin van ons lys, ons vorder deur middel van, Ons wil hierdie node verwyder. As ons net dit verwyder, ons het die ketting gebreek. Dit node hier verwys na alles, dit bevat die ketting van hier op uit. 

So, wat ons nodig het om werklik te doen nadat ons kry om hierdie punt, is wat ons nodig het om terug te stap een, en koppel hierdie node oor hierdie knoop, sodat ons kan dan verwyder die een in die middel. Maar enkel geskakelde lyste te doen nie bied ons 'n manier om terug te gaan. So moet ons óf hou twee wysers, en hulle beweeg soort van af stap, een agter die ander soos ons gaan, of kry 'n punt en dan stuur 'n ander wyser deur. En soos jy kan sien, is dit kan 'n bietjie slordig te kry. Gelukkig het ons 'n ander manier om op te los nie, wanneer ons praat oor dubbeld geskakelde lyste. 

Ek is Doug Lloyd, dit is CS50.