4. diel - Spájať zoznam v Jave

V minulej lekcii, Zoznam (List) pomocou poľa v Jave , sme si predstavili zoznamy (listy), detailne opísali zoznam pomocou poľa a triedu ArrayList. Dnes sa v Java tutoriálu zameriame na druhý typ zoznamu, ktorým je spájať zoznam.

Spojové zoznamy

Druhou možnosťou vytvorenia zoznamu s premenným počtom prvkov sú tzv. Spojové zoznamy. Tie už s poľom vôbec nepracujú a sú založené na odlišnom princípe. Jednotlivé prvky v liste sú v pamäti rôzne rozhádzané (už teda nie sú uložené za sebou) a po sebe idúce prvky na seba odkazujú. Môžeme si to predstaviť ako taký reťazec, kedy 1. prvok ukazuje na druhý, druhý na tretí a tak ďalej. Prvky z minulého príkladu by sme si vo spájať zozname mohli predstaviť napr. Nasledovne:

Takému spojovému zoznamu sa hovorí jednosmerný (Single Linked List). Ak nemáme nejaký vážny dôvod šetriť pamäťou, zvyčajne na seba 2 po sebe idúce prvky ukazujú navzájom (teda aj 2. na prvú a tak ďalej). Hovoríme o obojsmernom spájať zoznamu (double Linked List). Ten by v našom prípade vyzeral nejako takto:

U spojových zoznamov sme prišli o možnosť rýchlo pristúpiť k prvku podľa jeho indexu a to kvôli tomu, že prvky už nie sú v pamäti za sebou. Neexistuje spôsob, ako efektívne preskočiť rovno napr. Na 100. prvok a prečítať jeho hodnotu. Keď chceme k 100. prvku pristúpiť, musíme z prvého prvku na druhý, z druhého na tretí a tak ďalej až do stovky. Časová zložitosť čítania a zápisu na index teda záleží na počte prvkov v liste.

Niekedy však nepotrebujeme prvky indexovať a v tej chvíli sa táto kolekcia stáva veľmi výhodnú. Už na začiatku sme si povedali, že s poľom vôbec nepracujeme. Už nie sme nijako obmedzení dĺžkou zoznamu a položky môžeme za behu programu pridávať a mazať tak dlho, kým nám bude stačiť pamäť. Pomerne dobre môžeme aj mazať prvky uprostred zoznamu alebo vkladať nové prvky medzi existujúce. U pole bolo vloženie prvku možné len tak, že sme všetky prvky napravo posunuli a vytvorili tak priestor pre nový prvok. To nás stálo nemalý výpočtový čas, ktorý bol závislý na počte prvkov. Vo spájať zoznamu iba prvok naodkazujeme medzi 2 existujúcej, ostatných prvkov sa zmena nedotkne.

Máme teda efektívne vkladanie a mazanie prvkov na úkor neefektívneho prístupu na indexy. Tak už to u dátových štruktúr a algoritmov vôbec býva, niečo za niečo

Vidíme, že spájať zoznam a zoznam cez pole sa veľmi líšia. Ak budeme často pristupovať k prvkom pomocou indexu, bol by spájať zoznam katastrofou. Ak budeme naopak prvky často vkladať alebo mazať uprostred kolekcie, spájať zoznam si s tým hravo poradí a list s poľom by bol extrémne pomalý.

LinkedList

Spájať zoznam je v Jave reprezentovaný generickú kolekcií LinkedList. Jedná sa o spájať zoznam obojsmerný, jednosmerný spájať zoznam v Jave nenájdeme. Mohli by sme si ho naprogramovať, ale nemá to príliš význam, pretože sa s ním horšie pracuje a úspora pamäte je mizivá. Na obrázku nižšie je opäť vidieť kompletný hierarchie tried spojovaceho zoznamu:

LinkedList neobsahuje rovno naše prvky ako tomu bolo u ArrayList u, ale sú v ňom uložené položky typu Node. Sú to uzly, ktoré na seba navzájom ukazujú (odkazujú sa, ak chcete) a disponujú vlastností item. Práve v tej je ešte len uložený náš prvok, ktorý uzol obaľuje. Dodáva tak nášmu prvku ony väzby na prvky okolité. Ukážme si metódy, ktoré má LinkedList oproti klasickému ArrayList u navyše:

• addFirst() - Pridá nový prvok na začiatok zoznamu.
• addLast() - Pridá nový prvok na koniec zoznamu.
• getFirst() - Vráti prvý prvok.
• getLast() - Vráti posledný prvok.
• removeFirst() - Odstráni prvý prvok.
• removeLast() - Odstráni posledný prvok.

Príklad

Vyskúšajme si podobný príklad ako u ArrayList u:

LinkedList<Integer> seznam = new LinkedList<>();
seznam.add(5);
seznam.addFirst(6);
seznam.addLast(10);
System.out.println(seznam.getFirst());
System.out.println(seznam.getLast());

Výstup programu:

6
10

Vytvoríme nový spájať zoznam typu Integer. 1. prvok pridáme štandardnou metódou add(). Číslo 6 pridáme metódou addFirst(), čím sa dostane na začiatok zoznamu. Metódou addLast() pridáme 3. prvok. Nakoniec vypíšeme prvý a posledný prvok.

Skúsme si ešte ono rýchle vkladanie a mazanie prvkov:

// inicializace a naplnění spojového seznamu
LinkedList<Integer> seznam = new LinkedList<>();
seznam.addLast(1);
seznam.addLast(2);
seznam.addLast(3);
seznam.addLast(4);
seznam.addLast(5);

// přidávání a mazání v prostředku seznamu
seznam.add(3, 32);
seznam.add(3, 31);
seznam.remove(2);

// výpis seznamu
for (Integer i : seznam) {
    System.out.print(i + ", ");
}

výstup:

1, 2, 31, 32, 4, 5,

Po "spojáku" siahneme hlavne v prípade, keď chceme často vkladať a mazať prvky doprostred zoznamu, čo by u ArrayList u bolo veľmi pomalé.

Dnes to bolo trochu kratšie, ale nechcel som začínať na konci novú tému. V budúcej lekcii, Viacrozmerné polia v Jave , sa pozrieme na viacrozmerné pole.

V budúcej lekcii, Viacrozmerné polia v Jave , sa teda uvidíme pri viacrozmerných poliach.

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š.