Liste varie

di il
61 risposte

Liste varie

Bene, già una volta avevo aperto un thread su questa cosa, ma ci sono stati dei fraintendimenti su quello che serviva a me, quindi ne ho aperto un altro.
veniamo al dunque, spiegando anzitutto cosa devo fare.
a scuola stiamo facendo le liste, quindi queue, stack, list, ma non quelle classiche dove tu importi la classe e sei a posto, oppure quelle che si vedono su internet che utilizzano vector o lo stack.
una linkedlist formata da nodi
quindi avrò la classe nodo con 2 attributi, data e link, vari metodi che mi ritornano/settano i valori.
bene non andiamo oltre con le spiegazioni, perché qua non capisco una cosa.
copio il breve codice, così da poter chiarire meglio la cosa

main

public class List 
{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
    {
        Node<Oggetto> n = new Node<>(new Oggetto("primo oggetto"));
        System.out.println(n.getData().getTesto());
        Stack<Node> s = new Stack<>();
        s.add((Node)n);
        System.out.println(s.getHead().getData());
    }
    
}
nel dettaglio, ho la mia classe oggetto con l'unico attributo testo, e oltre al costruttore, il getTesto(), che mi ritorna appunto testo.
ora, quando provo a ritornarmi l'oggetto che ho inserito, non mi fa usare il metodo dell'oggetto che ritorno, perché?
a seguire le altre 2 classi, nodo, e oggetto.

nodo

public class Node<T> 
{
    private T data;
    private Node link;
    
    public Node(T data)
    {
        this.data = data;
    }
    
    public void setLink(Node<T> n)
    {
        this.link = n;
    }
    
    public Node<T> getLink()
    {
        return link;
    }
    
    public T getData()
    {
        return data;
    }
    
    /*@Override
    public String toString()
    {
        return "" + data;
    }*/
}
oggetto

public class Oggetto 
{
    private String testo;
    
    public Oggetto(String s)
    {
        this.testo = s;
    }
    
    public String getTesto()
    {
        return testo;
    }
}
stack

public class Stack<E>
{
    private Node<E> head;
    
    public boolean isEmpty()
    {
        return head == null;
    }
    
    public void add(Node<E> n)
    {
        if(isEmpty())
        head = n;
    }
    
    public Node<E> getHead()
    {
        return head;
    }
    /*@Override
    public String toString()
    {
        return head + "";
    }*/
}

