[Powered by Google Translate] V programování, často potřebujeme reprezentovat seznamy hodnot, například názvy studentů v sekci nebo jejich skóre na poslední kvízu. 

V jazyce C, prohlásila pole mohou být použity uložit seznamy. Je to snadné vyjmenovat prvky seznamu uloženy v poli, a pokud budete potřebovat pro přístup k nebo upravit Ith prvek seznamu pro nějaký svévolný index I, který může být proveden v konstantním čase, ale pole mají nevýhody. 

Když jsme je deklarovat, že jsme povinni říci up front, jak velké jsou, že je, kolik prvků, které mohou uložit a jak velké tyto prvky jsou, která je určena jejich typu. Například, int arr (10) lze uložit 10 položek že jsou o velikosti typu int. 

Nemůžeme změnit celou řadu jeho velikost po vyhlášení. Musíme vytvořit nové pole, pokud chceme uložit více prvků. Důvodem toto omezení existuje, je, že naše Program ukládá celou řadu jako souvislý kus paměti. Řekněme to je vyrovnávací paměť, kde se uloží v našem poli. Tam by mohlo být jiné proměnné Nachází se hned vedle pole v paměti, takže nemůžeme jen aby pole větší. 

Někdy jsme chtěli obchodovat Array je rychlý přístup k datům rychlostí o trochu více flexibility. Zadejte spojový seznam, další základní údaje struktura nemusíte být obeznámeni s. Na vysoké úrovni, spojový seznam ukládá data v pořadí uzlů , které jsou vzájemně propojeny s odkazy, Odtud název "spojový seznam." Jak uvidíme, tento rozdíl v designu vede k různým výhodám a nevýhodám než pole. 

Zde je nějaký kód C pro velmi jednoduché propojeného seznamu celých čísel. Můžete vidět, že jsme zástupci každý uzel v seznamu jako struct, který obsahuje 2 věci, číslo uložit tzv. "val" a odkaz na další uzel v seznamu které představují jako ukazatel s názvem "Další." Tímto způsobem, lze sledovat celý seznam pouze s jedním ukazatel na uzel 1st, a pak můžeme sledovat další ukazatele na druhé uzlu, na 3. uzlu, na 4. uzlu, a tak dále, dokud se na konec seznamu. 

Ty by mohly být schopni vidět 1 výhodu to má přes statické pole struktury - s propojeného seznamu, nepotřebujeme velký kus paměti dohromady. 1. uzel seznamu by mohl žít na tomto místě v paměti, a 2. uzel by mohl být po celou cestu sem. Můžeme dostat do všech uzlů bez ohledu na to, kde v paměti jsou, protože začíná v uzlu 1st, každý uzel příští ukazatel nám říká přesně, kam jít dál. 

Navíc, nemáme říkat dopředu jak velký spojový seznam bude stejným způsobem jako my se statickými poli, protože můžeme držet přidání uzlů do seznamu jak dlouho jak tam je prostor někde v paměti pro nové uzly. Proto, propojené seznamy snadno změnit velikost dynamicky. Řekni, později v programu musíme přidat další uzly do našeho seznamu. Chcete-li vložit nový uzel do našeho seznamu za běhu, všechno, co musíme udělat, je alokovat paměť pro tento uzel, plop v datové hodnoty, a pak na místo, kde chceme úpravou vhodné ukazatele. 

Například, pokud chceme umístit uzel mezi 2. a 3. uzly seznamu,  bychom neměli přesunout 2. nebo 3. uzly vůbec. Řekněme, že jsme vložením tuto červenou uzel. Vše budeme muset udělat, je nastavit nový uzel je další ukazatel poukázat na 3. uzlu a potom přepojit druhé uzlu je další ukazatel upozornit na náš nový uzel. Takže, můžeme měnit velikost své seznamy za běhu protože náš počítač nespoléhá na indexování, ale spíše na propojení s ukazateli jejich uložení. 

Nicméně, nevýhodou spojené seznamy je skutečnost, že na rozdíl od statické pole, Počítač nemůže jen tak skočit do středu seznamu. Vzhledem k tomu, že počítač má navštívit každý uzel v propojeném seznamu se dostat na další, to bude trvat déle najít určitý uzel , než by se v poli. Přejít celý seznam trvá dlouho úměrná k délce seznamu, nebo O (n) v asymptotické notaci. V průměru, dosažení libovolného uzlu bere rovněž časově proporcionální k n.. 

