[Prehrávanie hudby] 

DOUG LLOYD: OK, tak na tento bod v priebehu, sme sa vzťahuje mnoho základy C. Vieme, že veľa o premenných, polí, ukazovatele, že všetky dobré veci. Tí, ktorí sú nejako postavený Ak chcete zobraziť ako základy, ale môžeme urobiť viac, že ​​jo? Môžeme kombinovať veci spolu zaujímavými spôsobmi. 

A tak poďme to urobiť, začnime vetviť, čo C nám dáva, a začať vytvárať vlastné údaje štruktúry pomocou týchto stavebných bloky dohromady niečo robiť naozaj cenné, užitočné. Jeden spôsob, ako to môžeme urobiť, je hovoriť o zbierok. Tak zatiaľ sme mali jeden druh dát štruktúra pre zastupovanie kolekcií z páči hodnoty, podobné hodnoty. To by byť pole. Máme zbierky celé čísla, alebo zbierky postáv a tak ďalej. 

Štruktúry sú tiež akýsi dát štruktúra pre zber informácií, ale nie je to pre zbieranie ako hodnoty. To zvyčajne sa miešajú rôzne dátové typy spolu vnútri jedinej krabici. Ale nie je to samo o sebe použité k reťazcu spoločne alebo sa pripojiť dohromady podobné predmety, ako pole. Polia sú skvelé pre prvok vzhlédnout, ale Recall že je to veľmi ťažké pre vloženie do matice, ak sme na vkladanie do samého konca tohto poľa. 

A najlepším príkladom mám pre ktoré je insertion sort. Ak si spomínate na naše video na vloženie druhu, tam bolo veľa výdavkom pri majúce vyzdvihnúť prvky a presunúť ich z cesty, aby sa zmestili niečo do stredu vášho poľa. Pole tiež trpí inou Problém, ktorý je nepružnosť. Keď sme sa vyhlásiť poľa, dostaneme jeden pokus na to. Dostávame sa povedať, chcem Táto mnoho prvkov. Môže byť 100, môže to byť 1000, by to mohlo byť x, kde x je číslo, ktoré užívateľ Dal nám na výzvu alebo na príkaz online. 

Ale my sme len jeden pokus na to, my nedostanú do tej doby hovoria oh, som vlastne potreboval 101, alebo som potreboval X plus 20. Príliš neskoro, sme už vyhlásila poľa, a ak chceme získať 101 alebo x zvýšenej o 20, musíme vyhlásiť, úplne iná poľa, skopírovať všetky prvky poľa cez, a potom máme dosť. A čo keď sme opäť zle, čo ak by sme skutočne potrebujú 102, alebo X plus 40, musíme to urobiť znovu. Takže sú veľmi nepružné pre zmenu veľkosti naše dáta, ale ak by sme skombinovať niektoré základy, ktoré sme už dozvedeli o ukazovatele a štruktúr, najmä s využitím dynamickej pamäte alokácie s malloc, my môže dať tieto kúsky dohromady Ak chcete vytvoriť nové dáta structure-- A jednotlivo spojené zoznam by sme mohli say-- ktorý nám umožňuje rast a zmenšiť súbor hodnôt, a nebudeme mať žiadnu zbytočný priestor. 

Takže znovu, nazývame túto myšlienku, tento pojem, pripojený zoznam. Najmä v tomto videu sme hovorí o jednotlivo Google zoznamu a potom ďalšie videá si pohovoríme asi dvojnásobne spojové zoznamy, ktoré je len variáciou na tému tu. Ale single previazaný zoznam sa skladá z uzlov, uzly byť len abstraktné term-- Je to proste niečo volám to je druh štruktúra, v podstate, ja som? Len tak to nazývať node-- a to uzol má dvoch členov, alebo dve polia. To má dáta, zvyčajne integer, charakter float, alebo by mohol byť nejaký iný typ dát že ste definovali pomocou typu def. A obsahuje ukazovateľ na iný uzol rovnakého typu. 

Takže máme dve veci vo vnútri tento uzol, dát a ukazovateľ do iného uzla. A ak začnete vizualizovať to, môžete si o tom myslíte ako reťaz uzlov, ktoré sú spojené dohromady. Máme prvý uzol, to obsahuje dáta, a ukazovateľ do druhého uzla, ktorý obsahuje dát, a ukazovateľ na tretiu uzla. A tak to je dôvod, prečo sme ho hovoru spájať zoznam, oni sú navzájom prepojené. 

