[Muziek] 

DOUG LLOYD: OK, dus bij dit punt in de loop, we hebben veel van de basisprincipes van C. gedekt We weten veel over variabelen, arrays, pointers, dat alles goed spul. Die zijn allemaal een soort van ingebouwde in te zien als de fundamenten, maar we kunnen meer recht doen? We kunnen dingen combineren samen in interessante manieren. 

En zo laten we dat doen, laten we beginnen vertakken van wat C geeft ons, en start van onze eigen gegevens creëren structuren met behulp van deze gebouw blokken samen om iets te doen echt waardevol, nuttig. Een manier kunnen we dit te doen is om te praten over collecties. Tot nu toe hebben we een soort van data had structuur voor het weergeven verzamelingen houd van waarden, dezelfde waarden. Dat zou een array zijn. We hebben collecties van gehele getallen, of verzamelingen van figuren enzovoort. 

Structuren zijn ook een soort van data structuur voor het verzamelen van informatie, maar het is niet voor het verzamelen van dergelijke waarden. Het combineert meestal verschillende datatypes samen in één enkele box. Maar het is niet zelf gebruikt chain elkaar of met elkaar te verbinden soortgelijke items, zoals een array. Arrays zijn zeer geschikt voor element opzoeken, maar recall dat het zeer moeilijk te voegen in een array, tenzij we het invoegen op het einde van de matrix. 

En het beste voorbeeld dat ik heb want dat is het inbrengen soort. Als u onze video herinneren op insertion sort, Er was veel kosten die betrokken zijn in het hebben van te halen elementen, en verschuiven ze uit de weg om iets te passen in het midden van de array. Arrays ook last van andere probleem, dat is inflexibiliteit. Toen we verklaren een array, we krijgen een schot op het. We krijgen om te zeggen, ik wil zoveel elementen. Misschien 100, het misschien zijn 1000, het misschien worden x waarbij x een getal die de gebruiker gaf ons op een prompt of op bevel lijn. 

Maar we krijgen maar één kans op het, we niet krijgen dan zeggen oh, eigenlijk heb ik nodig 101, of ik x plus 20 nodig. Te laat, hebben we al uitgeroepen tot het array, en als we willen krijgen 101 of x plus 20, we moeten verklaren Een geheel andere array, kopieer alle elementen van de array over, en dan hebben we genoeg. En wat als we het weer mis, wat als we eigenlijk nodig hebben 102 of x plus 40, We moeten dit opnieuw doen. Dus ze zijn zeer inflexibel voor het wijzigen van onze gegevens, maar als we samen een aantal combineren van de basis die we hebben al geleerd over pointers en structuren, in het bijzonder het gebruik van dynamisch geheugen toewijzing met malloc, we kunnen deze stukken samen te stellen een nieuwe data structure-- een aanmaken enkelvoudig gelinkte lijst kunnen we say-- die ons in staat stelt om te groeien en krimpen een verzameling van waarden en we zullen geen verspilde ruimte. 

Dus nogmaals, dit idee noemen we, dit begrip, een gekoppelde lijst. In het bijzonder in deze video zijn we over enkelvoudig gelinkte lijst, en dan nog een video we praten ongeveer dubbel gelinkte lijsten, die is gewoon een variatie op een thema hier. Maar een enkelvoudig gelinkte lijst bestaat uit knooppunten knooppunten alleen maar een abstracte term-- het is gewoon iets wat ik bel dat is een soort structuur, in feite, ik ben? Gewoon om het een node-- en dit noemen knooppunt twee leden of twee velden. Het heeft data, meestal een integer, een karakter vlotter, of kunnen een ander type data worden die u hebt gedefinieerd met een soort def. En een verwijzing naar bevat andere knoop van hetzelfde type. 

Dus hebben we twee dingen binnenkant van Dit knooppunt data en een pointer een ander knooppunt. En als je begint te visualiseren dit, kunt u erover nadenkt als een keten van knooppunten die elkaar verbonden. We hebben het eerste knooppunt, is het bevat data, en een wijzer met het tweede knooppunt, dat geheel data, en een verwijzing naar het derde knooppunt. En dus dat is waarom we noemen het een gelinkte lijst, zijn ze met elkaar verbonden. 

