2022.07 Spájané zoznamy

Zhrnutie prednášky

Prednáška uvádza spájané zoznamy v jazyku C ako riešenie hlavných nevýhod jednorozmerných polí, ktorými sú fixná veľkosť, zbytočne rezervovaná pamäť a lineárne drahé operácie, napríklad mazanie prvku zo stredu poľa. Na analógii ukladania súborov na disk po blokoch, kde každý blok odkazuje na ten nasledujúci, sa vysvetľuje princíp jednosmerného spájaného zoznamu. V jazyku C sa uzol (node) definuje ako štruktúra s dátami a ukazovateľom na ďalší uzol rovnakého typu; obojsmerný zoznam by pridal aj ukazovateľ na predchádzajúci prvok. Následne sa predstavujú základné operácie Create, Retrieve, Update a Delete a prakticky sa implementuje pomocná funkcia traverse na prechod a výpis zoznamu. Začína sa aj implementácia funkcie append, ktorá pridáva prvok na koniec zoznamu a využíva ukazovateľ na ukazovateľ na hlavu, aby mohla vytvoriť nový zoznam, ak je pôvodný prázdny.

• - Polia majú fixnú veľkosť, plytvajú pamäťou a ich základné operácie sú lineárne drahé.
• - Mazanie prvku zo stredu poľa vytvára medzeru (rieдke pole), preto treba prvky posúvať.
• - Spájaný zoznam pozostáva z uzlov, ktoré obsahujú dáta a referenciu na ďalší uzol.
• - Jednosmerný zoznam umožňuje pohyb len od začiatku ku koncu, obojsmerný pridáva ukazovateľ na predchádzajúci uzol.
• - Základné operácie nad zoznamom sú Create, Retrieve, Update a Delete (CRUD).
• - Funkcia traverse prechádza zoznam pomocným ukazovateľom a vypisuje dáta, pričom hlava zostáva nezmenená.
• - Funkcia append alokuje nový uzol cez calloc a prijíma adresu hlavy (ukazovateľ na ukazovateľ), aby vedela vytvoriť zoznam z prázdneho.

Zhrnutie pripravené s pomocou AI z prepisu videa.