Lekce 3 - Seznam (List) pomocí pole v Javě

V minulé lekci, Java Collections Framework, jsme se podívali, jak má jazyk Java implementované kolekce v rámci Java Collections Frameworku.

Dnes se budeme v Java tutoriálu věnovat první kolekci, seznamům (listům). To je typ kolekcí, se kterým jsme se během kurzu již setkali.

Pole

Udělejme si na začátku malou odbočku zpět k poli, které bylo první "kolekcí", kterou jsme v seriálu poznali. Pole se vyznačuje tím, že má pevně daný počet prvků. Z tohoto důvodu někdy ani nebývá považováno za kolekci, protože nesplňuje část jejich definice. Prvky v poli jsou číselně indexovány a to od nuly.

Hlavní nevýhodou pole tedy je, že do něj nemůžeme za běhu aplikace prvky přidávat nebo je mazat. To bohužel často potřebujeme, i když jsou situace, kdy je pole ideální volba. Touto daní je vyvážena obrovská rychlost, se kterou můžeme s prvky pole pracovat. Jelikož data jsou stejného typu (ať již úplně stejného, nebo společného předka), zabírají v paměti stejně místa. Jednotlivé prvky pole jsou v paměti uložené za sebou, jako v řadě, která je nepřerušená. Pole celých čísel si můžeme představit např. takto:

Pokud tedy chceme např. přistoupit na 5. prvek, jen vstoupíme tam, kde pole začíná, a poté odskočíme 4 násobky velikosti typu (zde intu) dále. Jsme na 5. prvku. Čtení a zápis na indexy v poli má tedy konstantní časovou složitost. Pokud vás tento termín zmátl, můžete to chápat tak, že do pole zapisujeme okamžitě a stejně tak z něj i čteme.

Pokud v Javě založíme prázdné číselné pole, je automaticky naplněno nulami.

Seznamy (Listy)

Seznamy (anglicky a často i česky Listy) jsou kolekce, které umožňují prvky za běhu programu přidávat a mazat. Mohou být číselně indexované jako pole, ale také nemusí. Jsou v zásadě 2 typy seznamů.

Seznamy s polem

Seznam nejčastěji využívá toho, že ačkoli velikost pole nemůžeme za běhu programu měnit, můžeme za běhu vytvořit pole nové.

Seznam je poté třída, která obsahuje metody pro přidání a odstranění prvků (a mnoho dalších, pro nás nyní nepodstatných metod). Třída v podstatě obaluje pole a obsahuje navíc proměnnou, kde si uchovává počet prvků. Při vytvoření instance se vytvoří pole např. o 12ti prvcích a proměnná s počtem prvků se nastaví na 0. Při přidání prvního prvku se prvek vloží na 1. index v poli a počet prvků se inkrementuje. Takto můžeme přidat až 12 prvků, než pole naplníme. Ve chvíli, kdy vyčerpáme kapacitu pole, jednoduše vytvoříme nové, třeba 2x větší. Prvky ze starého pole do něj zkopírujeme a staré pole zahodíme. Až se toto nové pole opět naplní, budeme situaci opakovat. Takovýmto způsobem opravdu interně funguje kolekce ArrayList, se kterou jsme doteď pracovali. ArrayList si můžeme představit asi takto:

Seznam na obrázku má 8 prvků. Prvky jsou uloženy v interním poli, které má prvků 12. Poslední 4 prvky se nevyužívají a seznam se zvenku tváří, jako že tam nejsou.

Výhodou je rychlost přístupu k prvkům pomocí indexů díky využití pole. Nevýhodou je samozřejmě časová prodleva nutná k vytvoření nového pole a překopírování prvků, i když nastává jen občas. Další, i když méně bolestivou nevýhodou, je, že kolekce zabírá v paměti více prostoru, než je nutné. Tento typ seznamu je přesto nejpoužívanější kolekcí v Javě a je poměrně dobře optimalizován.