Wat doet deze bijzondere knooppunt structuur eruit? Nou, als je te herinneren van onze video-on- definiëren van aangepaste soorten, met type def, kunnen we een structure-- definiëren en typt definiëren een structuur als deze. tyepdef struct sllist, en dan ben ik gebruik hier het woord in waarde willekeurig voor elk type data echt aan te geven. Je zou kunnen doorgeven aan een integer of float, je zou kunnen hebben wat je wilt. Het is niet beperkt tot alleen integers, of iets dergelijks. Dus de waarde is gewoon een willekeurige data type, en vervolgens een pointer een ander knooppunt van hetzelfde type. 

Nu, er is een kleine vangst Hier definiëren met een structuur als het een self referentiële structuur. Ik heb een tijdelijke hebben naam voor mijn structuur. Aan het eind van de dag I duidelijk wilt noemen sll knooppunt, dat is uiteindelijk de nieuwe noem een ​​deel van mijn type definitie maar ik kan sll knooppunt gebruiken in het midden van dit. De reden hiervoor is, dat heb ik niet creëerde een soort genaamd SLL knooppunt totdat ik raakte dit laatste punt hier. Tot dat moment, ik heb een andere manier om te verwijzen naar dit soort gegevens. 

En dit is een self referentiële data type. Het; s een data type van een structuur die data bevat, en een pointer naar een andere structuur van hetzelfde type. Dus ik moet in staat zijn om te verwijzen naar dit gegevenstype althans tijdelijk dus het geven van een tijdelijke naam van struct sllist kan ik dan zeggen dat ik wil een pointer naar een andere structuur sllist, een structuur sllist ster, en dan nadat ik de definitie hebt voltooid, Ik kan nu noemen dit type een SLL-knooppunt. 

Dus dat is waarom zie je er een tijdelijke naam hier, maar een permanente naam hier. Soms heb je zou kunnen zien definities structuur, bijvoorbeeld, die niet self referential, dat niet een specificatie naam niet hier hebben. Het zou gewoon zeggen typedef struct, Open accolade en definieer het dan. Maar als je structuur is zelf referentiële, als deze is, je nodig hebt om een ​​te specificeren tijdelijke typenaam. Maar uiteindelijk, nu dat we dit hebben gedaan, kunnen we alleen maar verwijzen naar deze knooppunten, deze eenheden, als sll knooppunten voor doeleinden van de rest van deze video. 

Oké, dus we weten hoe maak een gelinkte lijst knooppunt. We weten hoe te definiëren een gelinkte lijst knooppunt. Nu, als we gaan om te beginnen ze te gebruiken om informatie te verzamelen, Er zijn een paar van de activiteiten die we moeten begrijpen en te werken met. We moeten weten hoe te creëren een gekoppelde lijst uit de lucht. Als er geen lijst met al, we willen beginnen. Dus moeten we in staat zijn naar een gekoppelde lijst te maken, moeten we waarschijnlijk zoeken via de link lijst een element dat we te vinden. We moeten in staat zijn om in te voegen nieuwe dingen in de lijst, we willen dat onze lijst om te kunnen groeien. En zo ook, we willen kunnen om dingen uit onze lijst schrappen, we willen onze lijst om te kunnen krimpen. En aan het einde van onze programma's, in het bijzonder Als u zich herinneren dat we dynamisch toewijzen van geheugen deze lijsten meestal te bouwen, we willen allemaal dat het geheugen vrij te maken als we klaar ermee werken. En dus moeten we in staat zijn om een ​​te verwijderen gehele gekoppelde lijst in één klap niet. Dus laten we gaan door een aantal van deze operaties en hoe we ze kunnen visualiseren, praten in pseudo-code in het bijzonder. Dus we willen een maken gelinkte lijst, dus misschien we een functie wilt definiëren dit prototype. sll knooppunt ster, creëren, en ik ben het passeren in één argument, wat willekeurige data typt weer van enkele willekeurige data type. Maar ik ben returning-- deze functie moet terug naar mij een pointer, een afzonderlijk gelinkte lijst knooppunt. Nogmaals, we proberen te creëren een gekoppelde lijst uit de lucht, dus ik moet een pointer naar die lijst als ik klaar ben. 

