03_seznamy_realizace

// jinak proměnné zanikají 

a.iLeft = &b; 
a.iRight = &c; 
b.iLeft = &d; 
b.iRight = &e; 
c.iLeft = &f; 
c.iRight = &g; 

Varianty seznamů

-  jednosměrný x obousměrný (jednocestný x dvoucestný); obecný vícenásobně vázaný seznam 

-  cyklický/kruhový - buffer 

-  U jednosměrného potřebujeme často pracovat s prvkem „před“ – výhodou jsou rekurzní 

algoritmy. Například pro požadavek rušení od konce je výhodnější než neustálé hledání 
posledního prvku. 

-  obousměrný má snadnější pohyb v poli 

-  jednosměrný umožňuje spojení několika seznamů (seznamy začnou různě, ale v určité pozici 

se napojí na jediný koncový seznam. Problém s odstraněním spojovacího/společného prvku. 

-  obousměrný má o ukazatel více  

srovnání seznamu, stromu a pole – časová složitost 

-  seznamy a stromy jsou fragmentované 

-  nalezení prvku z daným indexem – O(n) ; O(log n) O(1) 

-  vložení, vybrání prvku na začátku – O(1) ; O(log n) ; nelze 

-  vložení, vybrání prvku na konec - O(1)/O(n) (ukazatel Tail ano/ne) ; O(log n) ; nelze 

-  vložení, vybrání uprostřed – nalezení prvku + O(1); O(1) ; O(log n) ; nelze 

-  paměťové nároky: + n . ukazatelů  ; +2 . n . ukazatelů ; +0 

Základní operace se seznamy 

-  přidání prvku – nastavení na (předchozí) prvek + vložení 

-  vybrání prvku – nastavení na (předchozí) prvek + vybrání 

-  předání odkazu na prvek 

-  zjištění zda je seznam prázdný 

Operace musí obsloužit základní stavy: 

-  práce s prázdným seznamem 

-  manipulace s prvním prvkem 

-  manipulace s posledním prvkem 

-  manipulace s prvky uprostřed seznamu