Seznam s polem je tedy v Javě zastoupen třídou ArrayList. Na obrázku níže je vidět kompletní hierarchie třídy ArrayList:

Jak vidíme, ArrayList implementuje mimo jiné rozhraní List.

Metody a další prvky na třídě List

Popišme si důležité metody na tomto rozhraní. List tvoří základ pro všechny seznamy v Javě a obsahuje zejména následující metody:

• add(), addAll() - Pro přidání nových prvků do listu máme dvě metody. První z nich přidá jeden prvek, jenž uvedeme v parametru. Druhá, jak název napovídá, přidá více prvků. Jako parametr tudíž bere jinou kolekci.
• clear() - Metoda clear() vymaže všechny prvky.
• contains() - Pomocí metody contains() zjišťujeme, zda list obsahuje daný prvek. Získáme hodnotu typu boolean.
• toArray() - Další metoda zkopíruje prvky z listu do pole.
• remove(), removeAll() - Pro mazání prvků z kolekce máme také dvě metody. Fungují podobně, jako add() a addAll(). Obě jsou velmi užitečné v případě, že máme v listu instance nějaké třídy (např. uživatele), nemusíme si držet jejich číselné indexy, jen zavoláme např. list.remove(karel), kdy předáme konkrétní instanci, která se má ze seznamu odebrat.
• retainAll() - Metoda retainAll() umožňuje porovnávat dvě kolekce a zachová pouze prvky, které mají společné.
• size() - Pro zjištění počtu prvků v kolekci voláme metodu size().

Metoda add() má dvě přetížení. V jednom případě přijímá pouze přidávaný objekt, ve druhém případě přijímá ještě index, na který se má prvek vložit. Metoda remove() má také dvě přetížení. Jednou přijímá objekt, který se má odstranit, v případě druhém přijímá index, na kterém má prvek odstranit.

Ačkoli jsme si ArrayList vyzkoušeli již 1000krát, pro úplnost si přeci jen ukažme několik řádků kódu:

List<Integer> list = new ArrayList<>();
list.add(5);
list.add(10);
System.out.println(list.get(0));

Výstup programu:

5

Kód výše vytvoří ArrayList typu Integer, přidá do něj 2 čísla a poté vypíše první prvek do konzole. Pracujeme s indexy jako bychom pracovali s polem, ale můžeme do něj za běhu programu přidávat prvky a také je mazat.

Všimněte si, že používáme seznam typu Integer na ukládání typů int. V Javě není možné typovat generický typ primitivním datovým typem. Místo toho je potřeba použít tzv. obalové třídy (wrappery), které byly vytvořeny právě pro účely použití těchto typů v kolekcích. Jsou to Byte, Short, Integer, Long, Boolean, Character, Float a Double. Konverze mezi primitivními datovými typy a jejich obalovými třídami probíhá automaticky.

Dále List nabízí metody:

• indexOf() - Získáme index prvního výskytu daného prvku v listu.
• lastIndexOf() - Obdoba metody indexOf() vrací index posledního výskytu daného prvku v listu.
• removeIf() - Tato metoda odstraní všechny prvky, které odpovídají dané podmínce (predikátu, viz dále v kurzu).
• sort() - Metoda sort() setřídí list. Je důležité, aby jeho prvky implementovaly rozhraní Comparable, jinak metoda vyvolá výjimku. Základní třídy a struktury z Javy rozhraní Comparable implementují, u svých tříd ho umíme dodat.

Až na několik metod jsme si popsali celý ArrayList, kompletní výčet najdete v oficiální dokumentaci.

Vyzkoušejte si další metody jako sort() a podobně. Detailnější práci s kolekcemi se budeme ještě věnovat, až se dostaneme k technologii Stream API.

V příští lekci, Spojový seznam v Javě, si uvedeme druhý typ seznamu, kterým je spojový seznam.

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.