Dus wat zijn de stappen die hier bij betrokken? Nou, het eerste wat ik ben gaan doen is dynamisch toewijzen ruimte voor een nieuw knooppunt. Nogmaals, we maken het uit dunne lucht, dus we moeten malloc ruimte voor. En natuurlijk, onmiddellijk nadat we malloc, checken we altijd om ervoor te zorgen dat onze pointer-- we niet terug null. Want als we proberen en eerbied een null pointer, we gaan een last segfault en we niet willen dat. 

Dan willen we in het veld in te vullen, willen we het veld waarde initialiseren initialiseren en het volgende veld. En dan willen we to-- uiteindelijk als functie prototype indicates-- we willen een pointer keren naar een SLL knooppunt. Dus wat maakt dit eruit als visueel? Nou, ten eerste gaan we dynamisch toewijzen ruimte voor een nieuwe SLL knooppunt dus we malloc-- dat is een visuele representatie van het knooppunt we zojuist hebt gemaakt. En we controleren om ervoor te zorgen het is niet null-- in casu het beeld niet zou hebben opdagen als het null, we uit het geheugen zou hebben gelopen, dus we zijn goed om daar heen te gaan. Dus nu zijn we op stap C, initialiseren het veld knooppunten waarde. Nou ja, op basis van deze functie noem ik hier gebruik, lijkt erop dat ik wil overgaan in 6, Dus ik zal 6 in het veld waarde. Nu, initialiseren het volgende veld. Nou, wat ga ik daar doen, er is niets naast, rechts, Dit is het enige wat in de lijst. Dus wat is het volgende dat in de lijst? 

Het moet niet wijzen op iets, rechts. Er is niets anders is er, dus wat is het concept die we kennen dat is nothing-- pointers niets? Het moet misschien willen we een null pointer daar te zetten, en ik zal de nul vertegenwoordigen pointer als gewoon een rode doos, we kunnen elke niet verder gaan. Zoals we zullen zien wat later, we zullen uiteindelijk ketens pijlen verbinden deze knooppunten samen, maar als je op de rode doos, dat is null, we kunnen elke niet verder gaan, dit is het einde van de lijst. 

En tot slot, we willen gewoon retourneren een pointer naar dit knooppunt. Dus we noemen het nieuwe, en zal nieuwe terugkeren zodat het kan worden gebruikt welke functie geschapen. Dus daar gaan we, hebben we een afzonderlijk geschapen gelinkte lijst knooppunt uit de lucht, en nu hebben we een lijst die we kunnen werken. 

Nu, laten we zeggen dat we al hebben een grote keten, en we willen iets in vinden. En we willen een functie die gaat true of false retourneren, afhankelijk Op de vraag of een waarde bestaat in die lijst. Een functie-prototype, of verklaring voor die functie, eruit zou kunnen zien dit-- Bool te vinden, en dan willen we nu in twee argumenten. 

De eerste is een verwijzing naar het eerste element van de gekoppelde lijst. Dit is eigenlijk iets wat je zult willen altijd bij te houden, en eigenlijk zou iets dat je zelfs in een globale variabele. Zodra u een lijst te maken, je altijd, altijd willen houden van de zeer eerste element van de lijst. Op die manier kunt u verwijzen naar alle andere elementen door gewoon naar aanleiding van de keten, zonder aanwijzingen te houden intact elk element. U hoeft alleen voor het bijhouden van de eerste te houden één als ze allemaal bij elkaar vastgeketend. 

En dan de tweede ding we weer passeren in arbitrair some-- ongeacht het type gegevens we zoekt er binnenin Hopelijk een van de knooppunten in de lijst. Dus wat zijn de stappen? Nou, het eerste wat we doen is creëren we een transversaal wijzer wijzend naar de lijsten hoofd. Nou, waarom doen we dat doen we al een pointer op de lijsten kop, waarom doen we niet bewegen alleen dat niemand in de buurt? Nou, zoals ik net zei, het is echt belangrijk voor ons altijd bijhouden van de eerste element van de lijst. En dus is het eigenlijk beter een duplicaat van dat creëren en gebruik dat om rond zodat we nooit bewegen per ongeluk af te stappen, of we altijd een wijzer op een bepaald punt dat is recht op het eerste element van de lijst. Dus het is beter om een ​​te creëren tweede dat we om te bewegen. 

