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

Java Pro pokročilé 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ženo 155x (20.5 kB)
Aplikace je včetně zdrojových kódů v jazyce java

 

  Aktivity (1)

Článek pro vás napsal Milan Gallas
Avatar
Autor se věnuje programování, hardwaru a počítačovým sítím.

Jak se ti líbí článek?
Celkem (3 hlasů) :
4.666674.666674.666674.666674.66667


 



 

 

Komentáře

Avatar
hercik11
Člen
Avatar
hercik11:

Můžu se zeptat jak by vypadal obousměrný zřetězený seznam do kterého by se zadávaly objekty ?

 
Odpovědět 5.3.2014 10:39
Avatar
Milan Gallas
Redaktor
Avatar
Odpovídá na hercik11
Milan Gallas:

Plánuji na tohle téma napsat článek popřípadě 2. Tam to bude podrobně popsáno.

 
Odpovědět 5.3.2014 19:34
Avatar
hrebavka
Člen
Avatar
hrebavka:

Zdravím. Trochu mě mate metoda isEmpty() return(size == 0) pokud je pole
prázdné neměla by vrátit true? Mělo by to logiku když se ptám je prázdné
a je-li prázdné čekal bych souhlas. Nebo to pletu? Dík.

 
Odpovědět 5.1.2015 18:14
Avatar
Milan Gallas
Redaktor
Avatar
Odpovídá na hrebavka
Milan Gallas:

Však pokud je (size == 0) => pole je prázdné => vrátí se logická hodnota TRUE. Tak to má být.

 
Odpovědět 5.1.2015 20:44
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Milan Gallas
Jan Vargovský:

Tvůj komentář:

/**
* 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
*/
Editováno 5.1.2015 20:59
 
Odpovědět 5.1.2015 20:58
Avatar
hrebavka
Člen
Avatar
Odpovídá na Milan Gallas
hrebavka:

Jasně já jen, že v komentáři je to opačně. A ještě jedna věc mi není jasná
u metody remove() se píše "najdeme v seznamu předchozí uzel, který se nachází před mazaným prvkem a tomu nastavíme referenci na mazaný prvek. ". Proč
když ho mažeme? Neměla by se nastavit refernce na prvek který je za mazaným
prvkem?

 
Odpovědět 7.1.2015 20:42
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.