Čo to zvláštne Štruktúra uzol vyzerať? No, ak si spomínam z nášho videa na definovanie vlastných typov, s typom def, môžeme definovať structure-- a zadajte definovať štruktúru, ako je tento. tyepdef struct sllist, a potom som pomocou hodnoty slovo tu ľubovoľne uviesť akýkoľvek typ dát, naozaj. Dalo by sa preniesť na celé číslo alebo plaváku, by ste mohli mať, čo chcete. To nie je obmedzený len celé čísla, alebo niečo také. Takže hodnota je len ľubovoľná dátový typ, a potom ukazovateľ do iného uzla rovnakého typu. 

Teraz, tam je trochu háčik Tu sa definuje štruktúru keď je to štruktúra vlastné referenčné. Musím mať dočasnú meno pre moju štruktúru. Na konci dňa som jasne to chcete nazývať SLL uzol, to je nakoniec nový meno časť mojej definície typu, ale nemôžem použiť SLL uzol v stredu tohto. Dôvodom je, nemám vytvoril typ nazvaný SLL uzol až som narazila tento posledný bod tu. Až do tohto bodu, musím mať iný spôsob, ako sa odkazovať na tento typ dát. 

A to je samo referenčné dátový typ. Je to, to je typ dát Štruktúra, ktorá obsahuje údaje, a ukazovateľ na ďalšie štruktúra rovnakého typu. Tak som potrebné, aby bolo možné odkazovať na Tento typ dát aspoň dočasne, tak dávať to dočasné Meno struct sllist mi umožňuje potom povedzte Chcem ukazovateľ do iného struct sllist, struct sllist hviezda, a potom potom, čo som dokončil definíciu, Aj teraz môže hovoriť tento typ uzol SLL. 

Takže to je dôvod, prečo ste vidieť, že je to dočasný názov tu, ale trvalé meno sem. Niekedy môžete vidieť definície štruktúry, napríklad, že nie sú vlastný referenčný, že nemajú tu meno Špecifikátor. To by len povedať typedef struct, otvoriť zložená zátvorka a potom ju definovať. Ale ak ste struct je self Referenčný, pretože tento je, je potrebné špecifikovať dočasný názov typu. Ale nakoniec, teraz že sme urobili to, môžeme len odkazovať na tieto uzly, tieto jednotky, ako SLL uzly na účely zvyšku tohto videa. 

Dobre, takže vieme, ako vytvoriť prepojený zoznamu uzlov. Vieme, ako definovať prepojený zoznam uzol. Teraz, keď ideme na začiatok ich použitie zhromažďovať informácie, tam je niekoľko operácií sme musí pochopiť a pracovať s. Potrebujeme vedieť, ako vytvoriť prepojený zoznam zo vzduchu. Ak nie je žiadny zoznam už, chceme začať jeden. Preto musíme byť schopní vytvoriť prepojený zoznam, musíme pravdepodobne hľadať v zozname odkazov nájsť prvok, čo hľadáme. Musíme byť schopní vložiť nové veci do zoznamu, chceme náš zoznam, aby mohol rásť. A rovnako, chceme byť schopní odstrániť veci z nášho zoznamu, chceme, aby náš zoznam, aby bolo možné zmenšovať. A na konci nášho programy, najmä Ak si spomínate, že sme dynamicky prideľovanie pamäte vytvoriť tieto zoznamy typicky, chceme oslobodiť všetkých, že pamäť Keď sme hotoví s ňou pracovať. A preto musíme byť schopní Ak chcete odstrániť Celý spájať zoznam v jednom zlyhania Swoop. Takže poďme prejsť niektoré z týchto operácií a ako ich môžeme predstaviť, hovorí v pseudokódu kóde špecificky. Takže chceme vytvoriť spájať zoznam, takže možno sme chcete definovať funkciu s týmto prototypom. SLL uzol hviezda, tvoriť, a ja som okolo v jednom argumentu, niektorí ľubovoľné dáta typ opäť nejakého ľubovoľného typu dát. Ale ja som returning-- túto funkciu by mal vrátiť ku mne ukazovateľ, na single spájať zoznam uzol. Opäť platí, že sa snažíme o vytvorenie prepojený zoznam zo vzduchu, takže musím ukazovateľ tento zoznam, keď som urobil. 