Nyní, pojďme vlastně napsat nějaký kód , který pracuje s lineárními seznamy. Řekněme, že chceme propojeného seznamu celých čísel. Můžeme reprezentovat uzel v našem seznamu znovu jako struct s 2 polí, celočíselná hodnota tzv. "val" a další ukazatel na další uzel seznamu. No, vypadá docela jednoduché. 

Řekněme, že chcete napsat funkci který překročí seznamu a vytiskne Hodnota uložená v posledním uzlu seznamu. No, to znamená, že budeme muset přejít všechny uzly v seznamu najít ten poslední, ale protože nejsme přidání nebo cokoli smazali, nechceme měnit vnitřní struktura dalších ukazatelů v seznamu. 

Takže, budeme potřebovat ukazatel speciálně pro průchod které budeme nazývat "prolézací modul." To bude procházet přes všechny prvky seznamu podle pokynů řetězce dalších ukazatelů. Vše máme uloženy, je ukazatel na uzel 1st, nebo "hlava" ze seznamu. Head poukazuje na 1. uzlu. Je to typu pointer-to-uzlu. 

Chcete-li získat aktuální první uzel v seznamu, musíme dereference tento ukazatel, ale před tím, než může dereference to, musíme zkontrolovat v případě, že ukazatel je null první. Pokud je to null, seznam je prázdný, a my bychom měli vytisknout zprávu, že, protože seznam je prázdný, není poslední uzel. Ale řekněme, že seznam není prázdný. Pokud tomu tak není, pak bychom měli procházet celý seznam dokud se na poslední uzel seznamu, a jak můžeme říct, jestli se díváme na poslední uzel v seznamu? 

No, pokud uzel je další ukazatel je null, my víme, že jsme na konci od posledního další ukazatel by neměl další uzel v seznamu, aby ukazoval na. Je dobrým zvykem vždy poslední uzel je další ukazatel inicializován null mít standardizovanou vlastnost, která upozorní nás, když jsme došli na konec seznamu. 

Takže, pokud crawler → další je null, nezapomeňte, že šipka syntaxe je zkratka pro dereferencing ukazatel na struct, pak přístup její další pole odpovídá nepříjemné: (* Crawler). Další. Jakmile jsme našli poslední uzel, chceme tisknout prolézacího → val, hodnota v aktuálním uzlu které známe, je poslední. V opačném případě, když jsme ještě na poslední uzlu v seznamu, musíme přesunout na další uzel v seznamu a zkontrolujte, zda je to poslední. Chcete-li to, jen jsme nastavili pásové ukazatel bodu za aktuálním uzlem je další hodnoty, to znamená, že další uzel v seznamu. To se provádí nastavením crawler = crawler → další. Pak se tento proces opakovat, se smyčkou například, dokud nenajdeme poslední uzel. Tak například, jestliže pásový ukazoval na hlavu, jsme se vydali prolézací modul, aby ukazoval na pásový → Další, který je stejný jako další oblasti prvního uzlu. Takže, teď náš prohledávač ukazuje na 2. uzlu, a opět, opakujeme to se smyčkou, až jsme zjistili, poslední uzel, který je, kde uzlu další ukazatel ukazuje na null. A tady to máme, jsme našli poslední uzel v seznamu, a vytisknout svou hodnotu, stačí použít pásový → val. 

Pojezdu není tak špatné, ale co o vkládání? Řekněme, že chceme vložit celé číslo do 4. místě v celé číslo seznamu. To je mezi současnými 3. a 4. uzlů. Opět musíme procházet seznam jen dostat do 3. prvek, jeden jsme vkládání po. Takže, jsme vytvořit prolézacího ukazatel znovu procházet seznam, zkontrolujte, zda naše hlava ukazatel je null, a pokud tomu tak není, přejděte náš prohledávač ukazatel na hlavním uzlu. Takže, jsme na 1. prvek. Musíme jít vpřed 2 více prvků, než můžeme vložit, takže můžeme použít pro smyčce int i = 1; i <3; i + + a v každém opakování smyčky, Rozšíření našich pásový ukazatel vpřed o 1 uzel zkontrolovat, zda je aktuální uzel je další pole null, a je-li to není, přesunout naše pásový ukazatel na další uzel nastavením je roven aktuálnímu uzlu příštího ukazatel. Takže, protože naše cyklu for říká k tomu, že dvakrát, jsme dosáhli 3. uzel, a poté, co náš prohledávač ukazatel dosáhl uzel po které chceme vložit náš nový integer, Jak jsme vlastně se liší vkládání? 

