Na této stránce se používá SVG a MathML.
Firefox je umí a některé další prohlížeče se pro ně dají upravit.

ADT ‑ abstraktní datové typy

Spojový seznam List

Jazyky pro umělou inteligenci (IT) Prolog a LISP a mladší generace universálních programovacích jazyků ‑ příkladem budiž Java ‑ mají spojové seznamy zabudovány.
Ve všech právě uvedených případech se používá nejjednodušší jednosměrně provázaný lineární spojový seznam, jenž má většinu požadovaných charakteristických rysů spojových seznamů.
Proto budeme spojové seznamy probírat a ilustrovat na něm. V jiných případech to výslovně uvedeme. Pro začátek zmíníme několik variant spojových seznamů s možností odskoků na ně:


Spojový seznam
  jednosměrně provázaný obousměrně provázaný
    lineární    
    cyklický    
   
#define DELKA_SLOVA 16
typedef char slovo[DELKA_SLOVA];    
typedef struct cln {
          slovo data;
          struct cln *dalsi;
     } clen;
typedef clen* spojovySeznam;


   
#define DELKA_SLOVA 16
typedef char slovo[DELKA_SLOVA];    
typedef struct cln {
          slovo data;
          struct cln *predesly;
          struct cln *dalsi;
     } clen;
typedef clen* spojovySeznam;

 




V dřívějších dobách bylo možno v programovacích jazycích alokovat pole staticky na začátku programu. Museli jsme naalokovat pole největší možné velikosti a v programu si pak třeba nechat zadat počet prvků pole a používat jen onu jeho potřenou část.
Nyní máme například i v jazyku C možnost zjistit si (zadat či spočítat) velikost pole a teprve pak ho naalokovat.

Dříve se řešila nejistá velikost potřebné paměti a nutnost ji šetřit (až na bity) právě použitím spojových seznamů. Ale i nyní jsou spojové seznamy velmi užitečné, chceme-li do nějak uspořádané posloupnosti členů vkládat nové či z nich některé vypouštět.
Kdybychom na to použili pole, museli bychom ono pole při každé takové operaci „rozhrnovat” či „shrnovat”, což by zabralo příliš mnoho času (i na dnešních rychlých počítačích, pokud by se to dělo často).

Preemptivní multitasking (víceúlohovost) v operačním systému RSX-11M firmy DEC pro jejich v letech 1970 až 1990 velmi populárních a pro další vývoj IT vlivných minipočítačích PDP‑11 byl implementován i pomocí použití jednosměrně provázaného cyklického spojového seznamu.

Chceme-li realisovat zásobník (další ADT ‑ abstraktní datový typ) bezpečněji, ikdyž trochu pomaleji a s dalším voláním podpory při běhu OS, použijeme jeho implementaci spojovým seznamem. (Rychlejší realisace zásobníku polem, při neošetření přetečení či podtečení může být v choulostivých situacích zneužita pro cracking OS.)
Podobně se často spojový seznam používá pro implementaci fronty (opět další ADT ‑ abstraktní datový typ).

Pro snazší pochopení vlastností spojových seznamů a práci s nimi se využívá expresivně podobnost seznamu s hady.
První člen spojového seznamu se potom nazývá hlava a veškerý zbytek ocas. (Cyklický spojový seznam by potom byl Uroboros.)
Spojový seznam se potom skládá výhradně jen z hlavy a ocasu.
„Odtrhneme-li” hlavu, pak je ocas ‑ pokud vůbec existuje ‑ novým spojovým seznamem s jeho hlavou a ocasem. To znamená, že člen původně bezprostředně za hlavou se stává novou hlavou.
Hlava, respective ukazatel na ni je zároveň celým spojovým seznamem.
Analogicky: každý ukazatel na člena je zároveň spojovým seznamem s ním jakožto hlavou.
Navíc: spojovým seznamem je i neadresa NULL (jméno konstanty v jazyku C), což je prázdný seznam.
Předpis pro spojový seznam je rekursivní:

