Podcast na Spojový seznam

Kapitoly

Lovci pokladů a seznamy skladeb

Uzel a ukazatel: Stavební kameny

Tři příchutě seznamů

Kouzlo vkládání a mazání

Achillova pata: Přístup k prvkům

Běžné pasti a jak se jim vyhnout

Shrnutí a rozloučení

Přepis

Ondřej: Představ si, že organizuješ obrovskou honbu za pokladem. Máš sto stanovišť a indicie jsou napsané na dlouhém svitku papíru, jedna pod druhou. Jenže pak zjistíš, že jsi zapomněl na jednu indicii přesně uprostřed. Co teď? Musíš přepsat padesát indicií, jen abys tam vmáčkl jednu novou.

Tereza: Přesně tak. A teď si představ jiný způsob. Každá indicie je na samostatné kartičce a na konci každé je šipka, která ukazuje, kde najdeš tu další. Když chceš přidat novou, prostě vezmeš novou kartičku, napíšeš na ni indicii a jen změníš dvě šipky, aby zapadla do řetězu. Nic nemusíš přepisovat.

Ondřej: To zní o dost chytřeji. A přesně tenhle chytrý princip používá datová struktura, o které si dnes budeme povídat. Posloucháte Studyfi Podcast.

Tereza: Přesně tak, Ondřeji. Téhle struktuře říkáme spojový seznam. A ta tvoje honba za pokladem je dokonalá metafora. Na rozdíl od pole, kde jsou data uložená v paměti hezky vedle sebe jako na tom svitku, u spojového seznamu můžou být rozházená kdekoliv.

Ondřej: A drží pohromadě jen díky těm šipkám? Jak se jim říká v informatice? Předpokládám, že ne „šipky“.

Tereza: Dobrá poznámka. Těm šipkám říkáme **ukazatele** a každé té kartičce s indicií se říká **uzel**. Každý uzel má dvě části: datovou část – to je ta naše indicie nebo jakákoliv jiná informace – a ukazatel, což je v podstatě adresa dalšího uzlu v řadě.

Ondřej: Takže uzel je jako balíček, co obsahuje data a adresu dalšího balíčku. A jak vím, kde začít? Kde je ta první kartička?

Tereza: Skvělá otázka. Celý seznam začíná speciálním ukazatelem na první uzel, kterému říkáme **hlava** (head). A ten úplně poslední uzel? Jeho ukazatel neukazuje nikam, má hodnotu NULL. To je signál, že honba za pokladem, nebo spíš seznam, končí.

Ondřej: Takže je to vlastně datová struktura pro piráty. Hlava, ukazatel na další kus mapy... a na konci NULL místo truhly s pokladem.

Tereza: Přesně! Můžeš si to tak pamatovat. Ale místo pokladu tam může být třeba seznam studentů, historie transakcí nebo playlist písniček.

Ondřej: Dobře, chápu základní princip. Existuje jen jeden typ tohohle „pirátského“ seznamu, nebo je jich víc?

Tereza: Jsou tři hlavní druhy. Ten, co jsme popsali, se jmenuje **jednosměrný spojový seznam**. Můžeš jím procházet jen jedním směrem, od hlavy ke konci. Jako když sleduješ šipky v jednosměrce.

Ondřej: To dává smysl. A ty další?

Tereza: Pak máme **dvousměrný spojový seznam**. Tady má každý uzel nejen ukazatel na následující prvek, ale i na ten předchozí. Je to jako mít na každé kartičce s indicií i šipku zpátky na tu předchozí. Můžeš se tak pohybovat tam i zpět.

Ondřej: K čemu je to dobré? Vypadá to na víc práce s ukazateli.

Tereza: Určitě. Je to trochu složitější na implementaci a zabere to víc paměti. Ale je to neuvěřitelně užitečné. Představ si funkci „zpět“ nebo „vpřed“ v prohlížeči nebo v textovém editoru. To je často implementováno právě pomocí dvousměrného seznamu.

Ondřej: Aha! Takže to není jen akademická věc, ale něco, co používám každý den. A ten třetí typ?

Tereza: Třetí je **kruhový spojový seznam**. Tam poslední uzel neukazuje na NULL, ale zpátky na hlavu seznamu. Vytvoří to kruh, který nemá konec. Perfektní pro aplikace, kde potřebuješ něco neustále opakovat. Třeba playlist na repeat nebo přepínání úloh v operačním systému.

Ondřej: Fajn, teorii máme. Pojďme na praxi. Jak tedy do seznamu něco vložím? Říkal jsi, že je to jednoduché.

Tereza: Je to elegantní. Když chceš vložit prvek na začátek, je to bleskovka. Vytvoříš nový uzel, jeho ukazatel nastavíš na současnou hlavu a pak jen prohlásíš ten nový uzel za novou hlavu. Hotovo. Je to operace s konstantní složitostí, O(1).

Ondřej: Takže nezáleží na tom, jestli má seznam deset prvků nebo deset milionů? Vložení na začátek je vždycky stejně rychlé?