Takže aké sú kroky tu ide? No, prvá vec, ja som chystá urobiť, je dynamicky prideliť priestor pre nový uzol. Opäť sme vytvoriť to z tenkej vzduch, takže musíme malloc priestor pre to. A samozrejme okamžite potom, čo sme malloc, vždy skontrolujte, či, že naše pointer-- sme nedostali naspäť null. Vzhľadom k tomu, keď sa budeme snažiť a podriadenosť ukazovatele null, budeme trpieť segfault a my nechceme, že. 

Potom sme sa chcete vyplniť v tejto oblasti, chceme inicializovať hodnota poľa a inicializovať ďalšie pole. A potom chceme to-- nakoniec ako prototyp funkcie indicates-- chceme vrátiť ukazovateľ na uzol SLL. Tak čo, aby to vyzerať vizuálne? No, v prvom budeme dynamicky prideliť priestor pre nové SLL uzla, takže sme malloc-- to vizuálne reprezentácie uzla sme práve vytvorili. A skontrolujte, či to nie je null-- v tomto prípade, obraz nebude mať ukázal, či je to null, by sme dostatok pamäte, tak sme dobré tam ísť. Takže teraz sme na krok C, inicializáciu poľa uzly hodnoty. No, na základe tejto funkcii volajte Ja používam tu, vyzerá to chcem odovzdať 6, Takže budem 6 v poli hodnoty. Teraz, inicializovať ďalšie pole. No, čo mám robiť tam, nie je nič, čo ďalej, vpravo, to je jediná vec, v zozname. Takže to, čo je ďalšia vec na zozname? 

Nemalo by ukazovať na nič, že jo. Nič iné tam, tak to, čo je poňatie vieme, že je to nothing-- ukazovatele na nič? Malo by to byť snáď chceme dať ukazovatele null tam, a ja predstavujú null ukazovateľ ako len červené pole, nemôžeme ísť ďalej. Ako budeme o niečo vidieť neskôr, budeme mať nakoniec aj reťaze šípok pripojenie tieto uzly dohromady, ale keď narazí na červené pole, to je null, nemôžeme ísť ďalej, že je koniec zoznamu. 

A konečne, chceme len, aby vrátiť ukazovateľ do tohto uzla. Takže budeme hovoriť nový, a vráti nový takže ho možno použiť v bez ohľadu na funkciu ju vytvoril. Takže tam ideme, sme vytvorili single spájať zoznam uzol zo vzduchu, a teraz máme zoznam, môžeme pracovať. 

Teraz povedzme, že už majú veľký reťaz, a chceme nájsť niečo, čo v ňom. A chceme funkciu, ktorá sa deje vrátiť true alebo false, v závislosti na tom, či hodnota existuje v tomto zozname. Funkcia prototyp, alebo Vyhlásenie pre túto funkciu, môže vyzerať ako tohle-- bool nájsť, a potom chceme odovzdať dva argumenty. 

Prvý z nich, je ukazovateľ na Prvý prvok v Google zoznamu. To je v skutočnosti niečo, čo budete vždy chcú sledovať, a v skutočnosti by mohlo byť niečo, čo si dokonca dať do globálne premenné. Akonáhle si vytvoriť zoznam, vždy, vždy Chcete sledovať veľmi Prvý prvok zoznamu. Týmto spôsobom sa môžete obrátiť na všetky ostatné prvky podľa práve v nadväznosti na reťaz, bez toho aby museli držať ukazovatele neporušené na každý prvok. Jediné, čo potrebujete mať prehľad o prvú jedno, pokiaľ sa všetci zreťazenie. 

A potom druhá vec sme okolo znovu je ľubovoľne some-- bez ohľadu na typ dát sme hľadá je vnútri dúfajme, že jeden z uzlov v zozname. Takže aké sú kroky? No, prvá vec, ktorú robíme, je vytvoríme priečny ukazovateľ ukazujúci na zoznamoch hlavy. No, prečo to robíme, že sme už majú ukazovateľ na zoznamoch hlave, prečo nie my len presunúť, že jedna okolo? No, ako som práve povedal, je to naozaj dôležité pre nás vždy sledovať z Úplne prvý prvok v zozname. A tak je to vlastne lepšie vytvoriť duplikát, ktorý, a použiť sa pohybovať, takže sme nikdy náhodne vzdialiť, alebo vždy majú ukazovateľ v určitom okamihu, ktorý je priamo na prvý prvok v zozname. Takže je lepšie vytvoriť Druhý, ktorý používame k pohybu. 

