Zásobník a fronta jsou jednoduchými variantami obecných kolekcí prvků. Pod pojmem kolekce chápeme libovolnou datovou strukturu obsahující jistým způsobem uspořádanou sadu prvků. Do kolekce můžeme prvky přidávat, můžeme je z ní odebírat, testovat, zda je zadaný prvek v kolekci obsažen a případně jsme schopni zjistit, kolik prvků kolekce obsahuje. Tyto základní vlastnosti všech kolekcí můžeme v Javě jednoduše vyjádřit např. následujícím rozhraním:

interface Collection { 
   void add(Object elem); 
   boolean remove(Object elem); 
   boolean contains(Object elem); 
   int size(); 
}

Z hlediska vnitřní struktury jsou podstatné dvě základní vlastnosti, a to zda jsou prvky kolekce nějakým způsobem uspořádané a má tedy např. smysl hovořit o prvku na konkrétní pozici v kolekci, a zda se může konkrétní prvek v kolekci vyskytovat opakovaně. Kombinacemi těchto vlastností získáme tři prakticky využitelné varianty kolekcí:

V případě seznamu již díky uspořádání není podstatné, zda se prvky mohou či nemohou opakovat.

Seznam (list) je datová struktura, která umožňuje kromě základních operací nad obecnou kolekcí také přistupovat k libovolnému prvku na základě pořadového čísla (indexu) a vkládat a rušit prvky na libovolné pozici. Představuje vlastně nejobecnější kolekci, pomocí které můžeme implementovat kolekce další včetně zásobníku a fronty. Z tohoto důvodu jsou v mnoha programovacích jazycích seznamy k dispozici jako součást standardních knihoven (Java, C++, C#), nebo dokonce i přímo na úrovni základních typů (Haskell, Lisp, Prolog).

Typ seznam nabízí kromě operací obecné kolekce také operace definované následujícím rozhraním:

interface List extends Collection { 
  Object get(int pos); 
  void   add(int pos, Object obj); 
  void   remove(int pos); 
  int    indexOf(Object obj); 
}

Operace get() umožňuje získat prvek seznamu na zadané pozici, operace add() a remove() vkládá, resp. ruší prvek na zadané pozici. Operace indexOf() vyhledá zadaný prvek v seznamu a vrátí jeho pozici, případně hodnotu -1, pokud není nalezen.

V následujícím příkladu si ukážeme, jak můžeme projít všechny prvky takového seznamu a vypsat je na standardní výstup.

Příklad 3.5.

Vytvořte statickou funkci, která projde pomocí indexů zadaným seznamem prvků a vypíše je na standardní výstup. Funkce pro výpis nejprve zjistí počet prvků seznamu, a potom postupně v cyklu přečte operací get() jejich hodnoty a vypíše je na výstup. static void print(List list) { System.out.print("[ "); int len = list.size(); for(int i = 0; i < len; i++) { System.out.print(list.get(i) + " "); } System.out.println("]"); } Všimněte si toho, že funkce print() vůbec není závislá na tom, jakým způsobem bude seznam implementován - pracuje totiž pouze s rozhraním List. V závislosti na konkrétní implementaci se však může lišit efektivita jednotlivých variant.

Metody, jakými můžeme realizovat vyhledání prvku, záleží na konkrétní implementaci kolekce, ale všechny musí řešit jeden společný problém, a to jak definovat rovnost objektů. Každý objekt v jazyce Java má metodu equals(), která jej porovná s jiným zadaným objektem a vrátí hodnotu true nebo false. Tato metoda implicitně porovná pouze adresy, na nichž oba objekty leží (tj. použije pro jejich porovnání operátor ==). Chceme-li do porovnání zahrnout i obsah objektů, musíme pro ně metodu equals() předefinovat. Budeme-li například pracovat se standardním typem String, je jeho metoda equals() již definovaná tak, že skutečně porovnává obsah řetězců na rovnost.

Hlavní používané metody implementace seznamu jsou následující: