[Přehrávání hudby] 

DOUG LLOYD: OK, tak na tento bod v průběhu, jsme se vztahuje mnoho základy C. Víme, že hodně o proměnných, polí, ukazatele, že všechny dobré věci. Ti, kteří jsou nějak postavený Chcete-li zobrazit jako základy, ale můžeme udělat víc, že ​​jo? Můžeme kombinovat věci spolu zajímavými způsoby. 

A tak pojďme to udělat, začněme větvit, co C nám dává, a začít vytvářet vlastní údaje struktury pomocí těchto stavebních bloky dohromady něco dělat opravdu cenné, užitečné. Jeden způsob, jak to můžeme udělat, je mluvit o sbírek. Tak zatím jsme měli jeden druh dat struktura pro zastupování kolekcí z líbí hodnoty, podobné hodnoty. To by být pole. Máme sbírky celá čísla, nebo sbírky postav a tak dále. 

Struktury jsou také jakýsi dat struktura pro sběr informací, ale není to pro sbírání jako hodnoty. To obvykle se mísí různé datové typy spolu uvnitř jediné krabici. Ale není to samo o sobě použity k řetězci společně nebo se připojit dohromady podobné předměty, jako pole. Pole jsou skvělé pro prvek vzhlédnout, ale Recall že je to velmi obtížné pro vložení do matice, pokud jsme na vkládání do samého konce tohoto pole. 

A nejlepším příkladem mám pro které je insertion sort. Pokud si vzpomínáte na naše video na vložení druhu, tam bylo hodně výdajem při mající vyzvednout prvky a přesunout je z cesty, aby se vešly něco do středu vašeho pole. Pole také trpí jinou Problém, který je nepružnost. Když jsme se prohlásit pole, dostaneme jeden pokus na to. Dostáváme se říci, chci Tato mnoho prvků. Může být 100, může to být 1000, by to mohlo být x, kde x je číslo, které uživatel Dal nám na výzvu nebo na příkaz online. 

Ale my jsme jen jeden pokus na to, my nedostanou do té doby říkají oh, jsem vlastně potřeboval 101, nebo jsem potřeboval X plus 20. Příliš pozdě, jsme již prohlásila pole, a chceme-li získat 101 nebo x zvýšené o 20, musíme prohlásit, úplně jiná pole, zkopírovat všechny prvky pole přes, a pak máme dost. A co když jsme opět špatně, co pokud bychom skutečně potřebují 102, nebo X plus 40, musíme to udělat znovu. Takže jsou velmi neflexibilní pro změnu velikosti naše data, ale pokud bychom zkombinovat některé základy, které jsme již dozvěděli o ukazatele a struktur, zejména s využitím dynamické paměti alokace s malloc, my může dát tyto kousky dohromady Chcete-li vytvořit nová data structure-- A jednotlivě spojeny seznam bychom mohli say-- který nám umožňuje růst a zmenšit soubor hodnot, a nebudeme mít žádnou zbytečný prostor. 

Takže znovu, nazýváme tuto myšlenku, tento pojem, připojený seznam. Zejména v tomto videu jsme mluví o jednotlivě Google seznamu a pak další videa si promluvíme asi dvojnásobně spojové seznamy, které je jen variací na téma zde. Ale singly provázaný seznam se skládá z uzlů, uzly být jen abstraktní term-- Je to prostě něco volám to je druh struktura, v podstatě, já jsem? Jen tak to nazývat node-- a to uzel má dva členy, nebo dvě pole. To má data, obvykle integer, charakter float, nebo by mohl být nějaký jiný typ dat že jste definovali pomocí typu def. A obsahuje ukazatel na jiný uzel stejného typu. 

Takže máme dvě věci uvnitř tento uzel, dat a ukazatel do jiného uzlu. A pokud začnete vizualizovat to, můžete si o tom myslíte jako řetěz uzlů, které jsou spojeny dohromady. Máme první uzel, to obsahuje data, a ukazatel do druhého uzlu, který obsahuje dat, a ukazatel na třetí uzlu. A tak to je důvod, proč jsme ho hovoru spojový seznam, oni jsou navzájem propojeny. 