Toen we net vergelijken of het veld waarde op dat knooppunt is wat we zoeken, en als het niet, we gaan naar het volgende knooppunt. En we blijven dat doen over, en dan, en dan, totdat we ofwel vinden het element, of we slaan null-- we het einde bereikt van de lijst en het is er niet. Dit moet hopelijk een belletje rinkelen om u als gewoon lineair zoeken, we gewoon herhalen in een enkelvoudig gelinkte lijst structuur in plaats van een array te doen. 

Dus hier is een voorbeeld van een enkelvoudig gelinkte lijst. Deze bestaat uit vijf knooppunten, en we hebben een verwijzing naar het hoofd van de lijst, die lijst wordt genoemd. Het eerste wat we willen doen is nogmaals, maak dat traversal pointer. Dus we hebben nu twee pointers dat punt aan het zelfde ding. 

Nu, let hier ook, ik deed het niet moet iedere ruimte voor trav malloc. Ik heb niet gezegd trav gelijk aan malloc iets, dat knooppunt al bestaat, die ruimte in het geheugen bestaat. Dus alles wat ik eigenlijk aan het doen is het creëren van een pointer naar het. Ik ben niet mallocing een extra ruimte, maar hebben nu twee pointers die aan hetzelfde. 

Dus is 2 wat ik zoek? Nou, nee, dus in plaats ik ben ga naar de volgende. Dus eigenlijk zou ik zeggen, trav gelijk trav volgende. 3 is wat ik ben op zoek naar, nee. Dus ik blijven gaan door en tot uiteindelijk naar 6 dat is wat ik zoek voor op basis van de functie-oproep Ik heb aan de top daar, en dus ik ben klaar. 

Nu, wat als het element ik ben naar niet in de lijst, is het nog steeds gaat werken? Nou, merken dat de lijst hier is subtiel anders, en dit is een ander ding dat is belangrijk met gelinkte lijsten, je niet hoeft te behouden ze in een bepaalde volgorde. Je kunt als je wilt, maar je misschien al hebt gemerkt dat we niet bijhouden welk nummer element we op. 

En dat is een soort van een handel die we hebben met gekoppelde lijst verzen arrays, het is hebben we niet random access meer. We kunnen niet zomaar zeggen: ik wil naar de 0-element, of 6 element van mijn array, die ik kan doen in een array. Ik kan niet zeggen dat ik wil naar de 0 element, of de 6-element, of de 25ste element van mijn gekoppelde lijst, er is geen index in verband met hen. En dus is het niet echt van belang als we onze lijst te bewaren in orde. Als u wilt u kan zeker, maar er is geen reden waarom ze nodig hebben om worden bewaard in elke volgorde. Dus nogmaals, laten we proberen en vind 6 in deze lijst. Nou, we beginnen bij de beginnen, doen we niet vinden 6, en dan blijven we niet vinden 6, tot we uiteindelijk hier. Dus nu trav punten aan het knooppunt met 8, en zes is er niet in. 

Dus de volgende stap zou zijn naar de volgende pointer, dus zeggen trav gelijk trav volgende. Nou, trav volgende, aangegeven door de rode doos er is nul. Dus er is nergens anders gaan, en dus op dit punt kunnen we concluderen dat we hebben bereikt het einde van de gekoppelde lijst, en 6 is er niet in. En het zou worden teruggegeven false in dit geval. 

OK, hoe kunnen we plaats een nieuwe knooppunt in de gelinkte lijst? Daarom hebben we in staat om te creëren geweest een gekoppelde lijst uit het niets, maar we willen waarschijnlijk bouwen van een keten en niet het creëren van een heleboel verschillende lijsten. We willen een lijst die heeft een heleboel knooppunten in het, niet een bos van lijsten met een enkel knooppunt. Dus we kunnen niet gewoon blijven met de Create functie die we eerder gedefinieerd, nu zijn we wilt invoegen in een lijst die al bestaat. 

