4. diel - Spojový zoznam v Jave

V minulej lekcii, Zoznam (list) pomocou poľa v Jave, sme si predstavili kolekciu zoznamy (listy) a detailne popísali zoznamy pomocou poľa a triedu ArrayList.

Dnes sa v Java tutoriáli zameriame na druhý typ zoznamu, ktorým je spojový 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, v ktorom 1. prvok ukazuje na druhý, druhý na tretí a tak ďalej. Prvky z minulého príkladu by sme si v spojovom zozname mohli predstaviť napr. takto:

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

Pri spojových zoznamoch 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 prejsť 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ýhodnou. 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 pochodu programu pridávať a mazať tak dlho, pokiaľ nám na to bude stačiť pamäť. Pomerne dobre môžeme aj mazať prvky uprostred zoznamu alebo vkladať nové prvky medzi existujúce. Pri poli bolo vloženie prvku možné iba tak, že sme všetky prvky napravo posunuli a vytvorili tak miesto pre nový prvok. To nás stálo nemalý výpočtový čas, ktorý bol závislý od počtu prvkov. V spojovom zozname jednoducho prvok naodkazujeme medzi dva existujúce, ostatných prvkov sa zmena nedotkne.

Získame 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 spojový zoznam a zoznam cez pole sa veľmi líšia. Pokiaľ budeme často pristupovať k prvkom pomocou indexu, bol by spojový zoznam katastrofou. Pokiaľ budeme naopak prvky často vkladať alebo mazať uprostred kolekcie, spojový zoznam si s tým hravo poradí a list s poľom by bol extrémne pomalý.

LinkedList

Spojový zoznam je v Jave reprezentovaný generickou kolekciou LinkedList. Jedná sa o spojový zoznam obojsmerný, jednosmerný spojový 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 nepatrná. Na obrázku nižšie je opäť vidieť kompletnú hierarchiu tried spojového zoznamu:

LinkedList neobsahuje rovno naše prvky tak, ako tomu bolo pri ArrayListu, ale sú v ňom uložené položky typu Node. Sú to uzly, ktoré na seba navzájom ukazujú (či odkazujú) a disponujú vlastnosťou 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 ArrayListu 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 pri ArrayListu:

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

Výstup programu:

6
10

Vytvoríme nový spojový 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:

// initializing and filling the linked list
LinkedList<Integer> list = new LinkedList<>();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);

// adding and deleting in the middle of the list
list.add(3, 32);
list.add(3, 31);
list.remove(2);

// printing the list
for (Integer i : list) {
    System.out.print(i + ", ");
}

Výstup:

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

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

Dnes to bolo trochu kratšie, ale nechceli sme začínať na konci novú tému.

V nasledujúcom kvíze, Kvíz – Genericita, zoznam a spojový zoznam v Jave, si vyskúšame nadobudnuté skúsenosti z predchádzajúcich lekcií.

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