Co to zvláštní Struktura uzel vypadat? No, pokud si vzpomínám z našeho videa na definování vlastních typů, s typem def, můžeme definovat structure-- a zadejte definovat strukturu, jako je tento. tyepdef struct sllist, a pak jsem pomocí hodnoty slovo zde libovolně uvést jakýkoli typ dat, opravdu. Dalo by se přenést na celé číslo nebo plováku, byste mohli mít, co chcete. To není omezen jen celá čísla, nebo něco takového. Takže hodnota je pouze libovolná datový typ, a pak ukazatel do jiného uzlu stejného typu. 

Nyní, tam je trochu háček Zde se definuje strukturu když je to struktura vlastní referenční. Musím mít dočasnou jméno pro mou strukturu. Na konci dne jsem jasně to chcete nazývat SLL uzel, to je nakonec nový jméno část mé definice typu, ale nemohu použít SLL uzel ve středu tohoto. Důvodem je, nemám vytvořil typ nazvaný SLL uzel až jsem narazila tento poslední bod zde. Až do tohoto bodu, musím mít jiný způsob, jak se odkazovat na tento typ dat. 

A to je samo referenční datový typ. Je to, to je typ dat Struktura, která obsahuje údaje, a ukazatel na další struktura stejného typu. Tak jsem třeba, aby bylo možné odkazovat na Tento typ dat alespoň dočasně, tak dávat to dočasné Jméno struct sllist mi umožňuje pak řekněte Chci ukazatel do jiného struct sllist, struct sllist hvězda, a poté poté, co jsem dokončil definici, I nyní může říkat tento typ uzel SLL. 

Takže to je důvod, proč jste vidět, že je to dočasný název tady, ale trvalé jméno sem. Někdy můžete vidět definice struktury, například, že nejsou vlastní referenční, že nemají zde jméno specifikátor. To by jen říct typedef struct, otevřít složená závorka a pak ji definovat. Ale pokud jste struct je self Referenční, protože tento je, je třeba specifikovat dočasný název typu. Ale nakonec, teď že jsme udělali to, můžeme jen odkazovat na tyto uzly, tyto jednotky, jako SLL uzly pro účely zbytku tohoto videa. 

Dobře, takže víme, jak vytvořit propojený seznamu uzlů. Víme, jak definovat propojený seznam uzel. Teď, když jdeme na začátek jejich použití shromažďovat informace, tam je několik operací jsme musí pochopit a pracovat s. Potřebujeme vědět, jak vytvořit propojený seznam ze vzduchu. Pokud není žádný seznam už, chceme začít jeden. Proto musíme být schopni vytvořit propojený seznam, musíme pravděpodobně hledat v seznamu odkazů nalézt prvek, co hledáme. Musíme být schopni vložit nové věci do seznamu, chceme náš seznam, aby mohl růst. A stejně, chceme být schopni odstranit věci z našeho seznamu, chceme, aby náš seznam, aby bylo možné zmenšovat. A na konci našeho programy, zejména Pokud si vzpomínáte, že jsme dynamicky přidělování paměti vytvořit tyto seznamy typicky, chceme osvobodit všechny, že paměť Když jsme hotovi s ní pracovat. A proto musíme být schopni Chcete-li odstranit Celý spojový seznam v jednom selhání swoop. Takže pojďme projít některé z těchto operací a jak je můžeme představit, mluví v pseudokódu kódu specificky. Takže chceme vytvořit spojový seznam, takže možná jsme chcete definovat funkci s tímto prototypem. SLL uzel hvězda, tvořit, a já jsem kolem v jednom argumentu, někteří libovolná data typ opět nějakého libovolného typu dat. Ale já jsem returning-- tuto funkci by měl vrátit ke mně ukazatel, na singly spojový seznam uzel. Opět platí, že se snažíme o vytvoření propojený seznam ze vzduchu, takže musím ukazatel tento seznam, když jsem udělal. 

