Jednosmerné spájané zoznamy (záznam on-line prednášky 2. 3. 2022).

Zhrnutie prednášky

Prednáška uvádza jednosmerné spájané zoznamy ako zovšeobecnenie radu a zásobníka, kde možno vkladať a odoberať na ľubovoľnom mieste. Zoznam sa implementuje len pomocou dynamicky alokovaných atómov (hodnota typu int a smerník na nasledujúci atóm), nie poľom. Preberá sa cyklický spájaný zoznam, v ktorom posledný atóm ukazuje na prvý a celý zoznam reprezentuje jediný smerník na atóm. Postupne sa implementujú inicializácia, test prázdnosti, zistenie hodnoty a vkladanie za aktuálny atóm pomocou pomocného smerníka, po ktorom sa ukazovateľ posunie na nový atóm. Nakoniec sa ukazuje posun v smere smerníkov a v protismere, ktorý vyžaduje obehnúť celý kruh, čo je nevýhoda riešená obojsmernými zoznamami budúci týždeň.

• - Spájaný zoznam zovšeobecňuje rad a zásobník, lebo vkladať a odoberať možno kdekoľvek.
• - Zoznam sa implementuje iba pomocou atómov (hodnota a smerník na nasledujúci), nie poľom.
• - Cyklický zoznam: posledný atóm ukazuje na prvý a zoznam je reprezentovaný jedným smerníkom na atóm.
• - Inicializácia nastaví smerník na NULL a prázdnosť sa testuje porovnaním s NULL.
• - Vkladanie do prázdneho zoznamu vytvorí atóm ukazujúci sám na seba; inak sa nový atóm vloží za aktuálny pomocou pomocného smerníka.
• - Po vložení sa smerník zoznamu presunie na nový atóm, inak by stále ukazoval na pôvodný.
• - Posun v smere smerníkov je jednoduchý, no posun v protismere vyžaduje obehnúť celý kruh; túto nevýhodu rieši obojsmerný zoznam.

Zhrnutie pripravené s pomocou AI z prepisu videa.