[Musiikkia] 

DOUG Lloyd: OK, joten on tässä vaiheessa tietenkin Selvitimme jo paljon perusasiat C. Tiedämme paljon muuttujia, taulukot, osoittimet, kaikki hyvät jutut. Ne ovat kaikki tavallaan rakennettu vuonna nähdä niin perustekijät, mutta voimme tehdä enemmän, eikö? Voimme yhdistää asioita yhdessä kiinnostavalla tavalla. 

Ja niin tehdään se, aloitetaan sektoreita, mitä C antaa meille, ja alkaa luoda omia tietoja rakenteet näiden rakennus lohkot yhdessä tehdä jotain todella arvokas, hyödyllinen. Yksi tapa tehdä tämä on puhua kokoelmista. Joten toistaiseksi meillä on ollut yksi millaisia ​​tietoja rakenne edustaa kokoelmia samankaltaisten arvot, samat arvot. Se olisi jono. Meillä on kokoelmia kokonaislukuja, tai kokoelmat merkkiä ja niin edelleen. 

Rakenteet ovat myös eräänlainen tietojen rakenne tietojen keräämiseksi, mutta se ei ole keräämiseksi kuten arvoja. Se yleensä sekoittaa erilaiset tiedot yhdessä sisällä yhden laatikon. Mutta se ei ole itse käytetään ketjun yhdessä tai liittää yhteen samankaltaisia kohteita, kuten array. Taulukot ovat hyvin elementti etsiä, mutta muistuttaa että se on hyvin vaikeaa lisättävän array, ellei olemme lisäämällä at aivan lopussa, että jono. 

Ja paras esimerkki minulla on että on lisäyslajittelun. Jos muistatte meidän video sijoittamista lajitella, siellä oli paljon kustannuksella mukana ottaa poimia elementtejä, ja siirtää niitä pois tieltä sopivaksi jotain keskelle teidän array. Paneelit kärsivät myös toinen ongelma, joka on joustamattomuus. Kun me julistamme array, saamme yhden ampui sitä. Saamme sanoa, haluan Tämän monia elementtejä. Voi olla 100, se voisi olla 1000, se saattaa olla X, jossa x on numero, että käyttäjä antoi meille nopeasti tai komento linja. 

Mutta me vain saada yksi laukaus sitä, me älä päästä sitten sanoa oh, itse asiassa tarvitaan 101, tai tarvitsin x + 20. Liian myöhäistä, olemme jo ilmoittanut array, ja jos haluamme saada 101 tai X plus 20, meidän täytyy julistaa täysin eri array, kopioi kaikki taulukon alkiot yli, ja sitten meillä on riittävästi. Ja entä jos olemme väärässä jälleen, mitä jos me todella tarvitsemme 102, tai X + 40, meidän täytyy tehdä tätä uudelleen. Joten he ovat hyvin joustamaton koon muuttamisen tietomme, mutta jos yhdistämme yhteen joitakin perusasiat, että olemme jo oppinut viitteitä ja rakenteita, erityisesti käyttäen dynaaminen muisti jakamista malloc, me voi laittaa nämä palaset yhteen luoda uutta tietoa structure-- yksittäin linkitetty lista voisimme say-- jonka avulla voimme kasvaa ja kutistua kokoelma arvojen ja meillä ei ole mitään hukkaan tilaa. 

Joten jälleen, me kutsumme tätä ajatusta, käsitystä, linkitetty lista. Erityisesti tämän videon olemme puhumme yksittäin linkitetty lista, ja sitten toinen video jutellaan noin kaksinkertaisesti liittyvät luettelot, joka on vain muunnelma teemasta täällä. Mutta yksittäin linkitetty lista koostuu solmut, solmut vain on abstrakti term-- se on vain jotain Soitan se eräänlainen rakenne, periaatteessa, olen? Juuri menossa kutsua sitä node-- ja tämä solmulla on kaksi jäsentä, tai kaksi kenttää. Se on tietoja, yleensä kokonaisluku, merkki kellua, tai voisi olla jokin muu tietolaji että olet määritetty tyyppi def. Ja se sisältää osoittimen toisen solmun samaa tyyppiä. 

