Spiegazione su classi per trattamento di Liste e Nodi

[luigipolla]

Allora il testo del programma che devo realizzare è quella a questo link:

http://forum.html.it/forum/showthrea...readid=1435948

Il prof ci ha dato la risoluzione delle classi lista e nodo:

lista:

public class ListaSemplice {
    private Nodo testa;
    public ListaSemplice(){
        testa=null;
    }
    public void addHead(String info){
        Nodo newNodo=new Nodo(info, testa);
        testa=newNodo;
    }
    public void addTail(String info){
        if(testa==null){
            addHead(info);
        }else{
            Nodo elem;
            elem=findTail();
            Nodo newNodo=new Nodo(info,null);
            elem.setNext(newNodo);
        }
    }
    public void insert(String info, int pos) throws IndexOutOfBoundsException {
        if(pos>size()){
            throw new IndexOutOfBoundsException();
        }else{
            if(testa==null|pos==0){
                addHead(info);
            }else{
                Nodo prec;
                prec=findNodo(pos-1);
                Nodo newNodo=new Nodo(info,prec);
                prec.setNext(newNodo);
            }
        }
    }
    public void deleteHead() throws IndexOutOfBoundsException {
        if(testa==null){
            throw new IndexOutOfBoundsException();
        }
        testa=testa.getNext();
    }
    public void deleteTail() throws IndexOutOfBoundsException {
        if(testa==null){
            throw new IndexOutOfBoundsException();
        }
        Nodo elem;
        elem=testa;
        while(elem.getNext().getNext()!=null){
            elem=elem.getNext();
        }
        elem.setNext(null);
    }
    public void delete(int pos) throws IndexOutOfBoundsException {
        if(pos>size()){
            throw new IndexOutOfBoundsException();
        }else{
            if(pos==0){
                deleteHead();
            }else{
                Nodo element;
                element=findNodo(pos-1);
                element.setNext(element.getNext().getNext());
            }
        }
    }
    public void clear(){
        testa=null;
    }
    public String getFirst() throws NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        return testa.getInfo();
    }
    public String getLast() throws NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        return findTail().getInfo();
    }
    public String get(int pos) throws IndexOutOfBoundsException,NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        if(pos>size()){
            throw new IndexOutOfBoundsException();
        }else{
            if(pos==0){
                return getFirst();
            }else{
                return findNodo(pos).getInfo();
            }
        }
    }   
    public void setFirst(String info) throws NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        testa.setInfo(info);
    }
    public void setLast(String info)throws NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        findTail().setInfo(info);
    }
    public void set(String info, int pos) throws IndexOutOfBoundsException,NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        if(pos>size()){
            throw new IndexOutOfBoundsException();
        }else{
            if(pos==0){
                setFirst(info);
            }else{
                findNodo(pos).setInfo(info);
            }
        }
    }
    @Override
    public String toString(){
        return testa.toString();
    }
    public int size(){
        Nodo elem;
        int i=0;
        elem=testa;
        while(elem.getNext()!=null){
            elem=elem.getNext();
            i++;
        }
        return i;
    }
    protected Nodo findTail() {
        Nodo elem;
        elem=testa;
        while(elem.getNext()!=null){
            elem=elem.getNext();
        }
        return elem;
    }
    protected Nodo findNodo(int pos) throws IndexOutOfBoundsException,NullPointerException {
        if(testa==null){
            throw new NullPointerException();
        }
        if(pos>size()){
            throw new IndexOutOfBoundsException();
        }else{
            Nodo element;
            element=testa;
            for(int i=0;i<pos;i++){
                    element=element.getNext();
            }
            return element;
        }
    }
}

nodo:

public class Nodo {
    private String info;
    private Nodo next;
    public Nodo(){
        this.info=null;
        this.next=null;
    }
    public Nodo(String dato, Nodo next){
        this.info = dato;
        this.next = next;
    }
    public String getInfo(){
        return info;
    }
    public Nodo getNext(){
        return next;
    }
    public void setInfo(String dato){
        this.info=dato;
    }
    public void setNext(Nodo next){
        this.next=next;
    }
    @Override
    public String toString(){
        String s;
        s=this.info+" "+this.next;
        return s;
    }

}

Solo che io non ho capito come ha fatto queste due classi qualcuno sarebbe così gentile da spiegarmele, grazie!

Questa volta non chiedo una risoluzione ma una spiegazione, grazie!

[andbin]

Originariamente inviato da luigipolla
Solo che io non ho capito come ha fatto queste due classi qualcuno sarebbe così gentile da spiegarmele, grazie!

