3. diel - Zoznam (list) pomocou poľa v Jave

V minulej lekcii, Java Collections Framework, sme sa pozreli, ako na jazyk Java implementovanej kolekcie v rámci Java Collections Frameworku.

Dnes sa budeme v Java tutoriáli venovať prvej kolekcii, zoznamom (listom). To je typ kolekcií, s ktorým sme sa počas kurzu už stretli.

Pole

Urobme si na začiatku malú odbočku späť k poľu, ktoré bolo prvou "kolekciou", ktorú sme v kurze spoznali. Pole sa vyznačuje tým, že má pevne daný počet prvkov. Z tohto dôvodu niekedy ani nebýva považované za kolekciu, pretože nespĺňa časť jej definície. Prvky v poli sú číselne indexované, a to od nuly.

Hlavnou nevýhodou poľa teda je, že do neho nemôžeme počas spustenej aplikácie prvky pridávať ani ich mazať. To bohužiaľ často potrebujeme, aj keď sú situácie, keď je pole ideálna voľba. Túto daň však vyvažuje obrovská rýchlosť, s ktorou môžeme s prvky poľa pracovať. Keďže dáta sú rovnakého typu (či už majú úplne rovnakého, alebo spoločného predka), zaberajú v pamäti rovnako veľa miesta. Jednotlivé prvky poľa sú v pamäti uložené za sebou v rade, ktorý je neprerušený. Pole celých čísel si môžeme predstaviť napr. takto:

Pokiaľ teda chceme napr. prejsť k 5. prvku, len vstúpime tam, kde pole začína, a potom odskočíme 4 násobky veľkosti typu (tu int) ďalej. Sme na 5. prvku. Čítanie a zápis na indexe v poli má teda konštantnú časovú zložitosť. Pokiaľ vás tento termín zmiatol, môžete to chápať tak, že do poľa zapisujeme okamžite a rovnako aj z neho čítame.

Pokiaľ v Jave založíme prázdne číselné pole, je automaticky naplnené nulami.

Zoznamy (listy)

Zoznamy (anglicky a často tiež v slovenčine listy) sú kolekcie, ktoré umožňujú prvky za pochodu programu pridávať a mazať. Môžu byť číselne indexované ako pole, ale tiež nemusia. Existujú v zásade dva typy zoznamov.

Zoznamy s poľom

Zoznam najčastejšie využíva to, že hoci veľkosť poľa nemôžeme za pochodu programu meniť, môžeme však vytvoriť pole nové.

Zoznam je trieda, ktorá obsahuje metódy na pridanie a odstránenie prvkov (a mnoho ďalších, pre nás teraz nepodstatných metód). Trieda v podstate obaľuje pole a obsahuje navyše premennú, pričom si uchováva počet prvkov. Pri vytvorení inštancie sa vytvorí pole napr. o 12 prvkoch a premenná s počtom prvkov sa nastaví na 0. Pri pridaní prvého prvku sa prvok vloží na 1. index v poli a počet prvkov sa inkrementuje. Takto môžeme pridať až 12 prvkov, kým pole naplníme. Vo chvíli, keď vyčerpáme kapacitu poľa, jednoducho vytvoríme nové, napríklad 2-krát väčšie. Prvky zo starého poľa do neho skopírujeme a staré pole zahodíme. Keď sa toto nové pole opäť naplní, budeme postup opakovať. Takýmto spôsobom funguje interne kolekcia ArrayList, s ktorou sme doteraz pracovali. ArrayList si môžeme predstaviť asi takto:

Zoznam na obrázku má osem prvkov. Prvky sú uložené v internom poli, ktoré má 12 prvkov. Posledné štyri prvky sa nevyužívajú a zoznam navonok vyzerá, akoby tam neboli.

Výhodou je rýchlosť prístupu k prvkom pomocou indexov vďaka využitiu poľa. Nevýhodou je samozrejme časové oneskorenie potrebné na vytvorenie nového poľa a prekopírovanie prvkov, aj keď to nastáva len občas. Ďalšou, aj keď menej podstatnou nevýhodou je, že kolekcia zaberá v pamäti viac priestoru, než je nutné. Tento typ zoznamu je napriek tomu najpoužívanejšou kolekciou v Jave a je pomerne dobre optimalizovaný.