Joten meillä on kaksi asiaa sisällä tämä solmu, tiedot ja osoitin toiseen solmuun. Ja jos alkaa visualisoida tämän, voit ajatella sitä kuten ketju solmuja, jotka on liitetty yhteen. Meillä on ensimmäinen solmu, se sisältää dataa, ja osoitin toiselle solmulle, joka sisältää datan, ja osoitin kolmanteen solmuun. Ja niin siksi me kutsumme sitä linkitetty lista, ne toisiinsa. 

Mitä tämä erityinen solmu rakenne näyttää? No, jos muistatte meidän video määritellään räätälöidyt tyypit, tyypin def, voimme määritellä structure-- ja Define rakenne näin. tyepdef struct sllist, ja sitten olen käyttämällä sanaa arvo tähän mielivaltaisesti osoittamaan mitään tietotyyppi todella. Voisit siirtää kokonaisluku tai float, sinulla voisi olla mitä haluat. Se ei rajoitu vain kokonaisluvut, tai jotain sellaista. Joten arvo on vain mielivaltainen tietotyyppi, ja sitten osoitin toisen solmun samaa tyyppiä. 

Nyt, siellä on pieni saalis täällä määritellään rakenne kun se on itse viite rakenne. Minun on väliaikainen nimi minun rakennetta. Lopussa päivän I selvästi halua kutsua sitä SLL solmu, joka on viime kädessä uusi nimi osa minun tyyppiä määritelmän, mutta en voi käyttää SLL solmu keskellä tämä. Syynä on, en ole luotu tyyppi nimeltä SLL solmu kunnes osuin tämä viimeinen kohta täällä. Tuohon asti, minun täytyy saada toinen tapa viitata tietojen tyyppi. 

Ja tämä on itsestään viitetietojen tyyppi. Se, s tietotyyppi rakenne, joka sisältää tiedot, ja osoitin toiseen rakenne samaa tyyppiä. Joten minun täytyy pystyä viitata Tämä datatyyppi ainakin väliaikaisesti, joten antaa sille tilapäisen nimi struct sllist sallii minun sitten sanoa haluan osoitin toiseen struct sllist, struct sllist tähti, ja sitten kun olen suorittanut määritelmä, Voin nyt soittaa tämäntyyppisiä SLL solmu. 

Joten siksi näet siellä väliaikainen nimi täällä, mutta pysyvä nimi tähän. Joskus saatat nähdä määritelmät rakenne, esimerkiksi, että eivät ole itse viite, että ei ole määrittelyksi nimi tähän. Se olisi vain sanoa typedef struct, avaa kihara ahdin ja sitten määritellä se. Mutta jos olet struct on itsenäinen viite, koska tämä on, sinun täytyy määrittää väliaikainen tyypin nimi. Mutta lopulta, nyt että olemme tehneet tämän, voimme vain viitata Nämä solmut, nämä yksiköt, kuten SLL solmut tarkoituksiin muusta tämän videon. 

Selvä, joten osaamme luoda linkitetyn listan solmu. Tiedämme miten määritellä linkitetyn listan solmu. Nyt, jos aiomme aloittaa käyttää niitä kerätä tietoa, siellä on pari toiminnassamme täytyy ymmärtää ja työskennellä. Meidän täytyy tietää, miten luoda linkitetty lista tyhjästä. Jos ei ole luettelo jo, haluamme aloittaa yksi. Joten meidän on pystyttävä luoda linkitetty lista, meidän on luultavasti etsiä kautta linkkilista löytää elementti etsimme. Meidän täytyy pystyä lisätä uusia asioita listaan, haluamme luettelo pystyä kasvamaan. Ja samalla haluamme pystyä poistaa asioita listalta, haluamme luettelo pystyä kutistua. Ja lopussa meidän ohjelmat, erityisesti Jos muistatte, että olemme dynaamisesti jaetut muisti rakentaa nämä luettelot tyypillisesti, haluamme vapauttaa kaikki tämä muisti kun olemme tehneet työtä se. Ja niin meidän täytyy pystyä poistamaan koko linkitetty lista yhdellä epäonnistua syöksy. Joten mene läpi jotkut näistä toiminnoista ja kuinka voisimme visualisoida niitä, puhuu pseudokoodilla koodi erityisesti. Joten haluamme luoda linkitetty lista, joten ehkä me haluat määrittää funktion tämän prototyyppi. SLL solmu tähti, luoda, ja olen ohimennen yksi argumentti, jotkut mielivaltaista dataa tyyppi jälleen, joidenkin mielivaltaista tietojen tyyppi. Mutta olen returning-- tämän toiminnon pitäisi palata minulle osoitin, että yksittäin linkitetty lista solmu. Jälleen me yritämme luoda linkitetty lista tyhjästä, joten minun täytyy osoitin että luettelosta, kun olen valmis. 