Dus dit geval, we gaan geschiedde in twee argumenten, de aanwijzer naar het hoofd van die gelinkte lijst die we willen toevoegen. Nogmaals, dat is waarom het zo belangrijk dat we altijd bijhouden, want het is de enige manier waarop we echt hebben betrekking op de gehele lijst is alleen door een pointer naar het eerste element. Dus we willen passeren in een pointer om die eerste element, en welke waarde we wilt toevoegen aan de lijst. En uiteindelijk deze functie gaat een pointer terug tot het nieuwe hoofd van een gekoppelde lijst. 

Wat zijn de stappen die hier bij betrokken? Nou, net als bij te creëren, we moeten dynamisch toewijzen ruimte voor een nieuw knooppunt en controleer zeker dat we niet uit het geheugen lopen, opnieuw, omdat we met behulp van malloc. Dan willen we bevolken en steek het knooppunt, dus zet het nummer, ongeacht val is, naar het knooppunt. We willen het knooppunt invoegen op het begin van de gekoppelde lijst. 

Er is een reden dat ik dit wilt doen, en het de moeite waard een tweede zou kunnen zijn de video hier pauzeren en na te denken over de reden waarom ik zou willen invoegen aan het begin van een gekoppelde lijst. Nogmaals, ik eerder noemde dat het niet echt uit of we te behouden in een bestelling, dus misschien is dat een aanwijzing. En je zag wat er zou gebeuren als we wilde to-- of van slechts een seconde geleden, toen we gingen door middel van je zoekopdracht wat kon zien zou er gebeuren als we probeerden te voegen aan het einde van de lijst. Omdat we niet een hebben wijzer naar het einde van de lijst. 

Dus de reden dat ik zou willen te voegen aan het begin, is omdat ik het onmiddellijk kan doen. Ik heb een pointer aan het begin en we zullen zien in een visuele in een tweede. Maar als ik wil voegen aan het eind, Ik moet beginnen bij het begin, doorkruisen de hele weg naar de end, en overstag vervolgens op. Dus dat zou betekenen dat inbrengen aan het einde van de lijst zou een o n geworden operatie, terug te gaan naar onze bespreking van computationele complexiteit. Het zou een o n operatie, waarbij geworden als de lijst werd groter en groter, en groter, zal het meer geworden en moeilijker om iets tack op eind. Maar het is altijd heel makkelijk om overstag iets op aan het begin, je bent altijd aan het begin. 

En we zullen zien weer een visuele van deze. En toen we eenmaal klaar bent, zodra we hebben het nieuwe knooppunt geplaatst, we willen onze pointer terug te keren naar het nieuwe hoofd van een gelinkte lijst, die aangezien we het invoegen op de begin zal eigenlijk een verwijzing naar het knooppunt we zojuist hebt gemaakt. Laten we dit visualiseren, omdat ik denk dat het zal helpen. 

Dus hier is onze lijst, het bestaat uit vier elementen, een knooppunt met 15, die wijst op een knooppunt met 9, waarbij verwijst naar een knooppunt met 13, die wijst op een knooppunt met 10, waarbij de nulhypothese heeft pointer als zijn volgende pointer dat is het einde van de lijst. Dus we willen een voegen nieuw knooppunt met de waarde 12 aan het begin van deze lijst, wat doen we? Nou, ten eerste malloc we ruimte voor de knooppunt, en dan zetten we 12 in. 

Dus nu hebben we bereikt een beslispunt, toch? We hebben een paar aanwijzingen dat we konden bewegen, welke moeten we eerst verhuizen? Moeten we maken 12 punt het nieuwe hoofd van de list-- of neem me niet kwalijk, moeten we 12 wijzen op de oude kop van de lijst? Of moeten we zeggen dat de lijst begint nu op 12. Er is een onderscheid daar, en we zullen kijken wat er gebeurt met zowel een seconde. 

Maar dit leidt tot een groot onderwerp voor zijbalk, namelijk dat een van de lastigste dingen met gekoppelde lijsten wordt naar de pointers te regelen in de juiste volgorde. Als je dingen verplaatst buiten de orde, kunt u per ongeluk belanden orphaning de rest van de lijst. En hier is een voorbeeld van. Dus laten we gaan met het idee van-- goed, we hebben zojuist 12. We weten dat 12 gaat worden het nieuwe hoofd van de lijst, en dus waarom niet we gewoon bewegen de lijst pointer om daar te wijzen. 