seznam: NULL seznam: data seznam          kde je datová struktura (v jazyku C struct, v některých jiných record nebo záznam). První položka je datová, druhá je ukazatel (pointer) na následníka.
Ukazatel (pointer) na člena seznamu má ambivalentní povahu: ukazuje buď na onoho člena nebo na seznam, který jím začíná.
(Stejně je to v jazyku C ve znakových řetězcích: ukazuje se buď na znak nebo na řetězec jím začínající a končící znakem '\0'.)

Pro jednoduchost si obvyklé funkce jednosměrně provázaný lineární spojový seznam.
Cyklický by mohl mít vyjmi(clen) a spolu se obousměrně provázanými i pridejZa(clen, novyClen)

clen najdi(seznam, data), pridejZa(clen, novyClen), seznam vytvor(), smaz(seznam), velikost(seznam), vlozZa(clen, novyClen), vyjmi(seznam, clen), vypis(seznam)

    Jednosměrně provázaný lineární spojový seznam



data 0 z data 1 data 2 data 3 data 4 -25 data n

 je NULL.


Ukazatele na hlavu - prvního člena jednosměrně provázaného lineárního spojového seznamu (tady z) ‑ nesmíme nikdy ztratit.

#define DELKA_SLOVA 16
typedef char slovo[DELKA_SLOVA];    
typedef struct cln {
          slovo data;
          struct cln *dalsi;
     } clen;
typedef clen* spojovySeznam;


Vzhledem k typu jde o rekursivní definici: datová struktura obsahuje jakožto svou položku odkaz „na sebe”.
(Přitom se použije dosud záhadná „jmenovka” ‑ tady cln.)
Tady je tou datovou částí slovo, ale může tam být cokoli a datových položek může být i více.


    Jednosměrně provázaný cyklický spojový seznam



data 0 z data 1 data 2 data 3 data 4 data n
Ukazatele na hlavu - prvního člena jednosměrně provázaného cyklického spojového seznamu (tady z) ‑ můžeme ztratit.
Nesmíme nikdy ztratit ukazatele na všechny členy. Musíme mít ukazatele na alespoň jednoho člena.

#define DELKA_SLOVA 16
typedef char slovo[DELKA_SLOVA];    
typedef struct cln {
          slovo data;
          struct cln *dalsi;
     } clen;
typedef clen* spojovySeznam;


Vzhledem k typu jde o rekursivní definici: datová struktura obsahuje jakožto svou položku odkaz „na sebe”.
(Přitom se použije dosud záhadná „jmenovka” ‑ tady cln.)
Tady je tou datovou částí slovo, ale může tam být cokoli a datových položek může být i více.





    Obousměrně provázaný lineární spojový seznam



data 0 z data 1 data 2 data 3 data 4 data n

 je NULL.


        Obousměrně provázaný cyklický spojový seznam



data 0 z data 1 data 2 data 3 data 4 data n



        Pro oba ‑ obousměrně provázaný lineární i obousměrně provázaný cyklický ‑ spojový seznam platí:

Ukazatele na hlavu ‑ prvního člena obousměrně provázaného lineárního spojového seznamu ‑ můžete klidně ztratit.
Nacestovat na jeho začátek vždy můžete od jakéhokoli člena tohoto spojového seznamu.
Obousměrně provázaný cyklický spojový seznam začátek ani nemá. Dostat se k jakémukoli členu lze dvojím způsobem.
Nikdy ale nesmíte ztratit ukazatele na všechny členy obou těchto spojových seznamů.



#define DELKA_SLOVA 16
typedef char slovo[DELKA_SLOVA];    
typedef struct cln {
          slovo data;
          struct cln *predesly;
          struct cln *dalsi;
     } clen;
typedef clen* spojovySeznam;


Místo (*ukazatelNaStrukturu).polozka používejte v jazyku C „zkratku” ukazatelNaStrukturu->polozka





Tady je animace (omlouvám se za kostrbatost ‑ nějak mi nevyšlo dost času) vložení člena do spojového seznamu:


DATA DATA DATA DATA // first arrow movement za který se vkládá ten, který se vkládá Start