Singly Linked List vs Doubly 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 se získá propojením těchto prvků jako odkazů v řetězci. Samostatně 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 skutečná 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 zobrazuje 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 nulovou hodnotu. K libovolnému prvku v seznamu lze přistupovat spuštěním v záhlaví a sledováním dalšího ukazatele, dokud nesplníte požadovaný prvek.
Dvojnásobně propojený seznam
Každý prvek v dvojnásobně propojeném seznamu má tři pole, jak je znázorněno na obrázku 3. Podobně jako v případě jednotlivě propojeného seznamu obsahuje datové pole skutečná 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 zobrazuje dvojitě propojený seznam se třemi prvky. Všechny mezilehlé prvky ukládají odkazy na první a předchozí prvky. Poslední prvek v seznamu obsahuje nulovou hodnotu ve svém dalším poli a první prvek v seznamu obsahuje nulovou hodnotu ve svém předchozím poli. Dvojitě propojený seznam lze procházet dopředu sledováním další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 Singly Linked List a Doubly Linked List?
Každý prvek v jednotlivě propojeném seznamu obsahuje odkaz na další prvek v seznamu, zatímco každý prvek v dvojnásobně propojeném seznamu obsahuje odkazy na další prvek i na předchozí prvek v seznamu. Zdvojnásobené spojené 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. Seznamy odkazů však dvojnásobně umožňují snadnější manipulaci, protože umožňují procházení seznamu dopředu a dozadu.
