Zřetězené datové struktury

Zřetězená datová struktura je v programech taková struktura, která obsahuje soubor záznamů (uzlů), které jsou mezi sebou propojené pomocí referencí (odkazy nebo ukazateli).

Hlavním rozdílem mezi zřetězenou datovou strukturou a nezřetězenou je tedy to, že ve zřetězené musí být u každého prvku odkaz na další prvek/prvky v sekvenci, zatímco v nezřetězené struktuře probíhá přístup k dalšímu prvku pomocí dopočítání adresy v paměti.

Výhody a nevýhody zřetězených datových struktur

Obecně je hlavní výhodou zřetězených struktur větší volnost tvorby, ne všechny struktury používané k řešení specifických problémů jdou vytvořit jako nezřetězené, a také je velmi často mnohem přehlednější a jednodušší vytvořit strukturu zřetězeným způsobem.

Rozdíly u srovnatelné struktury

Mějme stejné struktury, jednu uloženou zřetězeně a druhou v souvislém bloku paměti kde dokážeme spočítat adresu pro okamžitý přístup k libovolnému prvku. Klasickým příkladem by byl třeba lineární seznam a (dynamické) pole.

Zřetězená struktura bude obecně rychlejší pro manipulaci s daty, tedy mazání a přidávání hodnot kamkoliv ve struktuře kromě konce, měníme jen prvek, se kterým manipulujeme a odkazy okolních prvků. Zatímco u nezřetězené struktury musíme, kromě speciálních případů jako přidávání v poli na konec, přesouvat větší objemy dat.

Nezřetězená struktura bude obecně rychlejší pro náhodný přístup k datům. Ve zřetězené struktuře musíme „dojít“ k požadovanému prvku přes odkazy. Zatímco v nezřetězené struktuře je přímo dopočítána adresa paměti a přístup je tedy velmi rychlý.

Dalším rozdílem, který velmi často nebude rozhodující, ale je dobré na něj při výběru vhodné struktury pamatovat, je že zřetězené struktury jsou v paměti větší než nezřetězené, ale většinou to není zajímavý rozdíl.

Důležité struktury často ukládané jako zřetězené

Lineární seznam

Lineární seznam je popsán na vlastní stránce, která obsahuje i příklad.

Zásobník

Zásobník je datová struktura, která je nejčastěji používána na dočasné uložení prvků pro další zpracování. Ukládá se metodou LI-FO (last in – first out) což znamená, že vždy ze zásobníku zpětně odebíráme poslední prvek, který jsme do něj vložili.

Jeho fungování i s příklady implementace jsou dobře popsány na vlastní stránce.

Fronta

Fronta je podobná zásobníku, ale funguje na principu FI-FO (first in – last out) tedy prvky dostáváme zpět v pořadí, ve kterém jsme je přidávali. Další informace o frontě jsou na její samostatné stránce, ale ta se nezabývá její možnou reprezentací v programu.

Lineární seznam je vhodným základem fronty, k implementaci nám stačí držet odkaz na jeho začátek, ale je vhodné držet odkaz i na konec seznamu abychom dosáhli rychlého přidávání. Také není potřeba mít seznam dvojitě zřetězený, stačí nám odkaz od předchozího prvku na následující.

Při přidávání prvku vezmeme prvek, co je právě na konci a přidáme do něj odkaz na přidávaný prvek a také aktualizujeme odkaz na poslední prvek seznamu.

Při odebírání prvku vezmeme první prvek a aktualizujeme odkaz na první prvek na hodnotu z odkazu na následníka v prvním prvku.

Graf

Princip grafu je popsán na vlastní stránce.

V tomto článku nastíníme, jak se grafové struktury ukládají v informatice a zaměříme se na ukládání do zřetězených struktur, i když je samozřejmě lze uložit i třeba do matic, což je nastíněné ve článku o grafech.

Obecný graf si můžeme v nejjednodušší podobě představit jako strukturu, kde v uzlu je pole odkazů na další takové struktury. V reálném světě se do takové struktury přidávají ještě další informace patřící ke každému uzlu, ale hlavní je metoda navázání okolí.

