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

Zhrnutie prednášky

Prednáška predstavuje obojsmerné spájané zoznamy, ktoré odstraňujú hlavnú nevýhodu jednosmerných zoznamov – nutnosť obiehať celý zoznam pri pohybe proti smeru smerníkov. Každý atóm okrem hodnoty a smerníka nasl obsahuje aj smerník pred na predchodcu. Na príklade cyklického obojsmerného zoznamu sa postupne implementujú operácie inicializácia, vkladanie, čítanie hodnoty, pohyb dopredu aj dozadu a odoberanie. Pri vkladaní treba nastaviť smerníky nového atómu a prepojiť k nemu susedné atómy v oboch smeroch. Pri odoberaní sa atóm preskočí prepojením jeho susedov, smerník sa posunie na nasledujúci atóm a pamäť sa uvoľní; osobitne sa ošetruje prípad jediného atómu. Fungovanie je overené na slove „streda“.

• - Obojsmerný zoznam má v každom atóme smerníky nasl aj pred, takže pohyb proti smeru šípok nevyžaduje obiehanie celého zoznamu.
• - Inicializácia vytvorí jeden atóm, ktorého nasl aj pred ukazujú sám na seba (zacyklenie).
• - Pri vkladaní do neprázdneho zoznamu sa najprv nastavia smerníky nasl a pred nového atómu, potom sa upravia pred nasledovníka a nasl aktuálneho atómu.
• - Po vložení sa musí smerník zoznamu posunúť na novovložený atóm.
• - Posun dozadu cez smerník pred nepotrebuje pomocný smerník ani cyklus.
• - Odoberanie preskočí atóm prepojením jeho predchodcu a nasledovníka, smerník sa posunie na nasledujúci atóm a pôvodný atóm sa uvoľní cez free.
• - Odoberanie musí osobitne ošetriť prípad jediného atómu, kedy sa po uvoľnení nastaví smerník zoznamu na NULL.

Zhrnutie pripravené s pomocou AI z prepisu videa.