Takže jaké jsou kroky zde jedná? No, první věc, já jsem chystá udělat, je dynamicky přidělit prostor pro nový uzel. Opět jsme vytvořit to z tenké vzduch, takže musíme malloc prostor pro to. A samozřejmě okamžitě poté, co jsme malloc, vždy zkontrolujte, zda, že naše pointer-- jsme nedostali zpátky null. Vzhledem k tomu, když se budeme snažit a podřízenost ukazatele null, budeme trpět segfault a my nechceme, že. 

Pak jsme se chcete vyplnit v této oblasti, chceme inicializovat hodnota pole a inicializovat další pole. A pak chceme to-- nakonec jako prototyp funkce indicates-- chceme vrátit ukazatel na uzel SLL. Tak co, aby to vypadat vizuálně? No, v první budeme dynamicky přidělit prostor pro nové SLL uzlu, takže jsme malloc-- to vizuální reprezentace uzlu jsme právě vytvořili. A zkontrolujte, zda to není null-- v tomto případě, obraz nebude mít ukázal, jestli je to null, bychom dostatek paměti, tak jsme dobré tam jít. Takže teď jsme ke kroku C, inicializaci pole uzly hodnoty. No, na základě této funkci volejte Já používám zde, vypadá to chci předat 6, Takže budu 6 v hodnotovém poli. Nyní, inicializovat další pole. No, co mám dělat tam, není nic, co dál, vpravo, to je jediná věc, v seznamu. Takže to, co je další věc na seznamu? 

Nemělo by ukazovat na nic, že ​​jo. Nic jiného tam, tak to, co je pojetí víme, že je to nothing-- ukazatele na nic? Mělo by to být snad chceme dát ukazatele null tam, a já představují null ukazatel jak jen červené pole, nemůžeme jít dál. Jak budeme o něco vidět později, budeme mít nakonec i řetězy šipek připojení tyto uzly dohromady, ale když narazí na červené pole, to je null, nemůžeme jít dál, že je konec seznamu. 

A konečně, chceme jen, aby vrátit ukazatel do tohoto uzlu. Takže budeme říkat nový, a vrátí nový takže jej lze použít v bez ohledu na funkci ji vytvořil. Takže tam jdeme, jsme vytvořili singly spojový seznam uzel ze vzduchu, a teď máme seznam, můžeme pracovat. 

Nyní řekněme, že už mají velký řetěz, a chceme najít něco, co v něm. A chceme funkci, která se děje vrátit true nebo false, v závislosti na tom, zda hodnota existuje v tomto seznamu. Funkce prototyp, nebo Prohlášení pro tuto funkci, může vypadat jako tohle-- bool najít, a pak chceme předat dva argumenty. 

První z nich, je ukazatel na První prvek v Google seznamu. To je ve skutečnosti něco, co budete vždy chtějí sledovat, a ve skutečnosti by mohlo být něco, co si dokonce dát do globální proměnné. Jakmile si vytvořit seznam, vždycky, vždycky Chcete sledovat velmi První prvek seznamu. Tímto způsobem se můžete obrátit na všechny ostatní prvky podle právě v návaznosti na řetěz, aniž by museli držet ukazatele neporušené na každý prvek. Jediné, co potřebujete mít přehled o první jedno, pokud se všichni zřetězeno. 

A pak druhá věc jsme kolem znovu je libovolně some-- bez ohledu na typ dat jsme hledá je uvnitř doufejme, že jeden z uzlů v seznamu. Takže jaké jsou kroky? No, první věc, kterou děláme, je vytvoříme příčný ukazatel ukazující na seznamech hlavy. No, proč to děláme, že jsme již mají ukazatel na seznamech hlavě, proč ne my jen přesunout, že jedna kolem? No, jak jsem právě řekl, je to opravdu důležité pro nás vždy sledovat z Úplně první prvek v seznamu. A tak je to vlastně lepší vytvořit duplikát, který, a použít se pohybovat, takže jsme nikdy náhodně vzdálit, nebo vždy mají ukazatel v určitém okamžiku, který je přímo na první prvek v seznamu. Takže je lepší vytvořit Druhý, který používáme k pohybu. 