Tereza: Přesně tak. To je obrovská výhoda oproti poli, kde bys musel posunout všechny ostatní prvky. A vložení doprostřed? Najdeš uzel, za který chceš vkládat, a jednoduše „přepojíš“ dva ukazatele. Znovu, žádné masivní přesouvání dat.

Ondřej: A co mazání? Je to podobně jednoduché?

Tereza: Úplně. Smazání prvního prvku je zase O(1) – jen posuneš ukazatel hlavy na druhý prvek. Smazání prvku uprostřed znamená, že ukazatel předchozího uzlu přesměruješ tak, aby „přeskočil“ mazaný uzel a ukazoval na ten následující. Ten mazaný uzel pak prostě zmizí z řetězu.

Ondřej: Zní to skoro jako kouzlo. Jen mávneš ukazatelem a prvek je pryč.

Tereza: V podstatě ano. Ale pozor, má to i stinnou stránku. Zkus hádat jakou.

Ondřej: No... když nemůžu skočit rovnou na padesátou indicii a musím jít od první, tak asi bude problém rychle najít konkrétní prvek, že?

Tereza: Přesně! To je hlavní nevýhoda spojových seznamů. Přístup k prvkům je sekvenční. Pokud chceš pětistý prvek, musíš projít 499 uzlů před ním. To je operace s lineární složitostí, O(n). Čím delší seznam, tím déle to trvá.

Ondřej: Zatímco u pole prostě řeknu „dej mi prvek na indexu 500“ a mám ho hned. To je O(1).

Tereza: Přesně tak. Takže tady máme klíčový kompromis. Chceš rychlé vkládání a mazání? Použij spojový seznam. Potřebuješ bleskový přístup k libovolnému prvku podle indexu? Sáhni po poli.

Ondřej: Takže neexistuje jedna „nejlepší“ datová struktura. Vždycky záleží na tom, co s těmi daty chci dělat.

Tereza: To je zlaté pravidlo programování. Každý nástroj má své ideální použití. Spojový seznam je jako nůž na chleba – skvělý na krájení, ale na šroubování šroubků se nehodí.

Ondřej: Rozumím. A děkuju, že jsi nepoužila metaforu se švýcarským nožem, to by bylo klišé.

Tereza: Snažila jsem se!

Ondřej: Když s tím člověk začíná, na co by si měl dát největší pozor? Jaké jsou typické chyby?

Tereza: První a největší past je ztráta ukazatelů. Když špatně přepojíš ukazatele, může se ti stát, že ztratíš odkaz na celý zbytek seznamu. Ta část paměti pak zůstane obsazená, ale nedostupná. Tomu se říká paměťový únik.

Ondřej: To zní jako digitální bermudský trojúhelník pro data.

Tereza: Docela jo. Další klasika je zapomenout na krajní případy. Co se stane, když je seznam prázdný? Nebo když mažeš poslední prvek? Tvůj kód musí tyto situace ošetřit, jinak spadne s chybou, protože se bude snažit přistoupit k něčemu, co neexistuje, jako je NULL.dalsi.

Ondřej: Takže testovat, testovat, testovat. Hlavně s prázdným seznamem, jedním prvkem a při operacích na začátku a na konci.

Tereza: Přesně. A poslední věc, hlavně v jazycích jako C++, je nutnost manuálně uvolnit paměť po smazaném uzlu. Pokud uzel jen „odpojíte“ ze seznamu, ale paměť neuvolníte, opět vytváříte paměťový únik.

Ondřej: Perfektní, Terezo. Pojďme si to tedy rychle shrnout. Spojový seznam je řetězec uzlů, kde každý uzel obsahuje data a ukazatel na další uzel.

Tereza: Přesně. Jeho hlavní výhodou je dynamická velikost a bleskově rychlé vkládání a mazání prvků na začátku seznamu. To z něj dělá skvělou volbu pro fronty, zásobníky nebo správu úloh.

Ondřej: Na druhou stranu, jeho velkou nevýhodou je pomalý, sekvenční přístup k prvkům. Nemůžeme skočit rovnou na i-tý prvek jako u pole.

Tereza: Přesně tak. A existují různé varianty – jednosměrné, dvousměrné pro pohyb tam i zpět, a kruhové pro cyklické úlohy. Klíčem je vždy vybrat správný nástroj pro daný problém.

Ondřej: Bylo to super srozumitelné, díky moc, Terezo! Doufám, že teď naši posluchači vidí spojové seznamy ne jako strašáka, ale jako elegantní a silný nástroj.

Tereza: Já taky doufám. A pamatujte, nejlepší způsob, jak to pochopit, je si to zkusit naprogramovat. Nebojte se chyb, z těch se učíme nejvíc.

Ondřej: Skvělá rada na závěr. Děkujeme, že jste poslouchali Studyfi Podcast. U slyšenou příště!

Tereza: Na slyšenou!