# Spojkové zoznamy: Podrobný sprievodca Spojkové zoznamy sú jednou zo základných a najdôležitejších dátových štruktúr v informatike. Na rozdiel od polí, ktoré ukladajú prvky v súvislej oblasti pamäte, spojkové zoznamy ukladajú prvky nesúvisle. Každý prvok pritom obsahuje okrem dátovej hodnoty aj odkaz (ukazovateľ) na nasledujúci prvok. Táto flexibilita v usporiadaní pamäte prináša významné výhody pri určitých typoch operácií, ale aj určité nevýhody, ktoré si podrobnejšie rozoberieme. ## Základné pojmy: Uzol a ukazovateľ Srdcom spojkového zoznamu je **uzol**. Každý uzol je samostatný objekt, ktorý typicky obsahuje dve hlavné časti: 1. **Dátová časť:** Obsahuje skutočnú hodnotu alebo informáciu, ktorú chceme uložiť (napríklad celé číslo, reťazec, objekt). Typ dátovej časti závisí od konkrétnej aplikácie. 2. **Ukazovateľ (odkaz) na ďalší uzol:** Toto je pamäťová adresa, ktorá „ukazuje“ na nasledujúci uzol v sekvencii. Ak je uzol posledným prvkom v zozname, jeho ukazovateľ na ďalší uzol má špeciálnu hodnotu, často označovanú ako `NULL` (alebo `nil`), čo signalizuje koniec zoznamu. > **Ukazovateľ** je premenná, ktorá uchováva pamäťovú adresu inej premennej alebo objektu. V kontexte spojkových zoznamov sú ukazovatele kľúčové pre prepojenie uzlov a umožňujú prechádzanie zoznamom. Celý spojkový zoznam je typicky reprezentovaný ukazovateľom na svoj prvý uzol, ktorý sa často nazýva `hlava` (head). Ak je zoznam prázdny, `hlava` má hodnotu `NULL`. Did you know, že koncept spojkových zoznamov bol prvýkrát predstavený v roku 1955 Allenom Newellom, Cliffom Shawom a Herbertom Simonom na účely spracovania symbolov v programovaní, hlavne pre ich programovací jazyk IPL? ## Typy spojkových zoznamov Existuje niekoľko variantov spojkových zoznamov, ktoré sa líšia spôsobom prepojenia uzlov: 1. **Jednosmerný spojkový zoznam (Singly Linked List):** Toto je najjednoduchší typ. Každý uzol obsahuje dátovú hodnotu a ukazovateľ na nasledujúci uzol. Prechádzanie zoznamom je možné len v jednom smere, od začiatku ku koncu. 2. **Obojsmerný spojkový zoznam (Doubly Linked List):** Tento typ je robustnejší. Každý uzol obsahuje dátovú hodnotu a dva ukazovatele: jeden na nasledujúci uzol (`next`) a druhý na predchádzajúci uzol (`prev`). To umožňuje prechádzanie zoznamom v oboch smeroch (dopredu aj dozadu), čo zjednodušuje niektoré operácie, ako je mazanie uzla alebo vkladanie pred konkrétny uzol. Ukazovateľ `prev` prvého uzla a ukazovateľ `next` posledného uzla majú hodnotu `NULL`. 3. **Cyklický spojkový zoznam (Circular Linked List):** V tomto variante ukazovateľ `next` posledného uzla neukazuje na `NULL`, ale na prvý uzol zoznamu. Ak ide o obojsmerný cyklický zoznam, ukazovateľ `prev` prvého uzla ukazuje na posledný uzol. Cyklické zoznamy sú užitočné pre implementáciu kruhových bufferov alebo pre situácie, kde je potrebné neustále prechádzať zoznamom. ## Operácie so spojkovým zoznamom Hlavné operácie, ktoré sa vykonávajú so spojkovými zoznamami, sú vkladanie, mazanie a prístup k prvkom. ### Vkladanie prvkov Vkladanie nového uzla do spojkového zoznamu zahŕňa zmenu ukazovateľov. Časová zložitosť vkladania sa líši v závislosti od miesta vloženia. * **Vkladanie na začiatok ($O(1)$):** Toto je najefektívnejšia operácia vkladania. Nový uzol sa vytvorí, jeho dátová časť sa naplní a jeho ukazovateľ `next` sa nastaví na aktuálnu `hlavu` zoznamu. Následne sa `hlava` zoznamu aktualizuje tak, aby ukazovala na nový uzol. V prípade obojsmerného zoznamu je potrebné aktualizovať aj ukazovateľ `prev` pôvodnej hlavy, aby ukazoval na nový uzol, a ukazovateľ `prev` nového uzla sa nastaví na `NULL`. * Príklad: Máme zoznam $10 \to 20 \to 30$. Chceme vložiť $5$ na začiatok. 1. Vytvoríme nový uzol s hodnotou $5$. Jeho `next` je zatiaľ `NULL`. 2. Nastavíme `novy_uzol.next` na `hlava` (ktorá ukazuje na $10$). 3. Ak je zoznam obojsmerný, nastavíme `hlava.prev` (uzol $10$) na `novy_uzol`. 4. Nastavíme `hlava` na `novy_uzol`.