Mitkä ovat vaiheista täällä? No, ensimmäinen asia olen aikoo tehdä on dynaamisesti jakaa tilaa uusi solmu. Jälleen Luomme se tyhjästä ilma, joten meidän on malloc tilaa se. Ja tietenkin, heti kun olemme malloc, aina varmista, että meidän pointer-- emme saaneet takaisin null. Koska jos yritämme kunnioitus nollaosoittimen, aiomme kärsiä segfault ja emme halua että. 

Sitten haluamme täyttää alalla, haluamme alustaa arvon alalla ja alustaa seuraavaan kenttään. Ja sitten me haluamme to-- lopulta kuin toiminto prototyyppi indicates-- haluamme palata osoitin SLL solmuun. Joten mitä tehdä tämä näyttää visuaalisesti? No, ensimmäinen aiomme dynaamisesti jakaa tilaa uuden SLL solmu, joten malloc-- se visuaalinen esitys solmun me juuri luotu. Ja me varmista se ei ole null-- tässä tapauksessa, kuva ei olisi saapunut jos se oli tyhjä, olisimme loppuu muisti, joten olemme hyvä mennä sinne. Joten nyt olemme vaiheeseen C, alustaa solmut arvo kenttään. No, joka perustuu tämä toiminto soittaa Käytän tässä, näyttää haluan välittää 6, niin minä 6 arvokentässä. Nyt alustaa seuraavaan kenttään. No, mitä aion tehdä siellä, ei ole mitään vieressä, oikealla, tämä on ainoa asia luettelossa. Niin mitä seuraavaksi asia listassa? 

Se pitäisi ei viitannut mihinkään, oikealle. Ei ole mitään muuta siellä, niin mikä on käsite tiedämme se nothing-- viitteitä mitään? Sen pitäisi olla ehkä haluamme laittaa nollaosoittimen siellä, ja minä edustavat null osoittimen juuri punainen laatikko, emme voi mennä pidemmälle. Kuten näemme hieman myöhemmin, saamme lopulta ketjut nuolia yhdistää Nämä solmut yhdessä, mutta kun osut punainen laatikko, joka on null, emme voi mennä pidemmälle, se luettelon loppuun. 

Ja lopuksi, me vain haluamme palata osoitin tähän solmuun. Joten me kutsumme sitä uutta, ja palaa uuden joten sitä voidaan käyttää mitä toimintoa luonut. Joten siellä mennään, Olemme luoneet yksittäin linkitetty lista solmu tyhjästä, ja nyt meillä on lista voimme työskennellä. 

Nyt, sanokaamme meillä jo on suuri ketju, ja haluamme löytää jotain se. Ja haluamme toiminto, joka menee palata tosi tai epätosi riippuen onko arvo on olemassa kyseisessä luettelossa. Toiminto prototyyppi, tai ilmoituksen, että toiminto, voisi näyttää this-- bool löytää, ja sitten haluamme kulkea kaksi perustelua. 

Ensimmäinen, on osoitin ensimmäinen osa linkitetyn listan. Tämä on todella jotain sinun aina haluavat seurata, ja itse asiassa voi olla jotain, joka edes laittaa globaali muuttuja. Kun olet luonut listan, aina, aina haluavat seurata hyvin ensimmäinen osa luettelosta. Näin voit viitata kaikki muut elementit vain seuraava ketjun, ilman pitää viitteitä ehjä jokaiseen elementtiin. Sinun tarvitsee vain seurata ensimmäisen yksi jos he kaikki ketjuttaa. 

Ja sitten toinen asia olemme ohimennen uudelleen on mielivaltaisesti some-- mitä tietotyyppi olemme etsivät siellä on sisällä toivottavasti yksi solmujen luetteloon. Mitä ovat vaiheet? No, ensimmäinen asia mitä teemme on luomme poikittainen osoitin osoittaa luetteloihin päähän. No, miksi me teemme, että olemme jo on osoitin luettelot pään, miksi emme siirrä että yksi noin? No, kuten juuri sanoin, se on todella tärkeää meille aina seurata ensimmäinen elementti luettelosta. Ja niin se on itse asiassa parempi luoda päällekkäisiä kyseisen, ja käyttää sitä liikkua niin emme koskaan vahingossa siirtää pois, tai aina on osoitin jossain vaiheessa, että on aivan ensimmäinen osa luettelosta. Joten on parempi luoda toisessa, että käytämme liikkua. 