Potom sme len porovnať, či hodnota poľa v tomto uzle je to, čo hľadáme, a ak je to nie, len sme presunúť na ďalší uzol. A my sme pokračovať v tom, že cez, a znovu, a znovu, kým buď nájsť prvok, alebo si hit null-- sme došli na koniec zoznamu a je to tam nie je. To by malo snáď nehovorí aby vás ako práve lineárny vyhľadávania, sme len replikácie ju single spájať zoznam štruktúra namiesto použitia poľa, ako to urobiť. 

Tak tu je príklad single previazaný zoznam. Ten sa skladá z päť uzlov, a my máme ukazovateľ na hlave Zoznam, ktorý sa nazýva zoznam. Prvá vec, ktorú chceme urobiť, je znovu vytvoriť túto traversal ukazovateľ. Takže teraz máme dva ukazovatele tento bod na rovnakú vec. 

Teraz, všimnite si aj tu, ja nie musieť malloc žiadny priestor pre tráv. Nepovedal som, že tráv rovná malloc niečo, že uzol už existuje, že priestor v pamäti už existuje. Takže všetko, čo som vlastne robí, je vytvorenie ďalšej ukazovateľ na neho. Nie som mallocing ďalšie priestor, stačí teraz dva ukazovatele smerujúce k rovnakej veci. 

Takže je 2 to, čo som hľadal? No, takže namiesto toho som si budeme sťahovať do ďalšej. Takže v podstate by som povedal, tráv sa rovná tráv ďalšie. Je 3 to, čo som hľadal, no. Tak som aj naďalej ísť vďaka, až nakoniec dostať sa až 6, čo je to, čo som hľadal pre založené na volanie funkcie Aj majú v hornej časti tam, a tak som urobil. 

A teraz, čo keď element, že som hľadáte, nie je v zozname, je to ešte bude fungovať? No, zistíte, že zoznam tu je nepatrne odlišný, a to je ďalšia vec, ktorá je dôležité s previazané zoznamy, nemusíte zachovať je v ľubovoľnom poradí. Môžete, ak chcete, ale možno ste už zaznamenali že nie sme sledovanie aký počet element sme na. 

A to je druh z jedného obchodu, ktorý sme majú s Google zoznamu veršov polí, Je to nemáme náhodný prístup ešte. Nemôžeme len tak povedať, chcem ísť na 0. prvku, alebo 6. náplňou mojej poľa, čo sa dá robiť v poli. Nemôžem povedať, že chcem ísť do 0. prvok, alebo 6. element, alebo 25. prvok môjho zoznamu Google, nie je index spojený s nimi. A tak to nezáleží ak by sme zachovať náš zoznam v poradí. Ak chcete, aby vás Určite môže, ale je tu žiadny dôvod, prečo je potrebné, aby byť zachované v ľubovoľnom poradí. Takže znova, poďme sa pokúsiť nájsť 6 v tomto zozname. No, začneme u začiatok, nenájdeme 6, a potom pokračujeme nenájdenia 6, kým sa nakoniec dostať sem. Takže práve teraz tráv body do uzla obsahujúce 8, a šesť nie je tam. 

Takže ďalším krokom by bolo prejdete na ďalší ukazovateľ, tak povedať, tráv rovná tráv ďalšie. No, tráv ďalšie, indikované Tamojší červená krabička, je null. Takže tam kam inam go, a tak v tomto bode môžeme konštatovať, že sme dosiahli koniec zoznamu Google, a 6 nie je tam. A to by sa vrátil false v tomto prípade. 

OK, ako sme sa vložiť nový uzol do Google zoznamu? Takže sme boli schopní vytvoriť prepojený zoznam z ničoho, ale pravdepodobne chcieť vybudovať reťazca a nie vytvoriť veľa odlišných zoznamov. Chceme mať jeden zoznam, ktorý má veľa uzlov v ňom, nie banda zoznamov s jedným uzlom. Takže môžeme nielen udržať pomocou Vytvoriť Funkcie sme definovali skôr, teraz sme chcú vložiť do Zoznam, ktorý už existuje. 