Pak jsme jen porovnat, zda hodnota pole v tomto uzlu je to, co hledáme, a pokud je to ne, jen jsme přesunout na další uzel. A my jsme pokračovat v tom, že přes, a znovu, a znovu, dokud buď najít prvek, nebo si hit null-- jsme došli na konec seznamu a je to tam není. To by mělo snad neříká aby vás jako právě lineární vyhledávání, jsme jen replikace ji singly spojový seznam struktura namísto použití pole, jak to udělat. 

Tak tady je příklad singly provázaný seznam. Ten se skládá z pět uzlů, a my máme ukazatel na hlavě Seznam, který se nazývá seznam. První věc, kterou chceme udělat, je znovu vytvořit tuto traversal ukazatel. Takže teď máme dva ukazatele tento bod na stejnou věc. 

Teď, všimněte si i zde, já ne muset malloc žádný prostor pro trav. Neřekl jsem, že trav rovná malloc něco, že uzel již existuje, že prostor v paměti již existuje. Takže všechno, co jsem vlastně dělá, je vytvoření další ukazatel na něj. Nejsem mallocing další prostor, stačí nyní dva ukazatele směřující ke stejné věci. 

Takže je 2 to, co jsem hledal? No, takže místo toho jsem si budeme stěhovat do další. Takže v podstatě bych řekl, trav se rovná trav další. Je 3 to, co jsem hledal, no. Tak jsem i nadále jít díky, až nakonec dostat se až 6, což je to, co jsem hledal pro založené na volání funkce I mají v horní části tam, a tak jsem udělal. 

A teď, co když element, že jsem hledáte, není v seznamu, je to ještě bude fungovat? No, zjistíte, že seznam zde je nepatrně odlišný, a to je další věc, která je důležité s provázané seznamy, nemusíte zachovat je v libovolném pořadí. Můžete, pokud chcete, ale možná jste již zaznamenali že nejsme sledování jaký počet element jsme na. 

A to je druh z jednoho obchodu, který jsme mají s Google seznamu veršů polí, Je to nemáme náhodný přístup ještě. Nemůžeme jen tak říci, chci jít na 0. prvku, nebo 6. náplní mé pole, což se dá dělat v poli. Nemůžu říct, že chci jít do 0. prvek, nebo 6. element, nebo 25. prvek mého seznamu Google, není index spojený s nimi. A tak to nezáleží pokud bychom zachovat náš seznam v pořadí. Pokud chcete, aby vás Určitě může, ale je tu žádný důvod, proč je třeba, aby být zachovány v libovolném pořadí. Takže znovu, pojďme se pokusit najít 6 v tomto seznamu. No, začneme u začátek, nenajdeme 6, a pak pokračujeme nenalezení 6, dokud se nakonec dostat sem. Takže právě teď trav body do uzlu obsahující 8, a šest není tam. 

Takže dalším krokem by bylo přejdete na další ukazatel, tak říci, trav rovná trav další. No, trav další, indikováno Tamní červená krabička, je null. Takže tam kam jinam go, a tak v tomto bodě můžeme konstatovat, že jsme dosáhli konec seznamu Google, a 6 není tam. A to by se vrátil false v tomto případě. 

OK, jak jsme se vložit nový uzel do Google seznamu? Takže jsme byli schopni vytvořit propojený seznam z ničeho, ale pravděpodobně chtít vybudovat řetězce a nikoliv vytvořit spoustu odlišných seznamů. Chceme mít jeden seznam, který má spoustu uzlů v něm, ne banda seznamů s jedním uzlem. Takže můžeme nejen udržet pomocí Vytvořit Funkce jsme definovali dříve, teď jsme chtějí vložit do Seznam, který již existuje. 

