Kapitola 2.

Zreťazený zoznam je abstraktný údajový typ, ktorý sa skladá z jednotlivých záznamov. Tie obsahujú hodnotu prvku a ukazovateľ na nasledujúci záznam. Ak obsahujú iba jeden ukazovateľ a to na nasledujúci záznam, potom zoznamy skladajúce sa z takýchto záznamov nazývame jednosmerne zreťazené. Ak obsahujú aj ukazovateľ na predchádzajúci záznam, nazývame takéto zoznamy obojsmerne zreťazené. Algoritmy pre zoznamy sú podobné ako algoritmy pre polia. Ak ale chceme prehľadať celý zoznam nemôžeme pristupovať k záznamom priamo ako v poli, ale k nasledujúcemu záznamu alebo záznamu niekde uprostred zoznamu sa vždy musíme dostať pomocou ukazovateľa z predchádzajúceho záznamu. Niekedy môže posledný záznam obsahovať ukazovateľ na prvý záznam. Pri obojsmerne zreťazenom zozname potom aj prvý záznam môže obsahovať ukazovateľ na posledný. Takýmto zoznamom potom hovoríme zoznamy zreťazené dokola.

V záznamoch zoznamu sú zväčša uložené dátové štruktúry. Algoritmy, ktoré sú opísané na týchto stránkach však budú pracovať so záznamami, v ktorých budú uchovávané iba celé čísla.

Výstupom algoritmov venujúcim sa vyhľadávaniu v poli môže byť logická hodnota, ktorá odpovedá úspešnosti vyhľadávania alebo ukazovateľ na záznam s hľadanou hodnotou. Pri neúspešnom vyhľadávaní vraciame miesto konkrétneho ukazovateľa nulový ukazovateľ. Počet záznamov v zozname budeme označovať písmenom n.

Keďže boli použité rozdielne implementácie zoznamu pre opisované algoritmy, implementáciu tried nájdete na stránkach podkapitôl.