Nodo è una classe che "modella" l'insieme di informazione (String) e puntamento al Nodo successivo. Per come è scritta è un banale "bean".

ListaSemplice invece è la implementazione di una lista linkata che ha come unica informazione il riferimento al nodo "head" della lista (tutti gli altri nodi sono incatenati uno dietro l'altro).

La classe è un po' lunga e non l'ho analizzata tutta, prendi per esempio addHead se vuoi capire come interpretare le cose: aggiunge un nodo in testa. Se lo aggiunge in testa vuol dire che il nuovo nodo diventa la testa e quello che era prima in testa lo si incatena dietro il nuovo.
Infatti fa: Nodo newNodo=new Nodo(info, testa);
La testa è "puntata" dal next del nuovo nodo.
E: testa=newNodo;
il nuovo nodo diventa la nuova testa.

Se capisci questi passaggi non dovrebbe esserti difficile comprendere il tutto.

Originariamente inviato da luigipolla
Il prof ci ha dato la risoluzione delle classi lista e nodo:

Ecco ... questo mi preoccupa/turba. Non è affatto corretta al 100% per essere fatta da un prof.

Mi è "caduto" l'occhio sul size(). È sbagliato!! Quando la lista è nuova (testa è ancora null) se invochi size() si "schianta" con un bel NullPointerException. E se ci sono dei nodi ne conteggia uno in meno.

[LeleFT]

Magari un titolo un po' più esplicativo...
Lo sistemo io.


Ciao.

[valia]

Originariamente inviato da andbin
Ecco ... questo mi preoccupa/turba. Non è affatto corretta al 100% per essere fatta da un prof.

Mi è "caduto" l'occhio sul size(). È sbagliato!! Quando la lista è nuova (testa è ancora null) se invochi size() si "schianta" con un bel NullPointerException. E se ci sono dei nodi ne conteggia uno in meno.

Ipotesi numero 1:
programma scritto in fretta senza nessuna esecuzione, dando per scontato che non si sbagli (e sbagliare è umano, a volte penso che ci si distragga e si pensi ad altro visto il tipo di errori)

Ipotesi numero 2:
prof pigro che ha preso dalla rete un esempio di implementazione delle classi e lo ha dato a voi come corretto, senza nemmeno provare a compilare.

Per il futuro, chiarisciti per benino il concetto di lista, Nodo come ti diceva andbin implementa banalmente un bean, poi l'analisi (un po' lenta devo dire) del codice ti fa capire cosa fa ogni metodo. Se hai chiara la logica (e magari hai l'interfaccia di List a portata di mano) non è difficilissimo comprendere a cosa serve ogni metodo.
Commentare il codice sarebbe anche buona norma (ma questa sembra utopia)

[VincenzoTheBest]

Originariamente inviato da andbin
Mi è "caduto" l'occhio sul size(). È sbagliato!! Quando la lista è nuova (testa è ancora null) se invochi size() si "schianta" con un bel NullPointerException. E se ci sono dei nodi ne conteggia uno in meno.

Tra l'altro non mi convince il fatto che per prendere le dimensioni e la coda della lista bisogna scorrerla interamente...mi sembra eccessivo.

[valia]

beh hai due possibilità:

1. tieni un indice che incrementi ad ogni input (quindi a lista vuota vale zero) e lo usi come controllo su isEmpty()
2. non hai questo indice e devi "contare" quanti elementi ci sono in lista scorrendoli

quella dell'indice è stata una feature che il mio prof di fondamenti di informatica ha presentata in un secondo momento (per comodità), ma nella sua implementazione base il mio prof ci faceva guardare alla dimensione della lista contando gli elementi (quindi scorrendo la lista).
Secondo me quel codice è frutto di vari copia e incolla (non implementato direttamente da prof)

[andbin]

Originariamente inviato da VincenzoTheBest
Tra l'altro non mi convince il fatto che per prendere le dimensioni e la coda della lista bisogna scorrerla interamente...mi sembra eccessivo.

Se non c'è un campo apposito per il "size" (che comunque sarebbe da gestire/aggiornare in modo consistente nelle varie operazioni), scorrere la lista partendo dal head (che è l'unica informazione che si ha) ..... è l'unica possibilità!

[VincenzoTheBest]

Originariamente inviato da andbin
Se non c'è un campo apposito per il "size" (che comunque sarebbe da gestire/aggiornare in modo consistente nelle varie operazioni), scorrere la lista partendo dal head (che è l'unica informazione che si ha) ..... è l'unica possibilità!

Certo questo io lo so benissimo e siamo tutti d'accordo! Mi aspettavo una risposta da luigi..