Graf může být neorientovaný, hrana mezi uzly je obousměrná, to v naší reprezentaci vyřešíme v následujících krocích:

Do seznamu sousedů uzlu (uzel U), kterému přidáváme souseda přidáme odkaz na souseda
Do seznamu sousedů souseda, kterého přidáváme přidáme odkaz na uzel U (uzel do něhož jsme přidávali v minulém kroku)

Nebo může být graf orientovaný, hrana je jednosměrná, potom je přidání souseda jednodušší a stačí provést první krok z minulé posloupnosti, tedy jen přidám souseda do uzlu, a to je vše.

//struktura uzlu v grafu
class GraphNode {
    //uzel může obsahovat libovolné informace
    public int data;
    //uzel musí obsahovat seznam odkazů na sousedy
    public List<GraphNode> neighnours;

    //přidání souseda v grafu
    public void AddNeighbour(GraphNode other) {
        //přidáme odkaz na souseda
        neighnours.Add(other);
        //pokud je graf neorientovaný
        //přidáme odkaz na sebe do souseda
        other.neighnours.Add(this);
    }
}

Strom

Grafům se často zavádějí podmínky, které z nich tvoří specializované struktury vhodné k řešení specifických úkolů. Jednou z nejdůležitějších specializací grafu v IT je strom. Strom je orientovaný graf, je tedy jen jednoduše zřetězený, který nemá cykly. Tím vzniká hierarchická struktura, která se ukládá efektivněji než obecný graf.

//struktura uzlu stromu
class TreeNode {
    //uzel může obsahovat libovolné informace
    public int Data;
    //uzel musí obsahovat seznam odkazů na potomky
    public List<TreeNode> Children;

    //přidáváme potomka, protože je struktura 
    //jednoduše zřetězena nepřidáváme zpětný odkaz
    public void AddChild(TreeNode child) {
        Children.Add(child);
    }
}

//třída zachycující strom
class Tree {
    //jediným požadavkem na obecný strom je 
    //držení odkazu na kořen
    public TreeNode Root;
}

Halda

Halda je stromová datová struktura, ve které platí, že potomek má vždy stejnou nebo větší hodnotu než jeho rodič. Podrobnější popis a využití je na vlastní stránce, ale je tam nastíněná jen implementace pomocí polí.

Pomocí polí se dá implementovat jen binární halda, tedy halda, kde každý uzel má maximálně 2 potomky. Haldy s lepšími vlastnostmi už jako pole reprezentovat nejdou.

Takové haldy mají uzly podobné uzlu obecného stromu, třeba uzel Fibonacciho haldy může mít neomezené množství potomků.

Binární vyhledávací strom

Strom se dá dále specializovat na binární strom, kde každý uzel má maximálně 2 potomky, toho se dá využít třeba k vytvoření struktury ve které se dá efektivně vyhledávat, binární vyhledávací strom. V takovém stromu je v každém uzlu hodnota jednoho potomka menší než hodnota uzlu a hodnota druhého potomka je větší. Tato změna nám dokáže velmi urychlit vyhledávání prvků v takové struktuře.

Přesná struktura takového stromu a jeho implementace je na jeho vlastní stránce.

Množina

Datová struktura zachycující množinu dokáže uložit hodnoty bez opakujících se hodnot. Více informací o vlastnostech a použití této datové struktury je na její vlastní stránce, kde ale chybí informace o možnostech implementace.

Jedna z možností implementace množiny je pomocí binárního vyhledávacího stromu. Binární vyhledávací strom je vhodnou strukturou, protože hlavním použitím množiny je testování, zda je prvek v množině přítomen, na což je binární vyhledávací strom vhodný.

Oproti implementaci pomocí struktur používajících hashové funkce je implementace pomocí binárního vyhledávacího stromu často pomalejší a není v něm tak jednoduché naimplementovat množinové operace, ale oproti hashovaným strukturám dokáže zachovávat pořadí vložených prvků.