Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Spojové seznamy v Javě - 2. část

V minulém tutoriálu jsme si ukázali jak používat třídu LinkedList a máte již nějakou představu jak tyhle věci fungují. Dnes si vytvoříme vlastní jednosměrný spojový seznam.

SingleLinkedList

Nejdříve budeme potřebovat třídu Node. Která bude mít 2 privátní atributy a konstruktor, který bude inicializovat hodnotu v daném uzlu. Hodnotu přiřadí z parametru a může to být v našem případě pouze celočíselný datový typ(int). Dále bude mít 2 metody, které budou pracovat z referencí. Metoda setNext, která uzlu nastaví referenci na další uzel a metoda getNext, která bude vracet referenci na další uzel. Nakonec metodu getValue, která nám vrátí hodnotu daného uzlu(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;
    }
}

Dále si vytvoříme třídu SingleLinkedList, vytvoříme konstruktor a metody 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);
    }
}

Třída je zatím jednoduchá a není snad co vysvětlovat. Dále musíme vytvořit metodu, která nám přidá číslo do našeho seznamu. Bude se jmenovat add a bude fungovat na principu, že si vytvoří nový uzel. Otestuje, zda je seznam prázdný pomocí naši metody isEmpty. Pokud přidáme první položku, přiřadíme uzel prvnímu a poslednímu uzlu. V opačném případě nastavím odkaz poslednímu uzlu na právě vytvořený uzel a ten přiřadíme proměnné last (vytvoříme nový poslední uzel).

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++;
    }
}

Jako další budeme potřebovat metodu, která nám prvek ze seznamu odebere. Nazveme ji remove. Tato metoda dostane v parametru index, který nejdříve otestuje. Pokud nebude index menší než počet prvků, nebo bude menší než 0, vyvolají se potřebné výjimky. Dále otestuje, zda budeme odstraňovat první uzel. Pokud ano, nastavíme prvnímu uzlu, jeho vlastní referenci a tím ho vlastně vymažeme ze seznamu. Pokud ne, najdeme v seznamu předchozí uzel, který se nachází před mazaným prvkem a tomu nastavíme referenci na mazaný prvek. Pokud budeme mazat poslední uzel, tak proměnné last nastavíme prvek předešlý.

Přidejme si do třídy SingleLinkedList následující metodu:

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 nakonec by se jistě hodila metoda, která vrací hodnotu podle daného indexu. Tuto metodu pojmenujeme get, kterou dále ještě popíšu a rovnou si přidáme do třídy metodu toString, abychom mohli seznam jednoduše vypsat.

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();
    }
}

Metoda get stejně jako metoda remove ověří, zda byl zadán platný index. Dále si vytvoříme nový uzel a přiřadíme mu proměnnou first(první uzel v seznamu) a hezky postupně pomocí cyklu hledá daný prvek.

Třída je kompletní a teď si jí můžeme otestovat. Kód pro testování třídy může vypadat například takhle:

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());
       }
    }
}

Nejdříve vytvoříme náš seznam a naplníme ho hodnotami 1 až 7. Dále vymažeme prvek na pozici 4 pomocí funkce remove a indexu 4. Pokud si dobře pamatujete, tak jsem již zmiňoval, že tento seznam se indexuje od 0 stejně jako pole. Díky tomu že jsme v naší třídě přepsali metodu toString, si můžeme naši kolekci vypsat pomocí příkazu System.out.prin­tln.

Tak a to je pro dnešek vše. Pokud se někde zaseknete a nebudete moci najít chybu, tak si Stáhněte zdrojové kódy a chybu jistě najdete.


 

Stáhnout

Stažením následujícího souboru souhlasíš s licenčními podmínkami

Staženo 215x (4.49 kB)
Aplikace je včetně zdrojových kódů v jazyce Java

 

Všechny články v sekci
Kolekce a proudy v Javě
Článek pro vás napsal Milan Gallas
Avatar
Uživatelské hodnocení:
4 hlasů
Autor se věnuje programování, hardwaru a počítačovým sítím.
Aktivity