Sitten vain vertailla, onko arvo kentän että solmu on mitä etsimme, ja jos se on ei, me vain siirry seuraavaan solmuun. Ja me pitää tehdä, että yli, ja yli, ja yli, kunnes joko löytää elementti, tai me osuma null-- olemme päättynyt luettelon ja se ei ole siellä. Tämä toivottavasti tutulta sinulle vain lineaarinen haku, me vain jäljittelevän sitä yksittäin linkitetyn listan rakenne käyttämisen sijaan array tehdä se. 

Joten tässä on esimerkki yksittäin linkitetyn listan. Tämä yksi koostuu viisi solmua, ja meillä on osoitin johtaja luettelo, jota kutsutaan lista. Ensimmäinen asia, jota haluamme tehdä, on jälleen, luoda että kulkea osoitin. Joten meillä on nyt kaksi osoitinta että kohta sama asia. 

Nyt, huomaa tässä myös, en on malloc mitään tilaa Trav. En sanonut Trav vastaa malloc jotain, joka solmu on jo olemassa, että muistitilaa on jo olemassa. Joten kaikki Olen todella tekee on luomalla uuden osoitin sen. En mallocing lisää tilaa, vain nyt kaksi osoitinta osoittaa sama asia. 

Joten on 2 mitä etsin? No, ei, joten sen sijaan olen aikoo siirtyä seuraavaan. Joten periaatteessa sanoisin, trav vastaa trav seuraava. On 3 mitä etsin, ei. Joten olen edelleen mennä kautta, kunnes lopulta saada 6, joka on mitä etsin sillä perusteella funktiokutsua Minulla on huipulla siellä, ja niin olen valmis. 

Nyt, mitä jos elementti olen etsimässä ei ole luettelossa, Onko se vielä menossa töihin? No, huomaa, että luettelo tässä hieman toisenlainen, ja tämä on toinen asia, joka on tärkeää liittyvät luettelot, sinun ei tarvitse säilyttää niitä missään tietyssä järjestyksessä. Voit, jos haluat, mutta olet ehkä jo huomannut että emme pitää kirjaa mitä numero elementti olemme. 

Ja se on eräänlainen yhden kaupan me on kanssa linkitetty lista säkeet paneelit, se meillä ei ole random access enää. Emme voi vain sanoa, haluan mennä 0. elementti, tai 6. osa minun array, jota voin tehdä array. En voi sanoa haluan mennä 0. elementti, tai 6. elementti, tai 25. osa minun linkitetty lista, ei ole indeksiä niihin liittyviä. Ja niin se ei ole oikeastaan ​​väliä jos säilytämme lista järjestyksessä. Jos haluat sinua varmasti voi, mutta siellä on mitään syytä, miksi ne tarvitsevat säilytettävä missä tahansa järjestyksessä. Joten jälleen, yritetään ja löytää 6 tässä luettelossa. No, me alkavat alkaa, emme löydä 6, ja sitten jatkamme ei löytää 6, kunnes me lopulta päästä tänne. Joten nyt trav pistettä solmuun sisältävät 8, ja kuusi ei ole siellä. 

Niin seuraava askel olisi Siirry seuraavaan osoitin, niin sanoa trav vastaa Trav seuraava. No, trav seuraavaksi, merkitty punainen laatikko siellä, on nolla. Joten ei muuta paikkaa minne mennä, ja niin tässä vaiheessa voimme päätellä, että olemme saavuttaneet loppuun linkitetyn listan, ja 6 ei ole siellä. Ja se olisi palautettava väärä tässä tapauksessa. 

OK, miten voimme lisätä uuden solmun linkitetty lista? Joten olemme pystyneet luomaan linkitetty lista tyhjästä, mutta me luultavasti halua rakentaa ketju eikä luoda joukko erillisiä listoja. Haluamme olla yksi luettelosta on joukko solmuja se, ei nippu luettelot yhden solmun. Joten emme voi vain pitää käyttämällä Luo toiminto määrittelimme aikaisemmin, nyt meillä haluat lisätä osaksi luettelo jo olemassa. 