No, náš nový integer musí být vložen do seznamu jako součást vlastního uzlu struct, , protože to je ve skutečnosti sekvence uzlů. Takže, pojďme se nový ukazatel na uzel tzv. "new_node," a nastavte ji upozornit na paměti, že jsme nyní přidělit na haldě pro uzel sám, a kolik paměti potřebujeme přidělit? No, o velikosti uzlu, a chceme nastavit svůj val pole na celé číslo, které chceme vložit. Řekněme, 6. Nyní, uzel obsahuje náš celočíselnou hodnotu. Je také dobrým zvykem inicializovat nový uzel je další pole bodu na hodnotu null, ale co teď? 

Máme změnit vnitřní strukturu seznamu a další ukazatele obsažené v seznamu je existující 3. a 4. uzly. Vzhledem k tomu, další ukazatele určují pořadí v seznamu, a od té doby jsme vložením náš nový uzel přímo do středu seznamu, to může být trochu složitější. To je proto, pamatujte, náš počítač zná jen umístění uzlů v seznamu protože z dalších ukazatelů uložených v předchozích uzlů. Takže, pokud se někdy ztratil některé z těchto lokalit, říci změnou jednoho z následujících ukazatelů v našem seznamu, Například, že jsme změnily od 3. uzlu vedle pole poukázat na některé uzlu sem. Byli bychom smůlu, protože bychom tušení, kde najít zbytek seznamu, a to je zřejmě opravdu špatné. Takže, musíme být opravdu pozor na jejich pořadí , ve kterém jsme se manipulovat naše další ukazatele během zavádění. 

Takže, zjednodušit to, řekněme, že naše první 4 uzly se nazývá A, B, C a D, s šipkami představující řetěz ukazatelů která spojují uzly. Takže, je nutné vložit náš nový uzel mezi uzly C a D. Je důležité, aby to ve správném pořadí, a já vám ukážu, proč. 

Pojďme se podívat na špatně se to udělat jako první. Hele, my víme, že nový uzel má přijít hned po C, takže se pojďme nastavit C je další ukazatel poukázat na new_node. Dobře, zdá se v pořádku, jen musíme dokončit již nyní Díky nového uzlu je další ukazatel bod D, Ale počkejte, jak můžeme udělat, že? Jediná věc, která by nám mohl říct, kde D je, byla další ukazatel dříve uložené v C, ale my prostě přepsal tento ukazatel přejděte na nový uzel, takže již nemáme ponětí, kde D je v paměti, a my jsme ztratili zbytek seznamu. Vůbec dobré. 

Tak, jak to uděláme toto právo? Za prvé, bodu nového uzlu je další ukazatel na D. Nyní, jak nový uzel je a C je další ukazatele směřují na stejný uzel, D, ale to je v pořádku. Nyní můžeme bod C je další ukazatel na nový uzel. Takže jsme udělali to bez ztráty dat. V kódu, C je aktuální uzel že traversal ukazatel prolézací modul ukazuje na, a D je reprezentován uzlem na který ukazuje aktuální uzlu následujícího pole, nebo pásovém podvozku → další. Takže, nejprve nastavte nový uzel je další ukazatel poukázat na pásový → Další, stejným způsobem jsme si řekli, new_node příští ukazatel by měl poukazují na D na obrázku. Pak můžeme nastavit aktuální uzel je další ukazatel do našeho nového uzlu, stejně jako jsme museli čekat, až bodu C na new_node ve výkresu. Nyní je všechno v pořádku, a my jsme neztratili přehled o veškerých údajů, a my jsme byli schopni jen držet náš nový uzel ve středu seznamu bez přestavět celou věc, nebo dokonce posunutí všechny prvky způsob, jakým by se museli s pevnou délkou pole. 

Takže, propojené seznamy jsou základní, ale důležité, dynamická datová struktura které mají výhody i nevýhody ve srovnání s poli a jiných datových struktur, a jak je tomu často v informatice, je důležité vědět, kdy použít každý nástroj, takže si můžete vybrat ten správný nástroj na správné místo. 

Pro více praxe, zkuste napsat funkce odstranění uzlů z propojeného seznamu - nezapomeňte dávat pozor na pořadí, ve kterém jste změny uspořádání vaše další ukazatele, aby zajistily, že neztratíte kus svého seznamu - nebo funkci počítat uzly v propojeném seznamu, nebo legrace jeden, obrátit pořadí všech uzlů v propojeném seznamu. 

Jmenuji se Jackson Steinkamp, ​​je to CS50.