Obojsmerný spájaný zoznam

Zhrnutie prednášky

Prednáška rozširuje jednosmerný spájaný zoznam na obojsmerný (double list) v troch variantoch: cyklický, lineárny bez nárazníkov a lineárny s nárazníkmi. Motiváciou je, že v jednosmernom zozname pohyb od konca k začiatku vyžaduje pomocný smerník a prechod zoznamom, ktorého cena závisí od počtu prvkov. Riešením je rozšíriť atom o ďalší smerník na predchádzajúci prvok, čo veľkosť atómu zvýši len o jednu adresu, ale vyžaduje prepracovať všetky existujúce operácie. Pri cyklickom zozname sa podrobne rozoberá vkladanie (päť krokov prepájania šípok) a mazanie, pri ktorom odpadá hľadanie predchádzajúceho atómu cyklom. Na záver sa začína lineárny obojsmerný zoznam s nárazníkmi, kde sa mení najmä vytvorenie zoznamu.

• - Atom obojsmerného zoznamu obsahuje hodnotu a dva smerníky: na nasledovníka a na predchodcu.
• - Prechod proti smeru šípok v jednosmernom zozname vyžaduje cyklus závislý od počtu prvkov; v obojsmernom stačí jeden krok.
• - Inicializácia a test prázdnosti sa nemenia, index je 0 pri prázdnom zozname.
• - Pri vkladaní do neprázdneho cyklického zoznamu sa prepája päť smerníkov, pričom poradie krokov je dôležité.
• - Pri mazaní sa musia prepojiť smerníky susedov odstraňovaného atómu, potom sa atóm uvoľní cez free; osobitne sa ošetruje zoznam s jediným atómom.
• - Pohyb kurzora v protismere je jednoduchý posun cez smerník predchodcu, bez pomocného smerníka.
• - Pri lineárnom zozname s nárazníkmi sa mení create: oba nárazníky majú dva smerníky a začiatočný nárazník ukazuje pred seba na NULL.

Zhrnutie pripravené s pomocou AI z prepisu videa.