Ve vědě o počítačích , je seznam je datová struktura umožňující údaje , které mají být sestaveny tak, aby bylo možné přistupovat volně (na rozdíl od fronty a komíny , které jsou přístupné v FIFO i LIFO režimu v tomto pořadí ).
Seznam je základem složitějších datových struktur, jako je zásobník , fronta , stromy atd. Význam seznamu jako datové struktury je takový, že je základem programovacího jazyka Lisp ( zpracování seznamu v angličtině ).
Zde jsou primitiva běžně používaná k manipulaci se seznamy; pro primitiva pro manipulaci se seznamem neexistuje žádná standardizace, takže jejich názvy jsou uvedeny neformálně.
Základní primitiva:
Často se vyskytující pomocní primitiva:
Seznam je kontejner prvků, kde každý prvek obsahuje data a další informace umožňující načtení dat v seznamu. Povaha (typy) těchto informací charakterizuje jiný typ seznamu.
Obecně můžeme rozlišit dva typy seznamu:
Přístup k prvku se provádí pomocí indexu, který představuje umístění prvku ve struktuře.
Data v tabulce souvisejí v paměti. To vyvolává pevnou velikost pole, tj. Nemění se; Některé jazyky vyšší úrovně však poskytují pole, která mění jejich velikost podle jejich použití: toto se nazývá dynamicky velké pole. Jejich implementace však využívá princip propojených seznamů (viz níže).
Pole mohou mít také více dimenzí představovaných posloupností dolních indexů. V tomto případě, je-li n je rozměr pole (kde n je nenulová přirozená celé číslo), rozměr prvků pole 1 (na 1 I. index sekvence) každý polohovací na jinou (sub) pole rozměr n- 1 .
Na rozdíl od pole nemá velikost propojeného seznamu jiné omezení než velikost dostupné paměti. Toto omezení překonává skutečnost, že každý prvek může podle typu propojeného seznamu ukazovat na jeden nebo více prvků seznamu pomocí rekurzivní definice. Chcete-li tedy zvětšit velikost propojeného seznamu, stačí vytvořit nový prvek a na nový prvek nasměrovat určité prvky, které již v seznamu jsou.
Existují dva hlavní typy propojeného seznamu:
K tomu můžeme přidat vlastnost: cyklus. Tentokrát propojený seznam tvoří smyčku. Jakmile se dostanete na „konec“ seznamu a chcete pokračovat, ocitnete se na „prvním“ prvku seznamu. V tomto případě pojem začátek nebo konec řetězce již nemá důvod existovat.