Spojové zoznamy v Jave - 2. časť

V minulom tutoriále sme si ukázali ako používať triedu LinkedList a máte už nejakú predstavu ako tieto veci fungujú. Dnes si vytvoríme vlastný jednosmerný spájať zoznam.

SingleLinkedList

Najskôr budeme potrebovať triedu Node. Ktorá bude mať 2 privátne atribúty a konštruktor, ktorý bude inicializovať hodnotu v danom uzle. Hodnotu priradí z parametra a môže to byť v našom prípade iba celočíselný dátový typ (int). Ďalej bude mať 2 metódy, ktoré budú pracovať z referencií. Metóda setNext, ktorá uzla nastaví referenciu na ďalší uzol a metóda getNext, ktorá bude vracať referenciu na ďalší uzol. Nakoniec metódu getValue, ktorá nám vráti hodnotu daného uzla (prvku).

Třída Node:

public class Node {

    private int value;
    private Node next;

    /**
     * konstruktor třídy Node
     * @param číselná hodnola
     */
    public Node(int number){
       this.value = number;
    }

    /**
     * nastaví uzlu odkaz na další uzel
     * @param uzel
     */
    public void setNext(Node uzel){
        next = uzel;
    }

    /**
     * metoda vrací odkaz uzlu na další uzel
     * @return odkaz
     */
    public Node getNext(){
        return next;
    }

    public int getValue(){
        return value;
    }
}

Ďalej si vytvoríme triedu SingleLinkedList, vytvoríme konštruktor a metódy size a isEmpty:

public class SingleLinkedList {

    //první položka seznamu
    private Node first;
    //poslední položka seznamu
    private Node last;
    //velikost seznamu
    private int size;

    /**
     * Konstruktor Jednosměrného spojového seznamu
     */
    public SingleLinkedList(){
        size = 0;
    }

    /**
     * metoda, která vcasí velikost seznamu
     * @return velikost seznamu
     */
    public int size(){
        return size;
    }


    /**
     * metoda vrací logickou hodnotu naplnění pole. Pokud je pole prázdné vrací hodnotu false
     * Pokud je v poli minimálně jeden prvek vrací hodnotu true
     * @return true || false
     */
    public boolean isEmpty(){
        return (size == 0);
    }
}

Trieda je zatiaľ jednoduchá a nie je snáď čo vysvetľovať. Ďalej musíme vytvoriť metódu, ktorá nám pridá číslo do nášho zoznamu. Bude sa volať add a bude fungovať na princípe, že si vytvorí nový uzol. Otestuje, či je zoznam prázdny pomocou našu metódy isEmpty. Ak pridáme prvú položku, priradíme uzol prvému a poslednému uzla. V opačnom prípade nastavím odkaz poslednému uzla na práve vytvorený uzol a ten priradíme premenné last (vytvoríme nový posledný uzol).

public class SingleLinkedList {

    //atributy třídy
    //metody třídy

    public void add(int cislo){
       Node uzel = new Node(cislo);
       if(isEmpty()){
          first = uzel;
          last = uzel;
       }
       else{
          last.setNext(uzel);
          last = uzel;
       }
       size++;
    }
}

Ako ďalšie budeme potrebovať metódu, ktorá nám prvok zo zoznamu odoberie. Nazveme ju remove. Táto metóda dostane v parametri index, ktorý najskôr otestuje. Pokiaľ nebude index menší ako počet prvkov, alebo bude menší ako 0, vyvolajú sa potrebné výnimky. Ďalej otestuje, či budeme odstraňovať prvý uzol. Ak áno, nastavíme prvému uzla, jeho vlastné referenciu a tým ho vlastne vymažeme zo zoznamu. Ak nie, nájdeme v zozname predchádzajúcej uzol, ktorý sa nachádza pred mazaným prvkom a tomu nastavíme referenciu na mazaný prvok. Ak budeme mazať posledný uzol, tak premenné last nastavíme prvok predošlý.

Pridajme si do triedy SingleLinkedList nasledujúce metódu:

public class SingleLinkedList {

//atributy třídy
//metody třídy

     /**
     * smaže prvek na zvoleném indexu
     * @param index
     */
    public void remove(int index){
        if(index >= size)
            throw new IndexOutOfBoundsException("Přesáhli jste limit. Index nesmí být menší než "+size);
        if(index < 0)
            throw new IllegalArgumentException("Index nesmí být menší než 0!");
        if(index == 0)
            first = first.getNext();
        else{
            Node node = first;
            for(int i = 0; i < index-1; i++)
                node = node.getNext();
            node.setNext(node.getNext().getNext());
            if (index == (size - 1))
                last = node;
        }
        size--;
    }
}

Tak a nakoniec by sa iste hodila metóda, ktorá vracia hodnotu podľa daného indexu. Túto metódu pomenujeme get, ktorú ďalej ešte popíšem a rovno si pridáme do triedy metódu toString, aby sme mohli zoznam jednoducho vypísať.

Public class SingleLinkedList{

  //atributy třídy
  //metody třídy

  /**
     * Vrátí hodnotu uzlu pod zvoleným indexem
     * @param index
     * @return číselná hodnota indexu
     */

    public int get(int i) {

        if (i >= size) {
        throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
        }
        if (i < 0) {
        throw new IllegalArgumentException("Index mensi nez 0");
        }
        Node node = first;
        for (int j = 0; j < i; j++) {
        node = node.getNext();
        }
    return node.getValue();
}

@Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node node = first;
        for (int i = 0; i < this.size; i++) {
        builder.append(node.getValue());
        builder.append(" ");
        node = node.getNext();
        }
        return builder.toString();
    }
}

Metóda get rovnako ako metóda remove overí, či bol zadaný platný index. Ďalej si vytvoríme nový uzol a priradíme mu premennú first (prvý uzol v zozname) a pekne postupne pomocou cyklu hľadá daný prvok.

Trieda je kompletný a teraz si ju môžeme otestovať. Kód pre testovanie triedy môže vyzerať napríklad takto:

public class Test {
    public static void main (String args[]){
       try{
       SingleLinkedList seznam = new SingleLinkedList();
       //naplnění hodnotami
       seznam.add(1);
       seznam.add(2);
       seznam.add(3);
       seznam.add(4);
       seznam.add(5);
       seznam.add(6);
       seznam.add(7);

       //vymaže se 4-tý prvek
       seznam.remove(3);

       seznam.add(80);
       System.out.println(seznam);
       System.out.println("Velikost seznamu = "+seznam.size());
       System.out.println("Třetí položka seznamu = "+seznam.get(2));
       }
       catch(IllegalArgumentException | IndexOutOfBoundsException e){
          System.out.println(e.getMessage());
       }
    }
}

Najskôr vytvoríme náš zoznam a naplníme ho hodnotami 1 až 7. Ďalej vymastíme prvok na pozícii 4 pomocou funkcie remove a indexu 4. Ak si dobre pamätáte, tak som už spomínal, že tento zoznam sa indexuje od 0 rovnako ako pole. Vďaka tomu že sme v našej triede prepísali metódu toString, si môžeme našu kolekciu vypísať pomocou príkazu System.out.prin­tln.

Tak a to je pre dnešok všetko. Ak sa niekde zaseknete a nebudete môcť nájsť chybu, tak si Stiahnite zdrojové kódy a chybu určite nájdete.