61 Risposte

  • Re: Liste varie

    KuroKami69 ha scritto:


    quando provo a ritornarmi l'oggetto che ho inserito, non mi fa usare il metodo dell'oggetto che ritorno, perché?
    Perché il getData() di Node ha come tipo di ritorno java.lang.Object ... non Oggetto.
    Volendo fare le cose nel modo giusto, Node dovrebbe essere una classe "generica", che sfrutta i generics di Java 5.

    E comunque un conto è fare una classe che rappresenta una lista "linkata" (e che tipicamente/presumibilmente tiene "nascosti" i nodi), un altro conto è gestire dei nodi per conto proprio.
  • Re: Liste varie

    Bhe la nostra prof, non ho ben capito a che pro onestamente, vuole farci lavorare su queste liste, dove, si ha la pila, e dentro a sta pila si inseriscono tanti nodi. pila coda etc
    comunque ho capito, a dire il vero no, non so cosa siano i generics, ma andrò subito a documentarmi, grazie

    @EDIT:
    ho editato il codice di node nel primo post, è corretto?

    @EDIT2:
    considerando che funziona, direi di si. ovviamene ho modificato anche il main.
    ogni tanto mi chiedo "ma perché programmare? ne sarò in grado, con cose infinitamente più difficili?" e secondo me la risposta sono questi momenti dove, grazie all'aiuto di altri, e provando, si impara qualcosa di nuovo, la si applica e, anche se magari non si ha capito al 100% la cosa, si ha comunque la soddisfazione di quel piccolo passetto in avanti appena fatto
  • Re: Liste varie

    KuroKami69 ha scritto:


    @EDIT:
    ho editato il codice di node nel primo post, è corretto?
    No, non proprio. Innanzitutto tipicamente non si usa N come type variable. Ci sono una serie di lettere che si usano convenzionalmente: T in modo molto generalizzato, E per gli elementi delle collezioni, K e V per chiavi/valori delle mappe e pochi altri.

    Inoltre non hai parametrizzato tutto. Il modo corretto è il seguente.
    public class Node<T> {
        private T data;
        private Node<T> link;
    
        public Node(T data) {
            this.data = data;
        }
    
        public void setLink(Node<T> n) {
            this.link = n;
        }
    
        public Node<T> getLink() {
            return link;
        }
    
        public T getData() {
            return data;
        }
    
        @Override
        public String toString() {
            return data + "";
        }
    }
    Nota come TUTTI i riferimenti a Node sono parametrizzati!

    E quando poi lo usi non devi più fare:

    Node n = new Node(o);

    ma:

    Node<Oggetto> n = new Node<Oggetto>(o);

    Da Java 7 si può usare il "diamond" ( <> ) per abbreviare così:

    Node<Oggetto> n = new Node<>(o);
  • Re: Liste varie

    andbin ha scritto:



    Nota come TUTTI i riferimenti a Node sono parametrizzati!

    E quando poi lo usi non devi più fare:

    Node n = new Node(o);

    ma:

    Node<Oggetto> n = new Node<Oggetto>(o);

    Da Java 7 si può usare il "diamond" ( <> ) per abbreviare così:

    Node<Oggetto> n = new Node<>(o);
    onestamente funziona anche senza il diamond, anche se mi pare di capire che è meglio se ce lo metto
    effettivamente sono stato sciocco a parametrizzare solo 2 cosette! ok ma ora domanda.
    io ho il mio bellissimo nodo, formato dalla parte data(generics) e dal mio link(tipo node)
    si presuppone quindi che la parte link contenga/punti il nodo successivo giusto?
    ora, nella LIFO, ho un attributi head di tipo node, che sostanzialmente mi linka sempre l'ultimo nodo inserito.
    essendo un nodo, quindi, anch'esso avrà la parte data e la parte link giusto? quindi perché se io faccio una cosa di questo tipo
    
    ....
    head = n;
    ....
    
    allora esso mi funziona, mentre se faccio
    
    ....
    head.setLink(n);
    ....
    
    quando poi vado a stampare il data, mi punta a null?
    posto qua il breve codice della stack
    
    public class Stack 
    {
        private Node head;
        
        public boolean isEmpty()
        {
            return head == null;
        }
        
        public void add(Node n)
        {
            if(isEmpty())
            head = n;
        }
        
        @Override
        public String toString()
        {
            return head.getData() + "";
        }
    (attualmente mi stampa ancora l'indirizzo di memoria, è perché non ho parametrizzato tutto?

    @EDIT:
    mi è venuto un dubbio. le mie liste, conterranno solo nodi, quindi non ho ritenuto sia corretto generalizzarle. mi sbaglio?
  • Re: Liste varie

    KuroKami69 ha scritto:


    onestamente funziona anche senza il diamond, anche se mi pare di capire che è meglio se ce lo metto
    Se fai:

    Node<Oggetto> n = new Node(o);

    Quello a destra è il "raw type" (il tipo "crudo"). Tecnicamente funziona ma in compilazione hai un warning di unchecked conversion e già questo serve come campanello di allarme per indicare che c'è qualche problema sulla tipizzazione.

    Nota (non lo sai perché non hai studiato i generics ): il raw type è il super-tipo di tutte le parametrizzazioni possibili. Quindi Node come raw-type è il super-tipo di Node<Oggetto>, Node<String>, Node<Date> ecc... Non il contrario.

    Se fai:

    Node n = new Node<Oggetto>(o);

    dal punto di vista del subtyping sarebbe corretto. Ma un IDE "furbo" (come Eclipse) ti dà subito un warning per avvisare che il tipo dovrebbe essere parametrizzato. Altrimenti puoi avere poi altri warning dove poi usi la variabile.

    Insomma, i generics vanno usati appropriatamente.

    KuroKami69 ha scritto:


    si presuppone quindi che la parte link contenga/punti il nodo successivo giusto?

    KuroKami69 ha scritto:


    
    public class Stack 
    {
        private Node head;
        
        public boolean isEmpty()
        {
            return head == null;
        }
        
        public void add(Node n)
        {
            if(isEmpty())
            head = n;
        }
        
        @Override
        public String toString()
        {
            return head.getData() + "";
        }
    Beh ... ANCHE Stack andrebbe resa "generica" allora !!

    Comunque se head è null, NON puoi ovviamente fare head.setLink( ... );

    KuroKami69 ha scritto:


    (attualmente mi stampa ancora l'indirizzo di memoria, è perché non ho parametrizzato tutto?
    La tua classe Oggetto non ha il toString() ridefinito.
  • Re: Liste varie

    Si, lo so, infatti non lo sto utilizzando il toString per oggetto
    ho provato a rendere Stack generica, ma forse ho perso qualche punto mmh, anche se mi sembra di aver parametrizzato tutto mmh
    (riflettendoci un attimo, più che generalizzarla, in questo modo l'ho "specializzata", ma onestamente mi son un attimo perso uhm)
    
    public class Stack<Node>
    {
        private Node head;
        
        public boolean isEmpty()
        {
            return head == null;
        }
        
        public void add(Node n)
        {
            if(isEmpty())
            head = n;
        }
        
        public Node getHead()
        {
            return head;
        }
        /*@Override
        public String toString()
        {
            return head + "";
        }*/
    }
    
    onestamente non capisco perché, dopo aver aggiunto il primo nodo alla stack, non mi faccia più usare il getTesto della classe oggetto
    
    System.out.println(s.getHead().getData().getTesto());
    
    la lista è parametrizzata (?)(anche se forse ho mancato qualcosa), quindi io nel nodo(generico) inserisco un oggetto.
    poi questo nodo lo inserisco nella lista, e se voglio vedere il contenuto del mio head, dovrò richiamarlo, quindi richiamare l'oggetto contenuto nel nodo e poi posso usare i metodi dell'oggetto inserito no?
    ok ho troppa confusione in testa ._.
  • Re: Liste varie

    KuroKami69 ha scritto:


    ho provato a rendere Stack generica, ma forse ho perso qualche punto mmh, anche se mi sembra di aver parametrizzato tutto mmh
    (riflettendoci un attimo, più che generalizzarla, in questo modo l'ho "specializzata", ma onestamente mi son un attimo perso uhm)
    
    public class Stack<Node>
    {
        private Node head;
        
        public boolean isEmpty()
        {
            return head == null;
        }
        
        public void add(Node n)
        {
            if(isEmpty())
            head = n;
        }
        
        public Node getHead()
        {
            return head;
        }
        /*@Override
        public String toString()
        {
            return head + "";
        }*/
    }
    
    Assolutamente NO!

    Quando si definisce una classe "generica", quello che si mette tra <> NON è (e non deve essere) il nome di un tipo esistente. Lì si dichiarano delle type variable, che sono semplicemente dei "segnaposto". Usare il nome di un tipo esistente sarebbe altamente FUORVIANTE.
    Anche per questo motivo è d'uso usare lettere singole che sicuramente (di norma) NON sono tipi esistenti.

    Quindi:
    public class Stack<E>
    {
        private Node<E> head;
        
        public boolean isEmpty()
        {
            return head == null;
        }
        
        public void add(Node<E> n)
        {
            if(isEmpty())
            head = n;
        }
        
        public Node<E> getHead()
        {
            return head;
        }
    
        // ....
    }
    Qui ho usato E perché per convenzione si usa E ("elemento") per le "collezioni".

    KuroKami69 ha scritto:


    ok ho troppa confusione in testa ._.
    Troppa ....
  • Re: Liste varie

    Immaginavo fosse sbagliato, ma non avevo nulla da perdere a provarci, per cui...
    però, per favore, spiegami una cosa.
    abbiamo detto che la parte "link" del nodo, deve contenere un riferimento al nodo successivo. quindi, che differenza c'è tra fare, nella classe Stack
    head = n
    e
    
    head.setLink(n);
    
    ?? voglio dire, la variabile head è di tipo Node, quindi sarà la parte link del nodo.
    perché quei 2 codici non funzionano allo stesso modo? mi interessa capire anzitutto questo, se puoi spiegarmelo per cortesia
  • Re: Liste varie

    KuroKami69 ha scritto:


    head = n
    Questo assegna un nodo n alla variabile head. Ovvero quel nodo passato DIVENTA la "testa". Chiaramente ha senso SOLO se head è null.

    KuroKami69 ha scritto:


    head.setLink(n);
    Questo assegnerebbe n come nodo "successivo" del head ma ha senso SOLO se head NON è null cioè se c'è già un nodo come "testa".
  • Re: Liste varie

    Mmh credo di aver capito.
    quindi quel setlink lo dovrò usare nell'else interno all'add mh
    ora che questa cosa è più o meno chiara... ?????????? *inchino*. seriamente ora
    per fare questa cosa, delle pile, io avrò la classe nodo che è generica, mentre i vari tipi di pila, saranno delle collezioni di nodi, quindi andranno generalizzate, come mi hai gentilmente detto te, con <E>. fino a qua, credo sia corretto.
    domandona. nell'add
    
    public void add(Node<E> n)...
    
    quel Node<E> indica che si passa una collezione di nodi, o un componente di una collezione?
  • Re: Liste varie

    KuroKami69 ha scritto:


    domandona. nell'add
    
    public void add(Node<E> n)...
    
    quel Node<E> indica che si passa una collezione di nodi, o un componente di una collezione?
    Qui stai solo passando un Node e basta (dal punto di vista del add). E visto che la classe Node offre possibilità di smanettarla come ti pare con il setLink ... chi garantisce (al add) che non passi un pezzo di più nodi linkati??

    Il punto/problema è che nella tua Stack hai deciso di fare "esporre" all'esterno i nodi e la loro gestione. Questo rende molto più critica la gestione dello stack.
    La classe Stack potrebbe benissimo USARE la classe Node ma NON esporre i nodi all'esterno. Ovvero potrebbe essere fatta così:
    public class Stack<E> {
        private Node<E> head;
    
        public boolean isEmpty() { ..... }
    
        public void push(E valore) { ..... }
    
        public E pop() { ..... }
    
        //.....
    }
    Cioè non riceve né restituisce dei Node!!
  • Re: Liste varie

    Se vuoi fare uno "stack" (inserimento ed estrazione dallo stesso "lato" della collezione), ti dico concettualmente cosa devi fare. Per aiutarti ti faccio proprio il grafico "a caratteri" (nota: userò "next" per il riferimento al successivo. puoi chiamarlo "link" o come vuoi):

    1) Per fare un "push" (aggiungere un nuovo valore/nodo):

    a) se head è null, assegni direttamente il nodo a head. Ed ottieni:
                +-----------+
                | data=A    |
    head ------>| next=null |
                +-----------+
    
    b) se head NON è null, allora metti il nuovo nodo "in testa". Ed ottieni:
                +-----------+     +-----------+
                | data=B    |     | data=A    |
    head ------>| next=-----|---->| next=null |
                +-----------+     +-----------+
    Ovvero:
    - prima metti il valore di head nel next del nuovo nodo.
    - poi assegni il nuovo nodo al head.


    2) Per fare un "pop" (estrarre un valore togliendo il nodo in testa):

    a) se head è null, non ci sono nodi. In questi casi è bene lanciare una eccezione es. java.util.EmptyStackException (questa è del framework ma serve proprio per gli stack!)

    b) se head NON è null:

    - prima prendi il nodo puntato da head e lo tieni in una variabile temporanea
    - poi assegni a head il valore del next del primo nodo (così quel nodo viene "saltato")
    - poi annulli il next di quel nodo (giusto così non tiene referenziato il resto, presumendo/sperando che nessun'altro abbia tenuto il riferimento al nodo, così finirà al g.c.)
    - poi restituisci il valore
  • Re: Liste varie

    andbin ha scritto:


    Il punto/problema è che nella tua Stack hai deciso di fare "esporre" all'esterno i nodi e la loro gestione. Questo rende molto più critica la gestione dello stack.
    sfortunatamente non è stata una mia decisione.
    a scuola stiamo facendo queste pile partendo da 0, e onestamente non ne vedo il senso pratico, anche perché la prof. ci ha presentato la questione usando solo degli int, quindi per poterla applicare, questa cosa,a un contesto più generale, come poi in teoria dovrebbe essere, le cose che stiamo facendo adesso andrebbero riprese in mano e modificate/riscritte da 0, e non la vedo una come una cosa esattamente bella.
    per me, se avessimo trattato le liste in generale, quindi la linked, l'array etc, sarebbe stato molto più profiquo che perdere quasi 2 mesi su questa cosa, che onestamente mi ha messo in difficoltà a livello di codice, perché non son riuscito subito a figurarmi come dovrei scriverlo (non che ora sia messo molto meglio).
    il disegnetto che hai fatto te, è lo stesso che la prof continua a spammare sulle lavagne ogni volta che abbiamo lezione ahaha anche se fatto più cartonesco
    ora che mi hai chiarito ulteriormente le idee (onestamente, ora come ora, non ho idea di come gestire una pila senza esporre i nodi, quindi, anche se volessi fare qualcosa di un attimo più avanzato, ora non ne sarei in grado), volevo chiederti, forse me lo hai già spiegato tra le linee, ma io non ho colto nulla:
    prendendo la mia attuale pila Stack<E>, e il mio attuale nodo Node<T>, io mi creo un nodo generico, e ci metto dentro il mio oggetto o. fin qua è limpido e ci sono.
    quel nodo poi lo aggiungo allo stack. fin qua ancora tutto limpido.
    quando poi però voglio usare il nodo che ho in testa, se faccio semplicemente getData(), della pila, mi dovrebbe tornare l'unico nodo che ho, e con esso l'oggetto che ci avevo messo dentro. se dopo il getData() della pila, voglio usare il mio oggetto, dovrò fare un altro getData(), ma questa volta del Node. fino a qui credo di essere bene o male nella strada giusta. ma allora perché non mi fa usare l'oggetto che sta dentro al nodo?
    modifico il codice nel primo post con quello che ho ora.
    p.s. voglio far notare che trovo inutile soffermarci su queste cose a livello pratico, la teoria sul come funzionano è sempre importante. voglio dire, non sarò esperto ma non riesco ad immaginare un caso dove io mi debba costruire da 0 una pila, evitando di usare quelle già presenti
  • Re: Liste varie

    KuroKami69 ha scritto:


    a scuola stiamo facendo queste pile partendo da 0, e onestamente non ne vedo il senso pratico, anche perché la prof. ci ha presentato la questione usando solo degli int, quindi per poterla applicare, questa cosa,a un contesto più generale, come poi in teoria dovrebbe essere, le cose che stiamo facendo adesso andrebbero riprese in mano e modificate/riscritte da 0, e non la vedo una come una cosa esattamente bella.
    per me, se avessimo trattato le liste in generale, quindi la linked, l'array etc, sarebbe stato molto più profiquo che perdere quasi 2 mesi su questa cosa, che onestamente mi ha messo in difficoltà a livello di codice, perché non son riuscito subito a figurarmi come dovrei scriverlo (non che ora sia messo molto meglio).
    Dal punto di vista "pratico" no infatti. Difficilmente (non è ovviamente impossibile ma molto raro) in applicazioni reali andrai a creare "da zero" liste, stack, ecc.. Molto più facilmente andrai ad usare le collezioni del framework o di librerie esterne (es. quelle della Google Guava).

    Invece tutto questo ha una alta valenza dal punto di vista "didattico". Perché ti permette di confrontarti con molti concetti: classi/oggetti, reference, strutture dati e in questi casi possibilmente anche con i generics.

    Se non riesci ad implementare un banale stack con push/pop fatto a nodi (con o senza esporre i nodi) .... si presupporrebbe che difficilmente riusciresti ad affrontare cose più "avanzate" ....

    KuroKami69 ha scritto:


    il disegnetto che hai fatto te, è lo stesso che la prof continua a spammare sulle lavagne ogni volta che abbiamo lezione ahaha anche se fatto più cartonesco
    Beh, il concetto è quello con un stack implementato a nodi ...

    KuroKami69 ha scritto:


    onestamente, ora come ora, non ho idea di come gestire una pila senza esporre i nodi
    Ti assicuro che si può benissimo fare lo stack SENZA ricevere/esporre i nodi all'esterno.

    KuroKami69 ha scritto:


    quando poi però voglio usare il nodo che ho in testa, se faccio semplicemente getData(), della pila, mi dovrebbe tornare l'unico nodo che ho, e con esso l'oggetto che ci avevo messo dentro. se dopo il getData() della pila, voglio usare il mio oggetto, dovrò fare un altro getData(), ma questa volta del Node. fino a qui credo di essere bene o male nella strada giusta. ma allora perché non mi fa usare l'oggetto che sta dentro al nodo?
    Mettiamola così, se dall'oggetto Stack esponi la "testa" (con un es. getHead() o qualcosa del genere), allora certamente chi ha in mano lo Stack può anche ottenere la testa e può quindi fare svariate cose visto che il tuo Node permette di leggere/impostare il prossimo Node.
    Può sicuramente:
    a) scorrere la lista dei nodi per conto suo, FUORI dal controllo di Stack.
    e
    b) visto che c'è il setLink() pubblico nel Node, può anche andare a "ravanare" completamente la catena dei nodi, se lo vuole.

    Ma tutto questo scaturisce dal design che hai fatto dello Stack, ovvero dalla scelta (tua o non tua) di far sì che chi usa lo Stack debba "sapere" dei nodi e ci possa mettere il "naso" come/dove gli pare ....
Devi accedere o registrarti per scrivere nel forum
61 risposte