Takže tomto případě, jdeme předat dva argumenty, ukazatel na hlavě, který spojový seznam, který chceme přidat. Opět platí, že je důvod, proč je to tak důležité, že jsme vždy sledovat to, protože je to jediný způsob, jak skutečně muset odkazovat se na celý seznam je jen tím, že ukazatel na první prvek. Takže chceme předat v ukazatel na tento první prvek, a bez ohledu na hodnotu, kterou chcete přidat do seznamu. A nakonec tato funkce bude vrátí ukazatel na nového šéfa propojeného seznamu. 

Jaké jsou kroky zde jedná? No, stejně jako u vytvářet, musíme dynamicky přidělovat prostor pro nový uzel, a zkontrolujte, jisti, že nemáme dostatek paměti, znovu, proto, že jsme pomocí malloc. Pak chceme naplnit a vložte uzlu, tak dal číslo, bez ohledu val je, do uzlu. Chceme vložit uzel na začátek Google seznamu. 

Tam je důvod, proč jsem to chceš udělat, a to může být stojí za sekundu pozastavit video zde, a přemýšlet o tom, proč bych chtěl vložit na začátku propojenou Seznam. Opět jsem se zmínil dříve, že to opravdu není jedno, jestli se nám to uchovat v jakémkoli pořádek, takže možná je to stopa. A jsi viděl, co by se stalo, kdybychom Chtěl to-- nebo jen na vteřinu Před když jsme jeli pomocí vyhledávání vám mohl vidět, co by mohlo se stalo, kdybychom se snažili pro vložení na konec seznamu. Protože my nemají ukazatel na konec seznamu. 

Takže důvod, proč bych chtěl pro vložení na začátku, je proto, že jsem to udělat okamžitě. Mám ukazatel na začátku, a uvidíme to v vizuální ve vteřině. Ale pokud chci vložit na konec, Musím začít od začátku, přejít celou cestu až do konec, a poté jej přidají. Takže to by znamenalo, že vložením na konec seznamu stala by se o n provoz, se vrací k naší diskusi o výpočetní složitost. To by se stát o n provozu, kde i seznam dostal větší a větší, a větší, bude to čím dál obtížnější křižovat něco Na konci. Ale je to vždy opravdu snadné připínáček něco na začátku, jste vždy na začátku. 

A uvidíme opět vizuální tohoto. A pak jednou jsme skončili, jakmile jsme vložil nový uzel, Chceme se vrátit náš ukazatel nový šéf propojeného seznamu, který od té doby jsme vkládání u začátek, bude skutečně ukazatel na uzlu jsme právě vytvořené. Pojďme si to představit, protože si myslím, že to pomůže. 

Tak tady je náš seznam, skládá se z čtyři prvky, uzel obsahující 15, což ukazuje na uzel obsahující 9, který poukazuje na uzlu, který obsahuje 13, což ukazuje na uzel obsahující 10, který má null ukazatel pro svou další ukazatel tak to je konec seznamu. Takže chceme vložit nový uzel s hodnotou 12 na začátku tohoto seznam, co budeme dělat? No, v první jsme malloc prostor pro uzel, a pak jsme dali 12 tam. 

Takže teď jsme se dosáhne bod rozhodnutí, že jo? Máme pár ukazatele, které jsme mohli pohyb, který bychom měli přesunout jako první? Měli bychom udělat 12 přejděte na Nový šéf list-- nebo promiňte, bychom měli 12 poukazují na staré čele seznamu? Nebo bychom měli říci, že Seznam nyní začíná na 12. Tam je rozdíl tam, a my se podíváme na to, co se děje s oběma v druhém. 

Ale toto vede k skvělé téma pro postranním panelu což je, že jeden z nejkomplikovanější věci s spojových seznamů je uspořádat ukazatele ve správném pořadí. Pokud se pohybovat věcmi mimo provoz, můžete skončit nechtěně orphaning zbytek seznamu. A tady je příklad toho. Tak pojďme s myšlenkou of-- No, my jsme právě vytvořili 12. Víme, že 12 bude nový šéf seznamu, a tak proč ne my jen přesunout ukazatel seznam tam bodu. 

