Podcast o Spojkový zoznam

Kapitoly

Úvod do zákulisia playlistov

Uzly a ukazovatele: Stavebné kamene

Tri príchute spojkových zoznamov

Kúzla s vkladaním a mazaním

Spojkový zoznam verzus pole

Bežné chyby a ako sa im vyhnúť

Zhrnutie a záver

Přepis

Jakub: Lenka, poznáš ten pocit, keď počúvaš hudbu a preskakuješ pesničky? Klikneš na 'ďalšia', potom znova na 'ďalšia'... a potom si povieš, počkaj, tá predtým bola super! A klikneš na 'predchádzajúca'.

Lenka: Jasné, robím to stále. Prečo sa pýtaš?

Jakub: Pretože presne táto mechanika, to jednoduché preskakovanie dopredu a dozadu v playliste, je dokonalý príklad toho, o čom sa dnes budeme baviť. Je to motor, ktorý to celé poháňa.

Lenka: Áno! A tým motorom sú spojkové zoznamy. Možno to znie technicky, ale je to oveľa intuitívnejšie, ako si mnohí myslia.

Jakub: Počúvate Studyfi Podcast, kde robíme zložité témy jednoduchými. Tak poďme na to, Lenka, čo je to ten spojkový zoznam?

Lenka: Predstav si to ako reťaz. Každé očko reťaze je to, čo voláme 'uzol'. A v každom tom uzle sú dve veci: samotné dáta – v našom prípade pesnička – a potom niečo, čo sa volá 'ukazovateľ'.

Jakub: Ukazovateľ? To znie ako nejaká indícia v honbe za pokladom.

Lenka: To je perfektné prirovnanie! Presne tak to je. Ukazovateľ je v podstate len adresa, ktorá ti povie, kde v pamäti nájdeš ďalší uzol, teda ďalšie očko reťaze.

Jakub: Takže prvky nie sú uložené pekne vedľa seba v jednom rade ako v poli?

Lenka: Vôbec nie. Môžu byť rozhádzané po celej pamäti počítača. Jediné, čo ich spája, je táto reťaz ukazovateľov. Celý zoznam drží pohromade len tým, že poznáme adresu prvého uzla, takzvanej 'hlavy'.

Jakub: Chápem. Takže hlava je začiatok a od nej sa pomocou tých indícií, teda ukazovateľov, dostanem k ďalším prvkom, až kým nenarazím na koniec.

Lenka: Presne tak. A koniec spoznáš podľa toho, že ukazovateľ posledného uzla neukazuje nikam. Má špeciálnu hodnotu, zvyčajne NULL. To je signál: 'Stop, ďalej už nič nie je'.

Jakub: Dobre, takže máme reťaz. Ale existuje len jeden typ takejto reťaze?

Lenka: Kdeže. Základný typ je 'jednosmerný spojkový zoznam'. Tam sa môžeš pohybovať len jedným smerom, od hlavy ku koncu. Ako keď ideš po jednosmerke.

Jakub: A keď sa chcem vrátiť? Ako v tom playliste, keď chcem predošlú pesničku?

Lenka: A tu prichádza na scénu 'obojsmerný spojkový zoznam'! Ten je oveľa šikovnejší. Každý uzol má totiž dva ukazovatele.

Jakub: Dva? Na čo?

Lenka: Jeden ukazuje na nasledujúci prvok, presne ako predtým. Ale ten druhý ukazuje na predchádzajúci prvok. Vďaka tomu sa môžeš po zozname pohybovať dopredu aj dozadu. Presne ako v tvojom playliste!

Jakub: Aha! Preto to funguje tak hladko. A je ešte nejaký ďalší typ? Nejaký pre fajnšmekrov?

Lenka: Je! Volá sa 'cyklický spojkový zoznam'. Tam posledný prvok neukazuje na NULL, ale... hádaj kam?

Jakub: Žeby... naspäť na prvý?

Lenka: Presne! Vytvorí to kruh. Je to užitočné pre veci, ktoré sa majú opakovať stále dookola, napríklad rotujúce animácie alebo správa úloh v operačnom systéme.

Jakub: Nekonečný playlist! To by sa mi páčilo.

Lenka: No, poďme teraz na tie kúzla. Ako do takej reťaze niečo pridáme? Najjednoduchšie je vkladanie na začiatok.

Jakub: Takže pred prvú pesničku v playliste.

Lenka: Áno. Je to extrémne rýchle, má to zložitosť O(1), čiže konštantný čas. Jednoducho vytvoríš nový uzol, povieš mu, aby jeho ukazovateľ 'next' ukazoval na doterajšiu hlavu, a potom vyhlásiš tento nový uzol za novú hlavu. Dva-tri kroky a je to.

Jakub: To znie super jednoducho. A čo keď chcem vložiť niečo doprostred? Povedzme za tretiu pesničku.

Lenka: Tam už je to trochu zložitejšie. To má zložitosť O(n), pretože najprv musíš ten tretí uzol nájsť. Musíš prejsť zoznamom od začiatku. Keď ho nájdeš, musíš prepojiť ukazovatele.

Jakub: Ako to myslíš, 'prepojiť'?

