Seznam (informatika)

V informatice je seznam ( anglicky  list ) abstraktní datový typ , což je uspořádaná množina hodnot, ve kterých se určitá hodnota může vyskytovat více než jednou. Instance seznamu je počítačová implementace matematického konceptu konečné posloupnosti . Instance hodnot v seznamu se nazývají prvky seznamu ( anglicky  item, entry nebo element ); pokud se hodnota vyskytuje vícekrát, je každý výskyt považován za samostatný prvek.

Termín seznam také odkazuje na několik specifických datových struktur , které se používají při implementaci abstraktních seznamů, zejména propojených seznamů .

Definice

Použitím zápisu syntakticky orientované konstrukční metody C. Hoareho lze definici seznamu zapsat následovně:

První řádek této definice znamená, že seznam prvků typu (řekněme: "seznam přes ") je diskriminované spojení prázdného seznamu a kartézského součinu atomu typu se seznamem nad . K vytváření seznamů se používají dva konstruktory (druhý řádek definice), z nichž první vytváří prázdný seznam a druhý - neprázdný. Je zcela jasné, že druhý konstruktor obdrží jako vstup nějaký atom a seznam jako parametry a vrátí seznam, jehož prvním prvkem je původní atom a zbytek jsou prvky původního seznamu. To znamená, že atom má předponu v seznamu, což je důvod pro takový název konstruktoru. Prázdný seznam není atom, a proto nemůže být opatřen předponou. Na druhou stranu prázdný seznam je nulový prvek pro konstrukci seznamů, takže každý seznam obsahuje prázdný seznam na samém konci - konstrukce začíná u něj.

Třetí řádek definuje selektory pro seznam, tedy operace pro přístup k prvkům v seznamu. Selektor bere jako vstup seznam a vrací první prvek tohoto seznamu, tedy typ výsledku je type . Tento selektor nemůže přijmout prázdný seznam jako vstup - v tomto případě není výsledek operace definován. Selektor vrátí seznam získaný ze vstupu v důsledku odříznutí jeho hlavy (prvního prvku). Tento selektor také nemůže přijmout prázdný seznam jako vstup, protože v tomto případě není výsledek operace definován. Pomocí těchto dvou operací můžete získat libovolný prvek ze seznamu. Chcete-li například získat třetí prvek seznamu (pokud nějaký existuje), musíte použít selektor dvakrát za sebou a poté použít selektor . Jinými slovy, chcete-li získat prvek seznamu, který je na pozici (počínaje u prvního prvku, jak je při programování obvyklé), musíte jednou použít selektor a poté použít selektor .

Čtvrtý řádek definice popisuje predikáty seznamu , tedy funkce, které v závislosti na určitých podmínkách vracejí booleovskou hodnotu. První predikát vrátí hodnotu , pokud je daný seznam prázdný. Druhý predikát funguje obráceně. Nakonec pátý řádek popisuje části seznamu, což, jak již bylo zmíněno, jsou prázdné a neprázdné seznamy.

Vlastnosti

Takto definovaná datová struktura má některé vlastnosti:

• Velikost seznamu  je počet prvků v něm, vyjma posledního prvku „null“, což je podle definice prázdný seznam.
• Typ prvků  je stejného typu , na kterém je sestavován seznam; všechny prvky v seznamu musí být tohoto typu.
• Seřazeno  - seznam lze třídit podle určitých třídicích kritérií (např. vzestupně celočíselné hodnoty, pokud se seznam skládá z celých čísel).
• Přístupnost  – Některé seznamy mohou v závislosti na implementaci poskytnout programátorovi selektory pro přímý přístup k číslovanému prvku.
• Srovnatelnost  - seznamy lze vzájemně porovnávat pro korespondenci a v závislosti na implementaci může operace porovnávání seznamů používat různé technologie.

Seznamy se používají k ukládání sad prvků stejného typu. Takové prvky lze třídit pro použití ve vyhledávacích funkcích nebo funkcích pro rychlé vkládání nových prvků do seznamu.

Seznamy v programovacích jazycích

Funkční jazyky

Základní strukturou jsou seznamy ve funkčních jazycích. Většina funkčních jazyků má vestavěné prostředky pro práci se seznamy, jako je získání délky seznamu, záhlaví (první prvek seznamu), konec (část seznamu, která následuje za prvním prvkem), použití funkce na každý prvek seznamu ( Mapa ), skládání seznamu atd.