Joten tässä tapauksessa, menemme kulkea kaksi argumenttia, osoitin johtaja, joka linkitetty lista, että haluamme lisätä. Jälleen siksi se on niin tärkeää, että aina seurata sitä, koska se on ainoa tapa, jolla voimme todella täytyy viitata koko lista on vain osoitin ensimmäinen osa. Joten haluamme kulkea Osoitin, että ensimmäinen elementti, ja arvosta riippumatta me haluavat lisätä luetteloon. Ja lopulta tämä toiminto aikoo palata osoitin jotta uusi johtaja linkitetyn listan. 

Mitä vaiheita mukana täällä? No, aivan kuten luoda, meidän on dynaamisesti varata tilaa uusi solmu, ja tarkista, varma emme lopu muisti, jälleen, koska käytämme malloc. Sitten haluamme asuttaa ja aseta solmu, niin laita numero riippumatta val on, osaksi solmu. Haluamme lisätä solmun alussa linkitetyn listan. 

On syy, että olen halua tehdä tätä, ja se voisi olla hyvä ottaa toinen Keskeytä video tästä, ja miettiä, miksi en haluaisi lisätä alussa linkitetyn lista. Jälleen mainitsin aiemmin että se ei ole oikeastaan merkitystä, me säilyttää sitä millään järjestys, joten ehkä se vihje. Ja näit mitä tapahtuisi, jos me halusi to-- tai vain toinen sitten kun olimme menossa haun kautta voit voisi nähdä, mitä voisi tapahtua, jos yritimme lisätä lopussa luettelosta. Koska meillä ei ole Osoitin listan loppuun. 

Niin siitä syystä, että haluaisin lisätä alussa, on koska voin tehdä sen heti. Minulla osoitin alussa, ja näemme tämän visuaalisen toisessa. Mutta jos haluan lisätä lopussa, Minun täytyy aloittaa alusta, kulkea aina end, ja sitten tack se. Niin se tarkoittaisi että työntämällä lopussa luettelo tulisi o n toiminta, menee takaisin meidän keskustelua laskennallinen monimutkaisuus. Se olisi tullut o n toimintaa, jossa kuten luettelon sai isompi, ja isompi, ja isompi, siitä tulee yhä vaikeampi tack jotain on lopussa. Mutta se on aina todella helppoa tack jotain alussa, olet aina alussa. 

Ja näemme visuaalinen tämän uudelleen. Ja sitten kun olemme tehneet, kun olemme lisätään uusi solmu, haluamme palata meidän osoitin uusi johtaja linkitetty lista, joka koska olemme lisäämällä at alussa, todella on osoitin solmuun me juuri luotu. Katsotaanpa visualisoida, koska mielestäni se auttaa. 

Joten tässä on meidän lista, se koostuu neljä elementtiä, solmu sisältää 15, mikä viittaa solmuun jotka sisältävät 9, joka viittaa solmuun, joka sisältää 13, mikä viittaa solmun sisältävä 10, joka on nolla- osoitin sen ensi osoitin niin se luettelon loppuun. Joten haluamme lisätä uusi solmu kanssa arvo 12 alussa tämän lista, mitä teemme? No, ensin meidän malloc tilaa solmu, ja sitten laitamme 12 siellä. 

Joten nyt olemme saavuttaneet päätös, eikö? Meillä on pari viitteitä, että voisimme liikkua, kumpi meidän pitäisi siirtyä ensin? Pitäisikö meidän tehdä 12 kohta uusi johtaja list-- tai anteeksi, meidän pitäisi tehdä 12 viittaavat vanha pää listan? Vai pitäisikö sanoa, että Listassa on nyt alkaa 12. On ero siellä, ja me tutustumme mitä tapahtuu sekä toisessa. 

Mutta tämä johtaa suuri aihe sivupalkin, joka on, että yksi vaikeimpia asioita liittyvät luettelot on järjestää viitteitä oikeassa järjestyksessä. Jos muutat asioita epäkunnossa, voit päätyä vahingossa orpoutumista loput luettelon. Ja tässä on esimerkki tästä. Joten mennä ajatus of-- No, olemme juuri luotu 12. Tiedämme 12 tulee olemaan uusi johtaja luettelo, ja niin miksi emme siirrä luettelon osoitin kohtaan siellä. 

