Singly Linked List vs. Double Linked List
Propojený seznam je lineární datová struktura, která se používá k ukládání kolekce dat. Propojený seznam přiděluje paměť svým prvkům samostatně ve svém vlastním bloku paměti a celková struktura je získána propojením těchto prvků jako článků v řetězci. Jednotlivě propojený seznam je tvořen posloupností uzlů a každý uzel má odkaz na další uzel v posloupnosti. Dvojitě propojený seznam obsahuje posloupnost uzlů, ve kterých každý uzel obsahuje odkaz na další uzel i na předchozí uzel.
Singly Linked List
Každý prvek v jednotlivě propojeném seznamu má dvě pole, jak je znázorněno na obrázku 1. Datové pole obsahuje aktuální uložená data a další pole obsahuje odkaz na další prvek v řetězci. První prvek propojeného seznamu je uložen jako hlava propojeného seznamu.
Obrázek 2 znázorňuje jednotlivě propojený seznam se třemi prvky. Každý prvek ukládá svá data a všechny prvky kromě posledního ukládají odkaz na další prvek. Poslední prvek má ve svém dalším poli hodnotu null. K jakémukoli prvku v seznamu lze přistupovat tak, že začnete od začátku a budete následovat další ukazatel, dokud nesplníte požadovaný prvek.
Seznam s dvojitým odkazem
Každý prvek ve dvojitě propojeném seznamu má tři pole, jak je znázorněno na obrázku 3. Podobně jako u samostatně propojeného seznamu obsahuje datové pole aktuální uložená data a další pole obsahuje odkaz na další prvek v řetězci. Předchozí pole navíc obsahuje odkaz na předchozí prvek v řetězci. První prvek propojeného seznamu je uložen jako hlava propojeného seznamu.
Obrázek 4 znázorňuje dvojitě propojený seznam se třemi prvky. Všechny mezilehlé prvky ukládají odkazy na první a předchozí prvky. Poslední prvek v seznamu má ve svém dalším poli hodnotu null a první prvek v seznamu má ve svém předchozím poli hodnotu null. Dvojitě propojený seznam lze procházet dopředu sledováním následujících odkazů v každém prvku a podobně lze procházet zpět pomocí předchozích odkazů v každém prvku.
Jaký je rozdíl mezi seznamem s jedním odkazem a seznamem s dvojitým odkazem?
Každý prvek v jednoduše propojeném seznamu obsahuje odkaz na další prvek v seznamu, zatímco každý prvek ve dvojitě propojeném seznamu obsahuje odkazy na další prvek i na předchozí prvek v seznamu. Dvojitě propojené seznamy vyžadují více místa pro každý prvek v seznamu a základní operace, jako je vkládání a mazání, jsou složitější, protože se musí vypořádat se dvěma odkazy. Dvojité seznamy odkazů však umožňují snadnější manipulaci, protože umožňují procházet seznamem vpřed a vzad.