Lenka: Predstav si, že vkladáš uzol 'B' medzi 'A' a 'C'. Musíš zmeniť štyri veci v obojsmernom zozname: Ukazovateľ 'next' z 'A' musí ukazovať na 'B'. Ukazovateľ 'prev' z 'C' musí ukazovať na 'B'. A potom nový uzol 'B' musí ukazovať svojím 'next' na 'C' a svojím 'prev' na 'A'.

Jakub: Uf, to je celkom dosť žonglovania s ukazovateľmi.

Lenka: Je, ale stále je to efektívnejšie ako v poli! V poli by si musel všetky prvky od 'C' ďalej fyzicky posunúť o jednu pozíciu, čo je pri veľkom poli extrémne pomalé.

Jakub: A mazanie funguje podobne, však? Nájsť prvok a potom len prehodiť ukazovatele tak, aby ho 'obchádzali'.

Lenka: Presne tak. Pri mazaní zo stredu nájdeš susedov a prepojíš ich priamo medzi sebou. Vymazaný uzol zostane visieť bokom a my ho potom musíme uvoľniť z pamäte.

Jakub: Dobre, stále mi to vŕta v hlave. Kedy si mám vybrať spojkový zoznam a kedy staré dobré pole? Zhrňme si to.

Lenka: Super nápad. Takže, pole je ako panelák s očíslovanými bytmi. Ak chceš ísť do bytu číslo 50, ideš tam priamo. To je prístup za O(1). Rýchly ako blesk.

Jakub: A spojkový zoznam?

Lenka: Spojkový zoznam je ako tá honba za pokladom. Ak chceš nájsť piaty poklad, musíš nájsť prvý, ktorý ti dá indíciu k druhému, ten k tretiemu a tak ďalej. Trvá to dlhšie, je to prístup za O(n).

Jakub: Takže ak potrebujem často pristupovať k prvkom podľa indexu, pole je jasný víťaz.

Lenka: Jednoznačne. Ale teraz si predstav, že chceš v tom paneláku pridať nový byt medzi tretím a štvrtým poschodím.

Jakub: To nejde! Musel by som zbúrať a prestavať polovicu budovy.

Lenka: Presne! A to je operácia O(n) v poli, lebo musíš všetko posúvať. Zatiaľ čo v spojkovom zozname je vkladanie a mazanie, najmä na začiatku, super rýchle. Stačí prehodiť pár ukazovateľov. To je obrovská výhoda, ak nevieš dopredu, koľko prvkov budeš mať, a často ich pridávaš a odoberáš.

Jakub: A čo pamäť? Ktorý je úspornejší?

Lenka: Pole je úspornejšie, pretože ukladá len samotné dáta. Spojkový zoznam má vyššiu pamäťovú réžiu, lebo každý uzol si okrem dát nesie aj jeden alebo dva ukazovatele navyše.

Jakub: Dobre, viem si predstaviť, že pri tom žonglovaní s ukazovateľmi sa dá veľa vecí pokaziť. Čo sú najčastejšie chyby?

Lenka: Absolútna klasika je zabudnúť aktualizovať nejaký ukazovateľ. Napríklad pri vkladaní do obojsmerného zoznamu zmeníš tri zo štyroch a na ten štvrtý zabudneš. Zrazu ti zoznam prestane fungovať jedným smerom a hľadaj chybu.

Jakub: To znie ako nočná mora pri ladení.

Lenka: To aj je. Druhá častá chyba je pokúsiť sa získať dáta z ukazovateľa, ktorý je NULL. To je ako snažiť sa otvoriť dvere, ktoré neexistujú. Program ti okamžite spadne s chybou NullPointerException alebo niečím podobným.

Jakub: Čiže vždy si treba skontrolovať, či ukazovateľ niekam ukazuje, predtým, ako ho použijem.

Lenka: Vždy! A posledná vec, hlavne v jazykoch ako C++, sú pamäťové úniky. Ak uzol zo zoznamu odstrániš, ale zabudneš uvoľniť pamäť, ktorú zaberal, ten uzol tam zostane ako duch. Postupne ti takíto duchovia zaplnia celú pamäť.

Jakub: Dobre, takže pozor na duchov v pamäti. Rozumiem.

Lenka: Presne tak. Vizualizácia a kreslenie si toho, ako sa ukazovatele menia, je naozaj najlepší spôsob, ako tomu predísť a pochopiť to.

Jakub: Super. Takže, aby sme to zosumarizovali. Spojkový zoznam je dynamická dátová štruktúra, kde sú prvky prepojené ukazovateľmi, nie sú uložené vedľa seba. Je to kráľ, keď potrebujeme často vkladať a mazať prvky.

Lenka: Áno. Na druhej strane, je pomalší, ak potrebujeme pristupovať k prvkom podľa indexu – na to je lepšie pole. A musíme si dávať veľký pozor na správne manažovanie ukazovateľov.

Jakub: Skvelé! Myslím, že teraz každý, kto si bude prepínať pesničky v playliste, si spomenie na uzly a ukazovatele.

Lenka: Dúfam, že áno! Je to naozaj základný koncept, ktorý otvára dvere k mnohým ďalším zložitým štruktúram v informatike.

Jakub: Lenka, ďakujem ti veľmi pekne za skvelé vysvetlenie.

Lenka: Aj ja ďakujem, Jakub. A vám, milí poslucháči, držíme palce pri štúdiu!

Jakub: Majte sa!