Spojové zoznamy v Jave - LinkedList

Teória

Spájať zoznam je kontajner objektov a je to jedna z najefektívnejších štruktúr, ak budeme často zapisovať na začiatok alebo na koniec zoznamu. Jednotlivé prvky tu nemajú žiadne indexy, ale jednoducho na seba po sebe idúce prvky odkazujú. Tieto spojové zoznamy slúžia prevažne na ukladanie dát vopred neznáme dĺžky. Základom týchto zoznamov je uzol čiže Node, ktorý odkazuje na ďalší prvok v zozname.

Výhody a nevýhody spojovaceho zoznamu

Najväčšou výhodou spojovaceho zozname je rýchle a efektívne pridávanie prvku na koniec alebo začiatok zoznamu. Rovnako tak to platí aj pre mazanie prvkov.

Jedna z najväčších nevýhod spojovaceho zozname je, že nemôžeme efektívne pristúpiť k prvku uprostred radu, ale musíme zoznam prehľadávať postupne celý, ktoré nájde náš n-tý prvok.

Delenie

Jednosmerný spájať zoznam

Anglicky (Single Linked List) - Je to jedna zo základných a najjednoduchších spojových dátových štruktúr, keď každý jednotlivý dátový uzol (node) obsahuje svoje dáta a odkaz na ďalšiu položku zoznamu. Posledná položka neobsahuje žiaden odkaz ale len hodnotu null. Preto tiež jednosmerný

Obojsmerný spájať zoznam

Anglicky (Double Linked List) - Je to efektívnejšie a používanejšej variant spojovaceho zoznamu. Jednotlivé prvky obsahujú okrem svojich dát tiež odkaz na predošlý a nasledujúce prvok.

Linked List

V Jave je obojsmerný spájať zoznam reprezentovaný triedou LinkedList. Umožňuje napríklad pridávať položky na poslednú pozíciu zoznamu, alebo na začiatok zoznamu s tým, že všetky ostatné prvky sa posunú o jednu pozíciu ďalej. Ak by ste z nejakého dôvodu po dokončení operácií vkladanie / mazanie ďalej nechceli pracovať so zoznamom a chceli by ste radšej použiť pole, tak nezúfajte. Jednoducho môžete zo zoznamu urobiť pole pomocou metódy toArray () a ďalej už s jednotlivými prvkami môžete pracovať tak, ako ste zvyknutí. Všetky operácie fungujú ako u dvojitého spojovaceho zoznamu. Pokiaľ uvedieme u nejakej funkcie index (get, set), bude sa prechádzať zoznam od začiatku alebo od konca, podľa toho, čo je bližšie k určenému indexu.

Konštruktory

• new LinkedList (); - bezparametrický konštruktor
• new LinkedList (Collection c); - vytvorí nový spájať zoznam a naplní ho položkami z danej kolekcie

Metódy

1. add () - pridá položku na ďalšiu pozíciu
2. addFirts (param) - pridá položku na začiatok zoznamu
3. addLast (param) - pridá položku na koniec zoznamu
4. addAll (Colection) - pridá do zoznamu celú kolekciu (všetky položky, ktoré obsahuje pôvodnú zoznam)
5. removeFirst () - odstráni prvú položku v zozname
6. removeLast () - odstráni poslednú položku v zozname
7. get (index) - vráti prvok na danej pozícii
8. getFirst () - vráti prvú položku v zozname
9. getLast () - vráti poslednú položku v zozname
10. set (index, param) - prepíše pôvodnú položku na danom indexe.
11. contains (param) - vráti hodnotu true, ak sa v zozname nachádza daná položka. V opačnom prípade vracia hodnotu false
12. size () - metóda vracia počet položiek zoznamu
13. toArray () - vráti pole naplnené položkami spojovaceho zoznamu

Pre predstavu ako táto kolekcia funguje prikladám okomentovaný kód jednoduché aplikácie:

package javalinkedlist;

import java.util.LinkedList;

public class JavaLinkedList {

    public static void main(String[] args) {
       //vytvoření seznamu
       LinkedList seznam = new LinkedList();
       //naplnění hodnotami
       seznam.add(1);
       seznam.add(2);
       seznam.add(3);
       seznam.add(4);
       seznam.add(5);
       seznam.add(6);
       seznam.add(7);
       // odstranění a přidání prvku na poslední pozici
       seznam.removeLast();
       seznam.addLast(8);
       //odstraňení a přidání prvku na první pozici
       seznam.removeFirst();
       seznam.addFirst(0);

       //vypsání seznamu
       System.out.println(seznam);

       //vložení 2 hodnot doprostřed seznamu
       seznam.add(Math.round(seznam.size()/2),13);
       seznam.add(Math.round(seznam.size()/2),15);
       //přepsání hodnot
       seznam.set(1, 20);

       //vypsání seznamu
       System.out.println(seznam);

       //pokud se číslo vyskytuje v seznamu vypíše ho, v opačném případě jej do seznamu zapíše a vypíše jeho pozici
       int cislo = 18;
       if(seznam.contains(cislo)){
           System.out.println(cislo);
       }
       else{
           seznam.addLast(cislo);
           System.out.printf("Index čísla %s je %s \n", cislo, seznam.indexOf(cislo));
       }

       //získání první a podlední hodnoty v seznamu
       int prvni = (int) seznam.getFirst();
       int posledni = (int) seznam.getLast();
    }
}

Nakoniec len doplním, že zoznam sa indexuje od 0, rovnako ako pole. Tak ao dvojsmernom spájať zoznamu už máte určitú predstavu. Viete ho používať a to je pre vás najdôležitejšia. Možno sa medzi čitateľmi nájde aj časť ľudí, ktorí by chceli vedieť ako to funguje "pod pokrievkou". Pre týchto ľudí mám pripravený ďalší diel, v ktorom sa týmito vecami budeme zaoberať viac do hĺbky a v ktorom si spoločne vytvoríme jednoduchý SingleLinkedList a ukážeme si ako to všetko vlastne funguje.

Pre dnešok ste sa naučili používať obojsmerný spájať zoznam v podobe triedy LinkedList, ktorú má java už v základe v balíčku java.util. Jednosmerný spájať zoznam Java neobsahuje a preto si ukážeme ako si ho vytvoriť a po prečítaní ďalšieho tutoriálu budete vedieť ako to celé vlastne funguje. Pod článkom sú ako vždy priložené zdrojové kódy, takže keby Vám čokoľvek nešlo a nemohli ste nájsť chybu tak si ich stiahnite a hľadajte riadok po riadku