OK, tak to je dobře. Takže nyní kde dělá 12 další bod? Myslím, vizuálně vidíme že to bude ukazovat na 15, jako lidé, je to opravdu jasné, k nám. Jak počítač ví? Nemáme nic ukázal na 15 už, že jo? 

Jsme ztratili schopnost se odkazovat na 15. Nemůžeme říci, nový šipku vedle rovná něco, nic tam není. Ve skutečnosti jsme se osiřelý zbytek seznamu Tím máme náhodně zlomený řetěz. A my rozhodně nechceme dělat. 

Takže pojďme zpět a zkuste to znovu. Možná, že správná věc je stanovit další ukazatele 12 je na staré čele seznamu první, pak se můžeme přesunout na seznam u konce. A ve skutečnosti, že je správné pořadí, že my je třeba dodržovat, když jsme pracuje s jednotlivě propojeného seznamu. Vždy chceme připojit nový prvek do seznamu, Než jsme se tento druh důležitým krokem změny kde v čele seznamu je Google. Opět platí, že je to tak zásadní věc, Nechceme ztratit přehled o tom. 

Proto chceme, aby se ujistil, že vše se připoutal spolu, Než jsme se přesunout tento ukazatel. A tak by to bylo správné pořadí, který je pro připojení 12 do seznamu, pak říkají, že seznam začíná 12. Pokud se nám řekl, že seznam začíná na 12 a pak se pokusil připojení 12 do seznamu, jsme již viděli, co se stane. Ztrácíme seznamu omylem. 

OK, takže ještě jedna věc, o čem mluvit. Co když chceme zbavit celý spojený seznam najednou? Opět jsme mallocing všechno tento prostor, a tak jsme třeba jej uvolnit, když budeme hotovi. Takže nyní chceme smazat celý provázaný seznam. No, co chceme dělat? 

Jestliže jsme dosáhli ukazatele null, my chtějí zastavit, jinak, stačí smazat zbytek seznamu a pak mě osvobodil. Odstraňte zbytek seznamu, a pak uvolnit aktuální uzel. Co to zní jako, Jakou technikou máme povídali o dříve Zní to jako? Odstranit všichni ostatní, pak vrátit a odstranit mě. 

To je rekurze, jsme učinil problém o něco menší, říkáme smazat každého jiného, ​​pak můžete mě odstranit. A dále po silnici, která uzel řekne, odstranit všechny ostatní. Ale nakonec se dostaneme k místo, kde je seznam null, a to je naše základna případ. 

Takže pojďme se podívat na to, a jak to může fungovat. Tak tady je náš seznam, je to stejné Seznam právě jsme mluvili o, a je tu kroky. Je tu hodně textu tady, ale Doufejme, že vizualizace pomůže. 

Tak jsme have-- a také jsem vytáhl up našeho stack frames ilustrace z našeho videa na volání komíny, a doufejme, že to všechno společně vám ukáže, co se děje. Tak tady je náš pseudokód kód. Pokud dojdeme null ukazatel, zastavit, jinak, odstraní zbytek seznamu, pak uvolnění aktuální uzel. Takže teď, list-- ukazatel, že jsme předáním zničit body do 12 let. 12 není ukazatele null, takže jsme chystá odstranit zbytek seznamu. 

Co vymazání Zbytek z nás zapojit? No, to znamená, že dodávání zavolat zničit, řekl že 15 let je na začátku Zbytek seznamu chceme zničit. A tak se výzva ke zničení 12 je v jistém smyslu v pořadí. Je to zmrazené tam a čekal, zavolat zničit 15, dokončit svou práci. 

No, 15 není nulový ukazatel, a takže to bude říkat, v pořádku, dobře, odstraňte zbytek seznamu. Zbytek seznamu začíná 9, a tak jsme si jen počkejte, až se odstranit vše, co věci, pak se vrátit a odstranit mě. No 9 to bude říkat, no, Nejsem nulový ukazatel, takže ostatní vymažte seznam zde. A tak se snaží a zničit 13. 13 říká, já nejsem nulový ukazatel, totéž, to projde kolem babku. 10 není ukazatele null, 10 obsahuje ukazatele null, ale 10 není sám null ukazatel právě teď, a tak předá dolar příliš. 

