Shrnutí na Spojový seznam

Spojové seznamy jsou fundamentální lineární datové struktury v informatice, které slouží k efektivnímu ukládání a organizaci dat. Na rozdíl od polí, kde jsou prvky uspořádány v souvislé oblasti paměti, jsou prvky spojového seznamu flexibilně rozmístěny v paměti a propojeny pomocí speciálních odkazů zvaných ukazatele. Tato adaptabilita přináší významné výhody, zejména při dynamických operacích, jako je vkládání a mazání prvků. ## Základní stavební kameny: Uzel a ukazatel Každý prvek spojového seznamu se nazývá **uzel**. Uzel je složen ze dvou hlavních částí: 1. **Datová část:** Obsahuje samotná data, která chceme v seznamu uchovávat (například číslo, text, objekt apod.). 2. **Ukazatel (odkaz):** Obsahuje paměťovou adresu, kde je uložen následující uzel v seznamu. Poslední uzel v seznamu má obvykle ukazatel nastavený na speciální hodnotu `NULL` (nebo `nil`), což signalizuje konec seznamu. > **Ukazatel** je proměnná, která uchovává paměťovou adresu jiného prvku. V kontextu spojových seznamů ukazatele „ukazují“ na další uzly, čímž vytvářejí řetězec propojených prvků. Celý seznam je obvykle přístupný přes ukazatel na svůj první uzel, který se nazývá **hlava** (head) seznamu. Pokud je seznam prázdný, ukazatel na hlavu je `NULL`. ### Typy spojových seznamů Existuje několik variant spojových seznamů, které se liší způsobem propojení uzlů: #### 1. Jednosměrný spojový seznam Jednosměrný spojový seznam je nejjednodušší formou. Každý uzel obsahuje data a ukazatel na **následující** uzel. Procházení seznamu je možné pouze jedním směrem – od hlavy k ocasu. Pro přístup k libovolnému prvku je nutné začít od hlavy a postupně sledovat ukazatele, dokud se nedostaneme k požadovanému uzlu. **Struktura uzlu:** ``` Uzel { data: libovolný_typ dalsi: ukazatel_na_Uzel } ``` #### 2. Dvousměrný spojový seznam Dvousměrný spojový seznam rozšiřuje jednosměrný seznam o další ukazatel. Každý uzel zde obsahuje data a dva ukazatele: 1. Ukazatel na **následující** uzel. 2. Ukazatel na **předchozí** uzel. Tato struktura umožňuje procházení seznamu oběma směry – od hlavy k ocasu i od ocasu k hlavě. Poslední uzel má ukazatel na následující uzel `NULL` a první uzel má ukazatel na předchozí uzel `NULL`. **Struktura uzlu:** ``` Uzel { data: libovolný_typ predchozi: ukazatel_na_Uzel dalsi: ukazatel_na_Uzel } ``` Dvousměrné seznamy jsou flexibilnější pro některé operace, například pro mazání uzlu, pokud máme pouze ukazatel na něj, nebo pro vkládání před daný uzel, aniž bychom museli procházet celý seznam od začátku. Cena za tuto flexibilitu je vyšší paměťová náročnost (každý uzel potřebuje jeden ukazatel navíc) a složitější implementace operací, které musí aktualizovat oba ukazatele. #### 3. Kruhový spojový seznam Kruhový spojový seznam je varianta, kde ukazatel posledního uzlu neukazuje na `NULL`, ale zpět na první uzel (hlavu) seznamu. To vytváří kruhovou strukturu, kde neexistuje explicitní konec. Kruhové seznamy mohou být jednosměrné i dvousměrné. Jsou užitečné v aplikacích, kde je potřeba cyklicky procházet prvky, například při správě úloh v operačním systému. ## Operace se spojovým seznamem Základní operace se spojovým seznamem zahrnují vkládání, mazání a přístup k prvkům. ### Vkládání prvků Vkládání nového uzlu do spojového seznamu vyžaduje změnu ukazatelů. Klíčovou výhodou je, že nemusíme přesouvat žádné existující prvky, jako je tomu u polí. #### 1. Vložení na začátek seznamu * Vytvoříme nový uzel s daty. * Ukazatel `dalsi` nového uzlu nastavíme na aktuální hlavu seznamu. * Hlavu seznamu aktualizujeme tak, aby ukazovala na nový uzel. * **Časová složitost:** $O(1)$ – konstantní čas, nezávislý na velikosti seznamu. Tato operace je velmi rychlá. *Příklad:* Máme seznam `[A] -> [B] -> NULL`. Chceme vložit `[X]` na začátek. 1. Vytvoříme uzel `[X]`. Jeho `dalsi` je `NULL`. 2. Nastavíme `X.dalsi` na `A`. 3. Nastavíme hlavu na `X`. Výsledek: `[X] -> [A] -> [B] -> NULL`. #### 2. Vložení na konec seznamu * Vytvoříme nový uzel s