Takže tomto prípade, ideme odovzdať dva argumenty, ukazovateľ na hlave, ktorý spájať zoznam, ktorý chceme pridať. Opäť platí, že je dôvod, prečo je to tak dôležité, že sme vždy sledovať to, pretože je to jediný spôsob, ako skutočne musieť odkazovať sa na celý zoznam je len tým, že ukazovateľ na prvý prvok. Takže chceme odovzdať v ukazovateľ na tento prvý prvok, a bez ohľadu na hodnotu, ktorú chcete pridať do zoznamu. A nakoniec táto funkcia bude vráti ukazovateľ na nového šéfa prepojeného zoznamu. 

Aké sú kroky tu ide? No, rovnako ako u vytvárať, musíme dynamicky prideľovať priestor pre nový uzol, a skontrolujte, istí, že nemáme dostatok pamäte, znova, preto, že sme pomocou malloc. Potom chceme naplniť a vložte uzla, tak dal číslo, bez ohľadu val je, do uzla. Chceme vložiť uzol na začiatok Google zoznamu. 

Tam je dôvod, prečo som to chceš urobiť, a to môže byť stojí za sekundu pozastaviť video tu, a premýšľať o tom, prečo by som chcel vložiť na začiatku prepojenú Zoznam. Opäť som sa zmienil skôr, že to naozaj nie je jedno, či sa nám to uchovať v akomkoľvek poriadok, takže možno je to stopa. A si videl, čo by sa stalo, keby sme Chcel to-- alebo len na sekundu Pred keď sme išli pomocou vyhľadávania vám mohol vidieť, čo by mohlo sa stalo, keby sme sa snažili pre vloženie na koniec zoznamu. Pretože my nemajú ukazovateľ na koniec zoznamu. 

Takže dôvod, prečo by som chcel pre vloženie na začiatku, je preto, že som to urobiť okamžite. Mám ukazovateľ na začiatku, a uvidíme to v vizuálnej v sekunde. Ale ak chcem vložiť na koniec, Musím začať od začiatku, prejsť celú cestu až do koniec, a potom ho pridajú. Takže to by znamenalo, že vložením na koniec zoznamu stala by sa o n prevádzku, sa vracia k našej diskusii o výpočtovej zložitosť. To by sa stať o n prevádzky, kde aj zoznam dostal väčšie a väčšie, a väčší, bude to čím ďalej ťažšie križovať niečo Na konci. Ale je to vždy naozaj ľahké pripináčika niečo na začiatku, ste vždy na začiatku. 

A uvidíme opäť vizuálne tohto. A potom raz sme skončili, akonáhle sme vložil nový uzol, Chceme sa vrátiť náš ukazovateľ nový šéf prepojeného zoznamu, ktorý od tej doby sme vkladanie u začiatok, bude skutočne ukazovateľ na uzle sme práve vytvorené. Poďme si to predstaviť, pretože si myslím, že to pomôže. 

Tak tu je náš zoznam, skladá sa z štyri prvky, uzol obsahujúci 15, čo ukazuje na uzol obsahujúce 9, ktorý poukazuje na uzle, ktorý obsahuje 13, čo ukazuje na uzol obsahujúce 10, ktorý má null ukazovateľ pre svoju ďalšiu ukazovateľ tak to je koniec zoznamu. Takže chceme vložiť nový uzol s hodnotou 12 na začiatku tohto zoznam, čo budeme robiť? No, v prvom sme malloc priestor pre uzol, a potom sme dali 12 tam. 

Takže teraz sme sa dosiahne bod rozhodnutia, že jo? Máme pár ukazovatele, ktoré sme mohli pohyb, ktorý by sme mali presunúť ako prvý? Mali by sme urobiť 12 prejdite na Nový šéf list-- alebo prepáčte, by sme mali 12 poukazujú na staré čele zoznamu? Alebo by sme mali povedať, že Zoznam teraz začína na 12. Tam je rozdiel tam, a my sa pozrieme na to, čo sa deje s oboma v druhom. 

Ale toto vedie k skvelé tému pre bočnom paneli čo je, že jeden z najkomplikovanejšie veci s spojových zoznamov je usporiadať ukazovatele v správnom poradí. Pokiaľ sa pohybovať vecami mimo prevádzku, môžete skončiť nechtiac orphaning zvyšok zoznamu. A tu je príklad toho. Tak poďme s myšlienkou of-- No, my sme práve vytvorili 12. Vieme, že 12 bude nový šéf zoznamu, a tak prečo nie my len presunúť ukazovateľ zoznam tam bodu. 