OK, niin se on hyvä. Joten nyt jos ei 12 seuraava kohta? Tarkoitan, visuaalisesti voimme nähdä että se tulee kohta 15, kuin ihmisillä se on todella selvää meille. Miten tietokone tietää? Meillä ei ole mitään osoittaen 15 enää, eikö? 

Olemme menettäneet kyvyn viitata 15. Emme voi sanoa uusia nuolta tasavertaisten jotain, ei ole mitään siellä. Itse asiassa, olemme orvoiksi loput luettelon tekemällä niin, olemme vahingossa rikki ketju. Ja emme missään nimessä halua tehdä sitä. 

Joten mennään takaisin ja kokeile tätä uudelleen. Ehkä oikein on asettaa 12 seuraava osoitin vanha johtaja listan ensimmäinen, sitten voimme siirtyä listan yli. Ja itse asiassa, että on oikeassa järjestyksessä, että me täytyy seurata, kun olemme työskennellä yksin linkitetyn listan. Haluamme aina yhdistää uusi elementti listaan, ennen kuin ryhdymme tuollaisen tärkeä askel muuttaa jossa pää linkitetyn listan on. Tämäkin on niin perustavanlaatuinen asia, emme halua menettää seurata sitä. 

Joten haluamme varmistaa, että kaikki on ketjuttaa, ennen kuin siirrymme että osoitin. Ja niin tämä olisi oikeassa järjestyksessä, joka on kytkeä 12 listalle sitten sanoa, että luettelo alkaa 12. Jos me sanoi luettelo alkaa 12 ja sitten yrittänyt liittää 12 listalle olemme jo nähneet, mitä tapahtuu. Menetämme lista vahingossa. 

OK, joten yksi asia puhua. Mitä jos haluamme päästä eroon koko linkitetty lista kerralla? Jälleen olemme mallocing kaikki tämä tila, ja niin me täytyy vapauttaa, kun olemme tehneet. Joten nyt haluamme poistaa koko linkitetyn listan. No, mitä haluamme tehdä? 

Jos olemme saavuttaneet nollaosoittimen, me halua lopettaa, muuten vain poistaa loput luettelosta ja sitten vapauta minut. Poistaa loput luettelon, ja sitten vapauttaa nykyisen solmun. Mitä se kuulostaa, mitä tekniikkaa on puhuimme noin aiemmin Kuulostaako? Poista kaikki muutkin, niin palata ja poistaa minut. 

Se rekursio, olemme tehneet ongelma hieman pienempi, sanomme poistaa kaikki muuten, niin voit poistaa minut. Ja edelleen tiellä, että solmu sanovat, poistaa kaikki muutkin. Mutta lopulta me saamme kohdassa, jossa luettelo on tyhjä, ja se on meidän perustapaus. 

Joten katsomaan tämän, ja miten tämä voisi toimia. Joten tässä on meidän lista, se on sama luetella me vain puhumme, ja siellä vaiheet. Siellä on paljon tekstiä täällä, mutta toivottavasti visualisointi auttaa. 

Joten me have-- ja olen myös vetänyt jopa meidän pino kehyksiä kuva meidän video soittaa pinoja, ja toivottavasti kaikki tämän yhdessä näyttää mitä tapahtuu. Joten tässä on meidän pseudokoodilla koodi. Jos pääsemme null osoitin, stop, muuten, poistaa loput luettelon, sitten vapauttaa nykyisen solmun. Joten juuri nyt, list-- osoitin, että olemme kulkee tuhota pistettä 12. 12 ei nollaosoittimen, joten olemme menossa poistaa loput luettelon. 

Mikä on poistaa me muut mukana? No, se tarkoittaa tehtävien soita tuhota, sanoi että 15 on alku Loput luettelon haluamme tuhota. Ja niin puhelu tuhota 12 on eräänlainen pidossa. Se on jäädytetty siellä, odottamassa soita tuhota 15, loppuun työnsä. 

