Spojový seznam

Propojený seznam  je základní dynamická datová struktura v informatice, sestávající z uzlů obsahujících data a odkazů ("odkazů") na další a/nebo předchozí uzel seznamu. [1] Zásadní výhodou oproti poli je strukturální flexibilita: pořadí prvků propojeného seznamu se nemusí shodovat s pořadím datových prvků v paměti počítače [2] a pořadí procházení seznamu je vždy explicitně nastavena svými vnitřními odkazy.

Typy propojených seznamů

Lineární propojený seznam

Jednotlivě propojený seznam (jednotlivě propojený seznam)

Lineární jednotlivě řízený seznam je datová struktura sestávající z prvků stejného typu, propojených postupně pomocí ukazatelů. Každý prvek seznamu má ukazatel na další prvek. Poslední prvek seznamu ukazuje na NULL . Prvek, na který neukazuje, je prvním (hlavním) prvkem seznamu. Zde odkaz u každého uzlu ukazuje na další uzel v seznamu. V jednotlivě propojeném seznamu se můžete pohybovat pouze ke konci seznamu. Je nemožné zjistit adresu předchozího prvku na základě obsahu aktuálního uzlu.

V informatice je lineární seznam obvykle definován jako abstraktní datový typ (ADT), který formalizuje pojem uspořádané kolekce dat . V praxi jsou lineární seznamy obvykle implementovány pomocí polí a propojených seznamů. Někdy se termín „seznam“ také neformálně používá jako synonymum pro „propojený seznam“. Například netypovaný proměnlivý seznam ADT lze definovat jako sadu konstruktoru a základních operací:

  • Operace, která kontroluje, zda je seznam prázdný.
  • Tři operace přidání objektu do seznamu (na začátek, konec nebo dovnitř za libovolný (n-tý) prvek seznamu);
  • Operace, která vyhodnocuje první (hlavní) prvek seznamu;
  • Operace pro přístup k seznamu sestávajícím ze všech prvků původního seznamu kromě prvního.
Charakteristika
  • Délka seznamu . Počet prvků v seznamu.
  • Seznamy mohou být zadané nebo nezadané . Pokud je seznam typovaný, pak je dán typ jeho prvků a všechny jeho prvky musí být typů, které jsou kompatibilní s daným typem prvků seznamu. Většina seznamů je psaná.
  • Seznam může být seřazený nebo neřazený .
  • V závislosti na implementaci může být možný náhodný přístup k prvkům seznamu.
Jednotlivě propojený seznam v programovacích jazycích

Xi

seznam struktur { int pole ; // datové pole struct seznam * další ; // ukazatel na další prvek };

pomocí jednoho propojeného seznamu:

seznam struktur * l1 = ( seznam struktur * ) malloc ( sizeof ( seznam struktur )); l1 -> pole = 1 ; l1 -> next = ( seznam struktur * ) malloc ( sizeof ( seznam struktur )); l1 -> další -> pole = 2 ; l1 -> další -> další = ( seznam struktur * ) malloc ( sizeof ( seznam struktur )); /* atd. */ Dvojitě propojený seznam (dvojitě propojený seznam)

Zde odkazy v každém uzlu ukazují na předchozí a následující uzel v seznamu. Stejně jako jednoduše propojený seznam, i dvojitě propojený seznam umožňuje pouze sekvenční přístup k prvkům, ale také umožňuje pohyb v obou směrech. V tomto seznamu je snazší mazat a přeskupovat prvky, protože adresy těch prvků seznamu, jejichž ukazatele směřují na měněný prvek, jsou snadno dostupné.

XOR propojený seznam

Málo používané.

Kruhový propojený seznam

Druh propojeného seznamu je kruhový (cyklický, uzavřený) seznam. Může být také jednovazný nebo dvojitý. Poslední prvek kruhového seznamu obsahuje ukazatel na první a první (v případě dvojitě propojeného seznamu) na poslední.

Zpravidla je taková struktura implementována na základě lineárního seznamu. Každý kruhový seznam navíc ukládá ukazatel na první prvek. V tomto seznamu není žádný odkaz na NULL.

Existují také kruhové seznamy s vyhrazeným prvkem head, který usnadňuje procházení celého seznamu.

Přeskočit seznam

Rozšířený seznam odkazů

Výhody

  • efektivní (v konstantním čase) přidávání a odebírání prvků
  • velikost je omezena pouze velikostí paměti počítače a bitovou hloubkou ukazatelů
  • dynamické přidávání a odebírání prvků

Nevýhody

Nevýhody propojených seznamů vyplývají z jejich hlavní vlastnosti – sekvenčního přístupu k datům:

  • složitost přímého přístupu k prvku, konkrétně určení fyzické adresy podle jejího indexu (sériového čísla) v seznamu
  • ukazatelová pole (ukazatele na další a předchozí prvek) spotřebovávají další paměť (například v polích nejsou ukazatele potřeba)
  • některé operace se seznamy jsou pomalejší než s poli, protože k libovolnému prvku seznamu lze přistupovat pouze procházením všech prvků, které mu předcházejí
  • sousední prvky seznamu mohou být alokovány nelokálně v paměti, což sníží efektivitu ukládání dat do mezipaměti v procesoru
  • ve srovnání s poli je mnohem obtížnější (ačkoli možné) provádět paralelní vektorové operace na propojených seznamech, jako je výpočet součtu: režie iterace přes prvky snižuje efektivitu paralelizace

Viz také

Poznámky

  1. ↑ Cormen, Leiserson, Rivest a Stein. Úvod do algoritmů, 2. vydání. The MIT Press, 2001. ISBN 0-262-03293-7
  2. ↑ Zarovnání dat
 Datové struktury
Seznamy
Stromy
Počítání
jiný