OK, dus dat is goed. Dus nu waar komt 12 volgende punt? Ik bedoel, visueel kunnen we zien dat zal verwijzen naar 15, als mensen het is echt ons duidelijk. Hoe werkt de computer weet? We hebben niets wijzend naar 15 meer, toch? 

We hebben elke mogelijkheid om te verwijzen naar 15 verloren. We kunnen geen nieuwe pijl naast gelijken zeggen iets, er is niets daar. In feite hebben we verweesd de rest van de lijst door dit te doen, we hebben per ongeluk gebroken ketting. En we willen zeker niet om dat te doen. 

Dus laten we teruggaan en probeer dit opnieuw. Misschien is het juiste ding om te doen is tot en met 12 van de volgende pointer ingesteld de oude kop van de eerste lijst, dan kunnen we de lijst bewegen over. En in feite, dat is de juiste volgorde dat wij moet volgen wanneer we werken met enkelvoudig gelinkte lijst. Wij willen altijd het sluiten nieuw element in de lijst, voordat we dat soort nemen belangrijke stap van het veranderen wanneer het hoofd van de gekoppelde lijst. Nogmaals, dat is zo'n fundamentele ding, we willen niet te houden van het te verliezen. 

Dus we willen ervoor zorgen dat alles wordt aan elkaar geketend, voordat we verder dat pointer. En dus zou dit de juiste volgorde te zijn, die verbinding 12 op de lijst, dan zeggen dat de lijst begint een 12. Als we zei dat de lijst begint bij 12 en Vervolgens probeerde te verbinden 12 van de lijst, We hebben al gezien wat er gebeurt. We verliezen de lijst per vergissing. 

OK, dus nog een ding om over te praten. Wat als we willen om zich te ontdoen van een hele tegelijk gelinkte lijst? Nogmaals, we mallocing al deze ruimte, en dus hebben we nodig om het te bevrijden als we klaar zijn. Dus nu willen we verwijderen de gehele gelinkte lijst. Nou, wat willen we doen? 

Als we de null pointer hebt bereikt, we willen stoppen, anders gewoon verwijderen de rest van de lijst en vervolgens bevrijd mij. Verwijdert u de rest van de lijst, en bevrijd dan het huidige knooppunt. Wat klinkt dat, welke techniek hebben we gesproken over eerder klinkt dat? Delete iedereen, dan terug te komen en me te verwijderen. 

Dat is recursie, hebben we de probleem een ​​beetje kleiner, we zeggen schrappen iedereen anders, dan kunt u mij verwijderen. En verder op de weg, dat knooppunt zal zeggen, iedereen verwijderen. Maar uiteindelijk zullen we naar het krijgen punt waar de lijst is nul, en dat is ons basisscenario. 

Dus laten we een kijkje nemen op deze, en hoe dit zou kunnen werken. Dus hier is onze lijst, het is hetzelfde geven we hadden het net over, en er is de stappen. Er is veel tekst hier, maar hopelijk de visualisatie zal helpen. 

Dus we have-- en ik heb ook trok onze stack frames illustratie van onze video-on-call stacks, en hopelijk alles samen zullen je laten zien wat er gaande is. Dus hier is onze pseudo-code. Als we een nul bereiken wijzer, stoppen, anders Verwijder de rest van de lijst, vrij dan het huidige knooppunt. Dus nu, list-- de aanwijzer dat we passeren in de punten 12 vernietigen. 12 is niet een null pointer, dus we zijn naar de rest van de lijst. 

Wat is het verwijderen van de rest van ons betrokken zijn? Nou, het betekent dat het maken van een bellen om te vernietigen, zeggende 15 is dat het begin van de rest van de lijst die we willen vernietigen. En zo de oproep om te vernietigen 12 is een soort van in de wacht. Het is er bevroren, in afwachting van de bellen om te vernietigen 15, om zijn werk af te maken. 