No, 15 ei ole nollaosoittimen, ja joten se tulee sanoa, okei, hyvin, poistaa loput luettelon. Loput luettelo alkaa klo 9, ja niin me vain odota kunnes poistat kaikki että kamaa, sitten tulevat takaisin ja poistaa minut. No 9 tulee sanoa, hyvin, En ole nollaosoittimen, joten poista loput listan täältä. Ja niin kokeile ja tuhota 13. 13 sanoo, en ole nollaosoittimen, sama asia, se kulkee pukki. 10 ei nollaosoittimen, 10 sisältää nollaosoittimen, mutta 10 ei itse nollaosoittimen juuri nyt, ja niin se kulkee pukki liian. 

Ja nyt luetella pistettä siellä, se todella osoittaisi some-- jos minulla olisi enemmän tilaa kuva, se osoittaa joitakin satunnaisia ​​tilaa että emme tiedä mitä se on. Se on tyhjän osoittimen kuitenkin, luettelo on kirjaimellisesti nyt asetettu se arvoja null. Se osoittaa oikealle sisällä että punainen laatikko. Pääsimme nollaosoittimen, joten voimme lopettaa, ja olemme tehneet. 

Ja jotta violetti kehys on now-- klo päälle stack-- se aktiivinen kehys, mutta se on tehty. Jos olemme saavuttaneet nollaosoittimen, lopeta. Emme tee mitään, me ei saa nollaosoittimen, emme malloc mitään tilaa, ja niin olemme tehneet. Jotta toiminto kehys tuhotaan, ja me resume-- haemme jossa jätimme pois seuraavaksi korkein, joka on tämä tummansininen runko täällä. Joten me poimia oikea mihin jäimme. Poistimme loput luettelo jo, joten nyt olemme menossa vapauttaa nykyisen solmut. Joten nyt voimme vapauttaa tämän solmun, ja nyt olemme lopussa funktion. Ja niin että toiminta kehys on tuhottu, ja me poimia vaaleansininen yksi. 

Joten se says-- olen jo done-- poistetaan loput listan, niin vapauttaa nykyisen solmun. Ja nyt keltainen kehys on takaisin pinon. Ja niin näette, olemme nyt tuhoaa listan oikealta vasemmalle. 

Mitä olisi tapahtunut, vaikka, jos olisimme tehneet asiat väärin? Aivan kuten kun yritimme lisätä elementin. Jos me sekaisin ketju, jos emme yhdistä viitteitä oikeassa järjestyksessä, jos me vain vapautti ensimmäinen elementti, jos me vain vapautti johtaja luettelon, nyt meillä ei ole tapa viitata loput luettelon. Ja niin meillä olisi orvoksi kaiken, meillä olisi ollut mitä kutsutaan muisti vuotaa. Jos muistatte meidän video dynaaminen muistin jakamista, se ei ole kovin hyvä asia. 

Joten kuten sanoin, siellä useita toimintoja että meidän on käytettävä töihin kanssa linkitetty lista tehokkaasti. Ja olet ehkä huomannut minä pois yksi, poistaa yksittäinen elementti liittyy lista. Syy Tein että on se oikeastaan ​​eräänlainen hankala miettiä, miten poistaa yksittäinen elementti yksittäin linkitetty lista. Meidän täytyy pystyä ohittaa yli jotain luettelossa, joka tarkoittaa saamme point-- me Poistetaanko node-- mutta jotta niin me älä hävitä tietoja, Meidän täytyy liittää tähän solmu tänne, täällä. 

Olen siis luultavasti teki sitä väärin ulkoasut keskenään. Joten olemme alussa meidän lista, olemme etenee läpi, haluamme poistaa tämän solmuun. Jos me vain poistaa sen, olemme rikki ketju. Tämä solmu täällä viittaa kaikki muu, se sisältää ketjun täällä ulos. 

Joten mitä meidän pitää tehdä todella kun olemme päästä tähän pisteeseen, on meidän askel taaksepäin yksi, ja liitä tämä solmu yli tämän solmun, jotta voimme sitten poistaa yksi keskellä. Mutta yksittäin liittyy Luettelot eivät meille tie taaksepäin. Joten meidän täytyy joko pitää kaksi osoitinta, ja siirtää ne tavallaan pois askel, yksi takana muut kuin menemme, tai saada pisteeseen ja sitten lähettää toisen osoitin kautta. Ja kuten näette, se voi saada hieman sotkuinen. Onneksi meillä on toinen tapa ratkaista että, kun puhumme kaksin verroin linkitetty luetteloista. 

Olen Doug Lloyd, tämä on CS50.