A nyní seznam body tam, ho Opravdu by chtěl poukázat na some-- kdybych měla více prostoru v obraze, že by chtěl poukázat na nějaký náhodný vesmíru že nevíme, co to je. To je nulový ukazatel ačkoli, seznam je doslova nyní nastaven, že je to hodnota null. Je to ukázal hned v té červeného pole. Dosáhli jsme ukazatele null, takže můžeme zastavit, a my jsme udělali. 

A tak, že rám je fialová now-- at the Vrchol stack-- to je aktivní rám, ale je to hotovo. Jestliže jsme dosáhli nulový ukazatel, zastavit. Nechceme dělat nic, my nemůže uvolnit ukazatele null, jsme neměli malloc jakýkoli prostor, a tak jsme hotovi. Takže funkce rámu je zničena, a my jsme resume-- jsme tam, kde jsme opustili off s příští nejvyšší, což Je to tmavě modrý rámeček zde. Tak jsme vyzvednout přesně tam, kde jsme skončili. Vypouští jsme zbytku Seznam již, takže teď jsme chystá uvolnit aktuální uzly. Takže teď se můžeme osvobodit tento uzel, a teď jsme došli na konec funkce. A tak, že funkce rám je zničena, a my vyzvednout na světle modrou. 

Tak to says-- už jsem done-- vypustit zbytek seznamu, tak osvobodí aktuální uzel. A teď je žlutý rámeček zpátky na vrcholu zásobníku. A tak jak vidíte, jsme nyní ničí seznam zprava doleva. 

Co by se stalo, i když, pokud jsme dělali věci špatně? Stejně jako když jsme se pokoušeli přidat prvek. Pokud bychom zpackal řetěz, pokud jsme se nepřipojili ukazatele ve správném pořadí, kdybychom jen osvobodil první prvek, pokud jsme právě propuštěny vedoucí seznamu, teď jsme nemají žádný způsob, jak se odkazovat na zbytek seznamu. A tak budeme mít osiřelé všechno, měli bychom to, co je volal k nevracení paměti. Pokud si vzpomínáte z našeho videa dynamické přidělování paměti, to není moc dobrá věc. 

Tak jak jsem řekl, že jsou několik operací že musíme použít k práci s spojový seznam efektivně. A možná jste si všimli jsem vynechat jeden, smazání jednoho prvku z propojeného Seznam. Důvod, proč jsem to udělal Je to vlastně druh ošidné přemýšlet o tom, jak odstranit jediný prvek z singly spojový seznam. Musíme být schopni přeskočit něco v seznamu, který znamená, že jsme si na point-- my chcete smazat tuto node-- ale aby se to dělá tak, abychom neztratí žádné informace, musíme spojit to uzel sem, sem. 

Tak jsem to udělal špatně nejspíš z vizuálního hlediska. Takže jsme na začátku našeho seznam, jsme vyřizováno, chceme smazat tento uzel. Pokud bychom prostě odstranit, jsme zlomený řetěz. Tento uzel tady se vztahuje na všechno ostatní, že obsahuje řetězec od tady na ven. 

Takže to, co musíme udělat skutečně poté, co se dostaneme do tohoto bodu, je musíme udělat krok zpět jeden, a připojení tohoto uzlu do tohoto uzlu, takže se pak můžeme smazat ten uprostřed. Ale jednotlivě propojené seznamy ne poskytují nám způsob, jak jít zpět. Takže potřebujeme buď udržet dva ukazatele, a přesunout je druh off kroku, jeden za ostatní, jak jsme jít, nebo dostat do bodu, a pak poslat další ukazatel přes. A jak můžete vidět, to může dostat trochu chaotický. Naštěstí, máme Další způsob, jak vyřešit to, když mluvíme o dvojnásobně spojových seznamů. 

Jsem Doug Lloyd, je to CS50.