Nou, 15 is niet een null pointer en dus het gaat om te zeggen, oke, goed, verwijdert u de rest van de lijst. De rest van de lijst begint 9, en dus zullen we net wachten tot je alles verwijderen dat spul, kom dan terug en me te verwijderen. Nou 9 gaat zeggen, goed, Ik ben niet een null pointer, dus verwijder de rest van de lijst van hier. En dus proberen en te vernietigen 13. 13 zegt, ik ben niet null pointer, hetzelfde, het passeren van de bok. 10 is niet null pointer, 10 bevat een null pointer, 10 maar zelf geen null nu wijzer, en zo gaat de bok ook. 

En nu een lijst van punten daar, het echt zou wijzen op some-- als ik meer ruimte in het beeld, het zou wijzen op een aantal willekeurige ruimte dat we niet weten wat het is. Het is de null pointer hoewel, de lijst is letterlijk nu ingesteld is het waarden null. Het is naar rechts in die rode doos. We bereikten een null pointer, dus we kunnen stoppen, en we zijn klaar. 

En zodat paars frame now-- op top van stack-- dat is het actieve frame, maar het heeft gedaan. Als we een null pointer hebt bereikt, stop. We doen niets, we kan er niet een null pointer, we hadden geen malloc ruimte, en dus zijn we klaar. Zodat de functie kader wordt vernietigd, en we resume-- we halen waar we gebleven af met de volgende hoogste een, die Dit is donkerblauw lijst hier. Dus halen we precies waar we gebleven waren. We verwijderde de rest van de lijst al, dus nu zijn we naar de huidige nodes bevrijden. Dus nu kunnen we vrij dit knooppunt, en nu we hebben het einde van de functie bereikt. En zodat functie frame vernietigd en we ophalen op de licht blauwe. 

Dus het says-- Ik heb al done-- verwijderen van de rest van de lijst, zodat vrij het huidige knooppunt. En nu de gele frame weer bovenop de stapel. En zo zie je, we zijn nu vernietigen van de lijst van rechts naar links. 

Wat zou er gebeurd zijn, maar, als we dingen hadden gedaan de verkeerde manier? Net als toen we probeerden een element toe te voegen. Als we messed up van de keten, indien we niet de pointers verbinden in de juiste volgorde, als we alleen het eerste element bevrijd, als we net bevrijd van de hoofd van de lijst, nu zijn we hebben geen manier om te verwijzen naar de rest van de lijst. En dus zouden we wees alles, we zouden hebben gehad wat is riep een geheugenlek. Misschien herinner je je van onze video op dynamisch geheugen toewijzing, dat is niet erg goede zaak. 

Dus zoals ik al zei, is er zijn verschillende bewerkingen dat we gebruiken werken met gekoppelde lijst effectief. En u misschien opgevallen ik weggelaten één, verwijderen van een enkel element van een gekoppelde lijst. De reden dat ik dat deed is het is eigenlijk soort lastig om na te denken over hoe om te verwijderen een enkel element van een enkelvoudig gelinkte lijst. We moeten in staat zijn om over te slaan iets in de lijst, die middelen krijgen we een point-- we wil dit node-- verwijderen maar om het zo te maken dat we geen informatie niet te verliezen, we nodig hebben om dit aan te sluiten knooppunt dan hier, hier. 

Dus ik waarschijnlijk wel wat mis visueel perspectief. Dus we zijn aan het begin van onze lijst, zijn we te gaan door middel van, we willen dit knooppunt te verwijderen. Als we gewoon verwijderen, we hebben de keten verbroken. Dit knooppunt hier verwijst naar al het andere, het bevat de keten van hier op uit. 

Dus wat moeten we eigenlijk doen nadat we op dit punt, is dat we nodig hebben om een ​​stap terug, en sluit dit knooppunt naar dit knooppunt, dus we kunnen dan verwijderen de een in het midden. Maar afzonderlijk gelinkte lijsten niet bieden ons een manier om achteruit te gaan. Dus moeten we ofwel blijven twee pointers, en verplaats soort van off stap achter andere als we gaan, of naar een punt en stuur vervolgens een ander aanwijzer door. En zoals je kunt zien, kan een beetje rommelig. Gelukkig hebben we een andere manier op te lossen dat, als we praten over dubbel gelinkte lijsten. 

Ik ben Doug Lloyd, dit is CS50.