OK, tak to je dobre. Takže teraz kde robí 12 ďalší bod? Myslím, vizuálne vidíme že to bude ukazovať na 15, ako ľudia, je to naozaj jasné, k nám. Ako počítač vie? Nemáme nič ukázal na 15 už, že jo? 

Sme stratili schopnosť sa odkazovať na 15. Nemôžeme povedať, nový šípku vedľa rovná niečo, nič tam nie je. V skutočnosti sme sa osirelý zvyšok zoznamu Tým máme náhodne zlomený reťaz. A my rozhodne nechceme robiť. 

Takže poďme späť a skúste to znova. Možno, že správna vec je stanoviť ďalšie ukazovatele 12 je na staré čele zoznamu prvý, potom sa môžeme presunúť na zoznam u konca. A v skutočnosti, že je správne poradie, že my treba dodržiavať, keď sme pracuje s jednotlivo prepojeného zoznamu. Vždy chceme pripojiť nový prvok do zoznamu, Než sme sa tento druh dôležitým krokom zmeny kde v čele zoznamu je Google. Opäť platí, že je to tak zásadnú vec, Nechceme stratiť prehľad o tom. 

Preto chceme, aby sa uistil, že všetko sa pripútal spolu, Než sme sa presunúť tento ukazovateľ. A tak by to bolo správne poradie, ktorý je pre pripojenie 12 do zoznamu, potom hovoria, že zoznam začína 12. Ak sa nám povedal, že zoznam začína na 12 a potom sa pokúsil pripojenie 12 do zoznamu, sme už videli, čo sa stane. Strácame zoznamu omylom. 

OK, takže ešte jedna vec, o čom hovoriť. Čo ak chceme zbaviť celý spojený zoznam naraz? Opäť sme mallocing všetko tento priestor, a tak sme treba ho uvoľniť, keď budeme hotoví. Takže teraz chceme zmazať celý previazaný zoznam. No, čo chceme robiť? 

Ak sme dosiahli ukazovatele null, my chcú zastaviť, inak, stačí zmazať zvyšok zoznamu a potom ma oslobodil. Odstráňte zvyšok zoznamu, a potom uvoľniť aktuálny uzol. Čo to znie ako, Akú technikou máme rozprávali o skôr Znie to ako? Odstrániť všetci ostatní, potom vrátiť a odstrániť ma. 

To je rekurzia, sme urobil problém o niečo menší, hovoríme zmazať každého iné, potom môžete ma odstrániť. A ďalej po ceste, ktorá uzol povie, odstrániť všetky ostatné. Ale nakoniec sa dostaneme k miesto, kde je zoznam null, a to je naša základňa prípad. 

Takže poďme sa pozrieť na to, a ako to môže fungovať. Tak tu je náš zoznam, je to rovnaké Zoznam práve sme hovorili o, a je tu kroky. Je tu veľa textu tu, ale Dúfajme, že vizualizácia pomôže. 

Tak sme have-- a tiež som vytiahol up nášho stack frames ilustrácie z nášho videa na volanie komíny, a dúfajme, že to všetko spoločne vám ukáže, čo sa deje. Tak tu je náš pseudokód kód. Ak dôjdeme null ukazovateľ, zastaviť, inak, odstráni zvyšok zoznamu, potom uvoľnenie aktuálnej uzol. Takže teraz, list-- ukazovateľ, že sme odovzdaním zničiť body do 12 rokov. 12 nie je ukazovatele null, takže sme chystá odstrániť zvyšok zoznamu. 

Čo vymazanie Zvyšok z nás zapojiť? No, to znamená, že dodávanie zavolať zničiť, povedal že 15 rokov je na začiatku Zvyšok zoznamu chceme zničiť. A tak sa výzva k zničeniu 12 je v istom zmysle v poradí. Je to mrazené tam a čakal, zavolať zničiť 15, dokončiť svoju prácu. 

