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š.
Stiahnuť
Stiahnutím nasledujúceho súboru súhlasíš s licenčnými podmienkami
Stiahnuté 221x (1.98 kB)
Aplikácia je vrátane zdrojových kódov v jazyku Java