Zoznam s poľom je teda v Jave zastúpený triedou ArrayList. Na obrázku nižšie je vidieť kompletnú hierarchiu triedy ArrayList:

Ako vidíme, ArrayList implementuje okrem iného rozhranie List.

Metódy a ďalšie prvky na triede List

Popíšme si dôležité metódy v tomto rozhraní. List tvorí základ pre všetky zoznamy v Jave a obsahuje najmä nasledujúce metódy:

• add(), addAll() – Na pridanie nových prvkov do listu máme dve metódy. Prvá z nich pridá jeden prvok, ktorý uvedieme v parametri. Druhá, ako názov napovedá, pridá viac prvkov. Ako parameter teda berie inú kolekciu.
• clear() – Metóda clear() vymaže všetky prvky.
• contains() – Pomocou metódy contains() zisťujeme, či list obsahuje daný prvok. Získame hodnotu typu boolean.
• toArray() – Ďalšia metóda skopíruje prvky z listu do poľa.
• remove(), removeAll() – Na mazanie prvkov z kolekcie máme aj dve metódy. Fungujú podobne ako add() a addAll(). Obe sú veľmi užitočné v prípade, že máme v liste inštancie nejakej triedy (napr. používateľa), nemusíme si držať ich číselné indexy, len zavoláme napr. list.remove(karel), kedy odovzdáme konkrétnu inštanciu, ktorá sa má zo zoznamu odobrať.
• retainAll() – Metóda retainAll() umožňuje porovnávať dve kolekcie a zachová iba prvky, ktoré majú spoločné.
• size() – Na zistenie počtu prvkov v kolekcii voláme metódu size().

Metóda add() má dve preťaženia. V jednom prípade prijíma iba pridávaný objekt, v druhom prípade prijíma ešte index, na ktorý sa má prvok vložiť. Metóda remove() má tiež dve preťaženia. Raz prijíma objekt, ktorý sa má odstrániť, v prípade druhom prijíma index, na ktorom má prvok odstrániť.

Hoci sme si ArrayList vyskúšali už 1000-krát, pre úplnosť si predsa len ukážme niekoľko riadkov 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 vyššie vytvorí ArrayList typu Integer, pridá doň dve čísla a potom vypíše prvý prvok do konzoly. Pracujeme s indexmi, ako by sme pracovali s poľom, ale môžeme do neho za pochodu programu pridávať prvky a tiež ich mazať.

Všimnite si, že používame zoznam typu Integer na ukladanie typov int. V Jave nie je možné typovať generický typ primitívnym dátovým typom. Namiesto toho je potrebné použiť tzv. obalové triedy (wrappery), ktoré boli vytvorené práve na účely použitia týchto typov v kolekciách. Sú to Byte, Short, Integer, Long, Boolean, Character, Float a Double. Konverzia medzi primitívnymi dátovými typmi a ich obalovými triedami prebieha automaticky.

Ďalej List ponúka metódy:

• indexOf() – Získame index prvého výskytu daného prvku v liste.
• lastIndexOf() – Obdoba metódy indexOf() vracia index posledného výskytu daného prvku v liste.
• removeIf() – Táto metóda odstráni všetky prvky, ktoré zodpovedajú danej podmienke (predikátu, viď ďalej v kurze).
• sort() – Metóda sort() zoradí list. Je dôležité, aby jeho prvky implementovali rozhranie Comparable, inak metóda vyvolá výnimku. Základné triedy a štruktúry z Javy rozhranie Comparable implementujú, pri svojich triedach ho vieme dodať.

Až na niekoľko metód sme si popísali celý ArrayList, kompletný zoznam nájdete v oficiálnej dokumentácii.

Vyskúšajte si ďalšie metódy, ako sort() a podobne. Podrobnejšej práci s kolekciami sa budeme ešte venovať, keď sa dostaneme k technológii Stream API.

V budúcej lekcii, Spojový zoznam v Jave, si uvedieme druhý typ zoznamu, ktorým je spojový zoznam.

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.