No, 15 nie je nulový ukazovateľ, a takže to bude hovoriť, v poriadku, dobre, odstráňte zvyšok zoznamu. Zvyšok zoznamu začína 9, a tak sme si len počkajte, až sa odstrániť všetko, čo veci, potom sa vrátiť a odstrániť ma. No 9 to bude hovoriť, no, Nie som nulový ukazovateľ, takže ostatní vymažte zoznam tu. A tak sa snaží a zničiť 13. 13 hovorí, ja nie som nulový ukazovateľ, to isté, to prejde okolo babku. 10 nie je ukazovatele null, 10 obsahuje ukazovatele null, ale 10 nie je sám null ukazovateľ práve teraz, a tak odovzdá dolár príliš. 

A teraz zoznam body tam, ho Naozaj by chcel poukázať na some-- keby som mala viac priestoru v obraze, že by chcel poukázať na nejaký náhodný vesmíru že nevieme, čo to je. To je nulový ukazovateľ hoci, zoznam je doslova teraz nastavený, že je to hodnota null. Je to ukázal hneď v tej červeného poľa. Dosiahli sme ukazovatele null, takže môžeme zastaviť, a my sme urobili. 

A tak, že rám je fialová now-- at the Vrchol stack-- to je aktívny rám, ale je to hotovo. Ak sme dosiahli nulový ukazovateľ, zastaviť. Nechceme robiť nič, my nemôže uvoľniť ukazovatele null, sme nemali malloc akýkoľvek priestor, a tak sme hotoví. Takže funkcie rámu je zničená, a my sme resume-- sme tam, kde sme opustili off s budúci najvyššia, čo Je to tmavo modrý rámik tu. Tak sme vyzdvihnúť presne tam, kde sme skončili. Vypúšťa sme zvyšku Zoznam už, takže teraz sme chystá uvoľniť aktuálny uzly. Takže teraz sa môžeme oslobodiť tento uzol, a teraz sme došli na koniec funkcie. A tak, že funkcia rám je zničená, a my vyzdvihnúť na svetlo modrou. 

Tak to says-- už som done-- vypustiť zvyšok zoznamu, tak oslobodí aktuálny uzol. A teraz je žltý rámček späť na vrchole zásobníka. A tak ako vidíte, sme teraz ničí zoznam sprava doľava. 

Čo by sa stalo, aj keď, ak sme robili veci zle? Rovnako ako keď sme sa pokúšali pridať prvok. Ak by sme spackal reťaz, ak sme sa nepripojili ukazovatele v správnom poradí, keby sme len oslobodil prvý prvok, ak sme práve prepustené vedúci zoznamu, teraz sme nemajú žiadny spôsob, ako sa odkazovať na zvyšok zoznamu. A tak budeme mať osirelé všetko, mali by sme to, čo je volal k pretečeniu pamäte. Ak si spomínate z nášho videa dynamické prideľovanie pamäte, to nie je moc dobrá vec. 

Tak ako som povedal, že sú niekoľko operácií že musíme použiť na prácu s spájať zoznam efektívne. A možno ste si všimli som vynechať jeden, zmazanie jedného prvku z prepojeného Zoznam. Dôvod, prečo som to urobil Je to vlastne druh zradné premýšľať o tom, ako odstrániť jediný prvok z singly spájať zoznam. Musíme byť schopní preskočiť niečo v zozname, ktorý znamená, že sme si na point-- my chcete zmazať túto node-- ale aby sa to robí tak, aby sme nestratí žiadne informácie, musíme spojiť to uzol sem, sem. 

Tak som to urobil zle nejspíš z vizuálneho hľadiska. Takže sme na začiatku nášho zoznam, sme vybavovaných, chceme zmazať tento uzol. Ak by sme jednoducho odstrániť, sme zlomený reťaz. Tento uzol tu sa vzťahuje na všetko ostatné, že obsahuje reťazec od tady na von. 

Takže to, čo musíme urobiť skutočne potom, čo sa dostaneme do tohto bodu, ich musíme urobiť krok späť jeden, a pripojenie tohto uzla do tohto uzla, takže sa potom môžeme zmazať ten uprostred. Ale jednotlivo prepojené zoznamy nie poskytujú nám spôsob, ako ísť späť. Takže potrebujeme buď udržať dva ukazovatele, a presunúť ich druh off kroku, jeden za ostatné, ako sme ísť, alebo dostať do bodu, a potom poslať ďalší ukazovateľ cez. A ako môžete vidieť, to môže dostať trochu chaotický. Našťastie, máme Ďalší spôsob, ako vyriešiť to, keď hovoríme o dvojnásobne spojových zoznamov. 

Som Doug Lloyd, je to CS50.