Liste

Esistono dei tipi predefiniti in Java per liste e insiemi

Breve riepilogo

Variabili:

ogni oggetto si può mettere in Object
per il passo inverso, serve il cast

Quando la variabile è di un tipo ma l'oggetto è di una sottoclasse:

le componenti sono quelle della classe dalla variabile
i metodi sono quelli della classe dell'oggetto

Nota: questo discorso vale solo per i metodi e le componenti che esistono in tutte e due le classi

Se un metodo esiste solo nella classe dell'oggetto ma non in quella della variabile, non si può invocare

Ridefinizione dei metodi di `Object`

si definisce public String toString() come un metodo che ritorna una stringa ottenuta concatenando le componenti
si definisce public boolean equals(Object o) come un metodo che:
1. confronta o con null
2. fa il cast di o alla classe
3. confronta le componenti di o e this

class Studente {
  String nome;
  int esami;
  double media;

  public String toString() {
    return "["+this.nome+" "+
           this.esami+" "+
           this.media+"]";
  }

  public boolean equals(Object o) {
    if(o==null)
      return false;

    Studente s;
    s=(Studente) o;

    if(s.nome==null) {
      if(this.nome!=null)
        return false;
    }
    else
      if(!s.nome.equals(this.nome))
        return false;

    return ((s.esami==this.esami) &&
            (s.media==this.media));
  }
}

Oggetti con dentro altri oggetti

Li abbiamo già visti

Esempio: il triangolo è composto di tre punti

Dentro l'oggetto triangolo ci sono dei riferimenti ad altri oggetti

È semplicemente un oggetto con dentro riferimenti ad altri oggetti

Catene di tre oggetti

Possiamo anche definire oggetti con dentro oggetti con dentro altri oggetti...

class Terzo {
  int x;
}

class Secondo {
  int x;
  Terzo y;
}

class Primo {
  int x;
  Secondo y;
}

In memoria, gli oggetti sono collegati:

Questa catena di tre oggetti contiene tre interi

È un modo per rappresentare una sequenza di tre interi

Catene di lunghezza arbitraria

Se gli oggetti contengono un riferimento a un altro oggetto della stessa classe, posso realizzare catene di lunghezza qualsiasi

class Prova {
  int x;
  Prova p;
}

In memoria: un oggetto di tipo Prova contiene un intero, e una variabile in cui ci va l'indirizzo di un altro oggetto di tipo Prova

In a.x ci posso mettere un intero

In a.p ci posso mettere il riferimento a un altro oggetto Prova:

  Prova a=new Prova();
  a.x=12;
  a.p=new Prova();

In a.p c'è l'indirizzo di un altro oggetto Prova, quindi posso fare:

  a.p.x=-2;
  a.p.p=new Prova();

Nomenclatura

Strutture dati di questo tipo di dicono liste collegate

Di solito, le componenti vengono chiamate info e next:

class Nodo {
  int info;
  Nodo next;
}

Creazione di una lista

Esempio di creazione:

Nodo n;
n=new Nodo();
n.info=2;
n.next=new Nodo();
n.next.info=5;
n.next.next=new Nodo();
n.next.next.info=-2;
n.next.next.next=null;

Per chiudere la catena, metto null nel campo next

Significato: non c'è un prossimo elemento

Aspetto di una lista collegata

Nodo n;

Inizio: solo la variabile

Creazione primo oggetto

n=new Nodo();

Ora posso mettere 2 nella componente info

Creazione secondo nodo

n.next=new Nodo();

Crea un nuovo oggetto, e l'indirizzo lo mette in n.next

Situazione alla fine

Creo anche il terzo oggetto

Nel campo next ci metto null per indicare che non c'è un altro oggetto dopo di questo

Liste con oggetti arbitrari

Al posto di int info, posso mettere un tipo qualsiasi

Se ci metto Object, ho una lista i cui elementi sono di tipo Object

Vantaggio: in una variabile Object ci posso mettere oggetto qualsiasi

class Nodo {
  Object info;
  Nodo next;
}

Catene di oggetti, in memoria

L'unica differenza è che il campo info contiene l'indirizzo di un oggetto

Al posto di un intero, nei campi info ci sono riferimenti ad altro oggetti

Ci posso mettere riferimenti a Point, Rectangle, Studente, ecc

Cosa posso fare con una lista

Ci sono varie operazioni che si possono fare:

verifica se è vuota
trovare la lunghezza
trovare l'elemento in una certa posizione
inserire un elemento in una certa posizione
eliminare l'elemento in una certa posizione

Alcune sono complicate da realizzare

Cosa succede se si inserisce un elemento

Si può mettere all'inizio della catena, alla fine, o anche in mezzo:

Eliminazione di un elemento

Basta fare in modo che la catena di riferimenti ``aggiri'' l'elemento da eliminare:

Per eliminare il secondo:

n.next=n.next.next;

In generale, si può eliminare un elemento qualsiasi

Come si fanno le operazioni

Si possono scrivere metodi che realizzano queste operazioni

Non lo vediamo perchè sono troppo complicate

Esiste una classe Java che contiene i metodi che fanno queste operazioni

Tipo `LinkedList`

È un tipo di oggetto predefinito di Java

Realizza liste collegate, in cui il campo info è Object

Sono liste collegate di oggetti

È un tipo predefinito del linguaggio: non c'è bisogno di sapere come sono implementati i metodi

Se si usa una LinkedList va fatto:

import java.util.*;

Come si usa

La lista è composta di più oggetti

A partire dal primo, so gli indirizzi degli altri

Uso una sola variabile LinkedList

  LinkedList l;
  l=new LinkedList();

Inserire un elemento in fondo alla lista:

  l.add(new Point(12,3));
  l.add("abcd");
  l.add(new Studente("Pippo", 1, 21));

Stampa della lista

Si può stampare una lista:

  System.out.println(l);

Per ogni oggetto della lista, viene invocato toString, e poi stampato

Se un oggetto della lista non ridefinisce toString, viene ereditato quello di Object (che stampa solo l'indirizzo)

Stampa della lista

Stampa della lista di sopra se toString non viene ridefinito in Studente:

[java.awt.Point[x=12,y=3], abcd,
Studente@5d87b2]

Stampa l'indirizzo dell'oggetto, non i dati dello studente!

Se ridefinisco toString di Studente:

[java.awt.Point[x=12,y=3], abcd,
[Pippo 1 21.0]]

Adesso vedo i dati dello studente!

Trovare la lunghezza di una lista

Metodo size, che ritorna un intero

import java.util.*;
import java.awt.*;

class Prova {
  public static void main(String args[]) {
    LinkedList l;
    l=new LinkedList();
  
    l.add(new Point(12,3));
    l.add("abcd");
    l.add(new Studente("Pippo", 1, 21));

    System.out.print("Lunghezza lista: ");
    System.out.println(l.size());
  }
}

Inserire un elemento in mezzo

Il metodo add è sovraccarico

  // inserisce elemento alla fine
 l.add("efg");

C'è una versione con un intero

  l.add(2, "efg");

Inserisce l'elemento in posizione 2

Numerazione degli elementi

Attenzione!

Gli elementi sono numerati da 0 a size()-1

Quando faccio l.add(2, "efg"), l'elemento "efg" viene inserito nella posizione 2, ossia in terza

Gli elementi successivi vengono scalati (in ordine):

Prima:   [abcd, ert, wwww, zzzz]
faccio   l.add(2, "nuova");
Dopo:    [abcd, ert, nuova, wwww, zzzz]

L'elemento viene inserito in posizione 2 (la terza)

Tutti quelli dopo sono spostati in ordine

Regola degli indici

È la stessa degli array:

l'elemento di indice 0 è il primo

Vale per gli array, per le liste, e per varie altre strutture dati

Regola della dimensione:

l'ultimo elemento ha indice num_elementi-1

Questa regola vale anche in altri linguaggi

Dove è facile sbagliare: quando si fanno cicli

Dove va l'elemento?

  l.add(i, oggetto);

Regola dell'inserimento:

l'oggetto diventa l'oggetto che sta in posizione i nella lista

Se faccio l.add(0, o) allora o diventa il nuovo elemento in posizione 0 (la prima posizione)

Esercizio

Creare una lista composta da cinque stringhe lette da tastiera

Soluzione

Ciclo: ad ogni iterazione, si legge e si aggiunge in fondo alla lista

import java.util.*;
import javax.swing.*;

class Tast {
  public static void main(String args[]) {
    LinkedList l;
    l=new LinkedList();

    int i;
    String s;

    for(i=0; i<5; i++) {
      s=JOptionPane.showInputDialog("Dammi una stringa");

      l.add(s);
    }

    System.out.println(l);

    System.exit(0);
  }
}

Mettere `null`

Posso anche aggiungere null come elemento di una lista

  l.add(null);

Variante

Stesso esercizio di prima, ma inserendo gli elementi all'inizio della lista

Soluzione

Gli elementi letti vanno inseriti in prima posizione

Quindi, si fa l.add(0, s)

import java.util.*;
import javax.swing.*;

class Tast {
  public static void main(String args[]) {
    LinkedList l;
    l=new LinkedList();

    int i;
    String s;

    for(i=0; i<5; i++) {
      s=JOptionPane.showInputDialog("Dammi una stringa");

      l.add(0, s);
    }

    System.out.println(l);

    System.exit(0);
  }
}

Ordine risultante

Il primo elemento viene messo in posizione 0

Il secondo elemento viene letto e messo in posizione 0, per cui va prima dell'altro

Poi si legge un altro elemento, che va in posizione 0, ossia prima degli altri due

Alla fine, la lista contiene le stringhe lette da tastiera in ordine inverso

Trovare un elemento

Ci sono tre metodi:

get(int index): trova l'elemento in una posizione qualsiasi
getFirst(): trova il primo
getLast(): trova l'ultimo

Tutti e tre restituiscono un Object

Cast sugli elementi

Se so che sono di un tipo specifico, posso fare il cast:

  String s;

  s=(String) l.getFirst();

Dà errore se poi l'oggetto non è di tipo stringa!

È un errore in esecuzione

Di solito, si fanno liste che contengono tutti elementi dello stesso tipo

Perchè devo fare il cast?

  Point p, q;
  ...

  l.add(p);
  q=(Point) l.getLast();

Domanda:

Quando metto dentro p, è un Point
perchè, quando lo tiro fuori, devo fare il cast per rimetterlo in una variabile Point?

Conversione a `Object`

Le liste sono sequenze di oggetti Object

È come se fosse una sequenza di variabili Object

inserire: in una variabile Object posso mettere un qualsiasi riferimento a oggetto
trovare: se ho un Point in una variabile Object, devo fare il cast per poterlo rimettere in un Point

Graficamente

Quando inserisco un oggetto in una LinkedList, viene messo in una variabile Object

Inserimento: faccio Object=Point:
non ho bisogno del cast

Trovare elemento: per fare Point=Object devo fare il cast, anche se l'oggetto è un Point

Notare l'incapsulamento: non so come è fatta la LinkedList

È come se ci fosse una ``barriera'', che mi impedisce di vedere la struttura degli oggetti

So solo che dentro ci sono delle variabili Object per memorizzare gli oggetti.

Queste variabili sono componenti di oggetti collegati fra loro, ma la cosa non mi interessa.

Esercizio

Stampare gli elementi di una lista, uno per linea

Notare che println(lista) li stampa tutti su una linea

  static void stampaLista(LinkedList l) {
    ...
  }

Suggerimento: per ogni elemento, stampalo

Soluzione

l.get(i) trova l'oggetto in posizione i

Gli elementi della lista hanno indici che vanno da 0 a l.size()-1

  static void stampaLista(LinkedList l) {
    int i;
    Object o;

    for(i=0; i<l.size(); i++) {
      o=l.get(i);

      System.out.println(o.toString());
    }
  }

Osservazione

Quando faccio l.get(i), viene ritornato un Object, che metto in o

o.toString() invoca il metodo toString dell'oggetto di invocazione

Se è un Point, allora o.toString() invoca il metodo toString di Point, anche se la variabile o è un Object

Nota: questo vale anche se faccio l.get(i).toString(): il risultato di l.get(i) è di tipo Object, per cui è come se faccessi Object o=l.get(i); o.toString();

Esercizio

Scrivere un metodo statico che verifica la presenza di un oggetto in una lista

  static boolean
     presente(LinkedList l, Object o) {
    ...
  }

Voglio sapere se la lista contiene un oggetto che è equals ad o

Soluzione

Solito metodo del risultato parziale

Per ogni elemento della lista, se è equals ad o, ritorna true

Se si arriva alla fine senza aver trovato l'elemento, si ritorna false

Implementazione della soluzione

  static boolean presente(LinkedList l, Object o) {
    int i;

    for(i=0; i<l.size(); i++) {
      if(o.equals(l.get(i)))
        return true;
    }

    return false;
  }

Attenzione! Quando faccio o.equals viene invocato l'equals dell'oggetto!

Se l'oggetto è un Point, viene invocato equals di Point, anche se o è una variabile Object

Più facile

Nella classe LinkedList c'è il metodo contains:

  boolean contains(Object)

Verifica se l'elemento sta nella lista oppure no

Verifica coordinate negative

Scrivere un metodo statico che verifica se una lista di punti contiene un punto con coordinata x negativa

  static boolean puntiNegativi(LinkedList l) {
    ...
  }

Metodo del risultato parziale

Sempre la solita cosa:

quando inizio, non ho considerato nessun punto, quindi non ci sono punti con coordinata x negativa
se ne trovo uno, allora posso dire subito che c'è

  static boolean puntiNegativi(LinkedList l) {
    int i;

    for(i=0; i<l.size(); i++) 
      if(l.get(i).x<0)
        return true;

    return false;
  }

Quando si compila, genera un errore

Quale?

Non esiste la componente `x`

L'errore che viene dato è questo:

Negative.java:9: cannot resolve symbol
symbol  : variable x  
location: class java.lang.Object
      if(l.get(i).x<0)
              ^
1 error

Significa: l'oggetto l.get(i) non ha la componente x

È vero!

Le componenti sono date dalla variabile

l.get(i) è Object, che non ha la componente x

Quando scrivo l'invocazione di metodo, è come se scivessi una variabile con quel tipo di ritorno

Variabile e oggetto

variabile: l.get(i) è di tipo Object
oggetto: l'oggetto il cui indirizzo sta in l.get(i) è un Point

Regola: le componenti sono quelle della variabile!

Object non ha la componente x

Cast

Dato che l'oggetto è di tipo Point, posso fare il cast a Point

   Point e=(Point) l.get(i);

Ora posso fare e.x ecc.

Soluzione corretta

Prima faccio il cast, e poi vedo la componente x

  static boolean puntiNegativi(LinkedList l) {
    int i;
    Point p;

    for(i=0; i<l.size(); i++) {
      p=(Point) l.get(i);

      if(p.x<0)
        return true;
    }

    return false;
  }

Osservazione

Se nella lista ci metto un rettangolo, e poi invoco il metodo, viene dato errore

Il cast (Point) oggetto si può fare solo se la variabile contiene effettivamente un punto

Nel testo del problema, ``data una lista di punti''
non esiste il tipo ``lista di punti''
significa solo che sto dicendo che invocherò il metodo solo su liste in cui tutti gli oggetti sono di tipo Point

Quindi, il cast e=(Point) l.get(i) non dà errore se la lista passata rispetta la specifica

Altro esercizio

Realizzare un metodo statico che prende una lista di punti, che sono in ordine di x crescente, e inserisce un nuovo punto nella posizione giusta

  static void inserisciPuntoOrdine(
    LinkedList l, Point p) {
    ...
  }

Soluzione

Primo livello di raffinamento dell'algoritmo:

trova la posizione in cui va messo l'elemento
inseriscilo

La seconda parte è facile

Trovare la posizione giusta

Faccio un ciclo

Appena trovo un elemento la cui x è maggiore o uguale di quello da inserire, l'indice è quello

Versione che non funziona

Viene dato un errore:

  static void inserisciPuntoOrdine(
    LinkedList l, Point p) {

    int i;
    int pos=0;

    for(i=0; i<l.size(); i++) {
      if(l.get(i).x>=p.x) {
        pos=i;
        break;
      }
    }

    l.add(pos, p);
  }

È un errore in compilazione: quale?

Non esiste la componente `x`

L'errore è:

Prova.java:30: cannot resolve symbol
symbol  : variable x  
location: class java.lang.Object
      if(l.get(i).x>=p.x) {
              ^
1 error

Motivo: l.get(i) è di tipo Object, che non ha il campo x

Variabile e oggetto

variabile: l.get(i) è di tipo Object
oggetto: l'oggetto il cui indirizzo sta in l.get(i) è un Point

Regola: le componenti sono quelle della variabile!

Object non ha la componente x

Cast

Dato che l'oggetto è di tipo Point, posso fare il cast a Point

   Point e=(Point) l.get(i);

Ora posso fare e.x ecc.

Soluzione corretta

Anche se una variabile o di tipo Object contiene l'indirizzo di un Point, per poter usare le componenti x ed y devo fare il cast

  static void inserisciPuntoOrdine(
    LinkedList l, Point p) {

    int i;
    int pos=0;
    Point e;

    for(i=0; i<l.size(); i++) {
      e=(Point) l.get(i);
      if(e.x>=p.x) {
        pos=i;
        break;
      }
    }

    l.add(pos, p);
  }

Funziona anche se la lista contiene più volte gli stessi elementi

Metodi non ridefiniti

Questa soluzione non funziona:

  int x=(int) (l.get(i).getX());

È vero che i metodi sono quelli dell'oggetto

È vero che Point ha il metodo getX()

Però vale solo per i metodi che sono ridefiniti

Object non ha il metodo getX()

Non posso fare o.getX(), anche se poi o contiene l'indirizzo di un Point

Metodi e componenti

Variabile e oggetto della stessa classe: metodi e componenti della classe

Variabile di un tipo e oggetto di una sottoclasse:

non ridefiniti: regola solita: ogni variabile accede ai suoi metodi e componenti
ridefiniti: le componenti sono quelle della variabile, i metodi dell'oggetto

La regola da ricordare vale solo per componenti e metodi che sono ridefiniti, e soltanto quando la varibile e l'oggetto sono di tipo diverso

Caso tipico

La variabile è un Object, ma l'oggetto è di un altro tipo:

non ha componenti (devo fare il cast, se mi servono le componenti dell'oggetto)
ha i metodi equals e toString: se sono ridefiniti, vengono invocati quelli dell'oggetto

Object non ha altri metodi

Se una variabile è Object, si possono solo invocare i metodi di Object, e non i metodi dell'oggetto (es move)

Soluzione alternativa

Questa soluzione non funziona

  static void inserisciPuntoOrdineDentro(
    LinkedList l, Point p) {

    int i;
    Point e;

    for(i=0; i<l.size(); i++) {
      e=(Point) l.get(i);
      if(e.x>=p.x) {
        l.add(i, p);
      }
    }
  }

Perchè?

Il problema

Quando arrivo al primo punto in cui e.x>=p.x, inserisco l'elemento

Però la condizione è vera anche per tutti gli elementi successivi

Il punto viene inserito più volte

Cicli e operazioni da fare una volta

A volte capita di dover fare una operazione a un certo punto del ciclo

Se l'operazione va fatta a tutte le iterazioni, non ci sono problemi

Se l'operazione va fatta una sola volta in tutte le iterazioni, occorre controllare che:

si esca dal ciclo subito dopo l'operazione
l'operazione stia in un if la cui condizione diventa vera una sola volta

Versione corretta

In questo caso, dopo l'inserimento, posso anche uscire:

  static void inserisciPuntoOrdineDentro(
    LinkedList l, Point p) {

    int i;
    Point e;

    for(i=0; i<l.size(); i++) {
      e=(Point) l.get(i);
      if(e.x>=p.x) {
        l.add(i, p);
        break;
      }
    }
  }

Ci sono casi in cui si deve continuare nel ciclo
in questi casi, bisogna controllare la condizione dell'if

Programma di prova

Creare una lista che contiene i punti di coordinate (0,0), ..., (9,9)

Inserire il punto di coordinate (2,4)

Soluzione

Faccio un ciclo

A ogni passo, creo un punto e lo aggiungo in fondo alla lista

    LinkedList l;
    l=new LinkedList();

    for(int i=0; i<10; i++) 
      l.add(new Point(i,i));

    stampaLista(l);
    inserisciPuntoOrdine(l, new Point(2,4));
    stampaLista(l);
  }

Per verificare la correttezza: stampare la lista sia prima che dopo

Se la stampate solo dopo, non sapete se è venuto bene oppure no

Esercizio difficile

Data una lista, creare quella che ha gli stessi elementi, in ordine inverso

Soluzione

Due soluzioni possibili:

scansione diretta della lista di partenza: ogni elemento lo aggiungo all'inizio della nuova lista
scansione inversa della lista, con aggiunta di elementi in fondo alla nuova lista

Soluzione 1

Verifica. All'inizio:

vecchia: 1 2 3 4 5
nuova:

Prendo il primo elemento, e lo metto all'inizio

vecchia: 1 2 3 4 5
nuova:   1

Secondo elemento della lista di partenza, all'inizio:

vecchia: 1 2 3 4 5
nuova:   2 1

Terzo elemento, sempre all'inizio:

vecchia: 1 2 3 4 5
nuova:   3 2 1

Ecc.

Soluzione 2

Verifica. All'inizio:

vecchia: 1 2 3 4 5
nuova:

Prendo l'ultimo elemento e lo metto in coda alla nuova lista:

vecchia: 1 2 3 4 5
nuova:   5

Penultimo elemento in coda:

vecchia: 1 2 3 4 5
nuova:   5 4

Terz'ultimo elemento in coda:

vecchia: 1 2 3 4 5
nuova:   5 4 3

Ecc.

Codice della soluzione 1

Inserire all'inizio: il nuovo elemento deve diventare quello di indice 0

  static LinkedList invertiLista(LinkedList l) {
    LinkedList nuova;
    nuova=new LinkedList();

    int i;

    for(i=0; i<l.size(); i++) {
      Object o;
      o=l.get(i);

      nuova.add(0, o);
    }

    return nuova;
  }

Esiste anche il metodo addFirst(Object)

Non è necessario saperlo:
add(0, oggetto) fa la stessa cosa

Codice della soluzione 2

  static LinkedList invertiLista(LinkedList l) {
    LinkedList nuova;
    nuova=new LinkedList();

    int i;

    for(i=l.size()-1; i>=0; i--) {
      Object o;
      o=l.get(i);

      nuova.add(o);
    }

    return nuova;
  }

Osservazione

Gli oggetti non sono stati copiati

Quando faccio nuova.add(o), sto mettendo nella lista il riferimento all'oggetto

La lista nuova contiene i riferimenti agli oggetti della vecchia lista, in ordine inverso

Copiare un oggetto arbitrario

  // non funziona
  Object o=new Point(12,3);
  Object b=o.clone();

Non si può clonare un oggetto generico

Motivo: ci sono oggetti che non si possono clonare (es. le stringhe)

Dato che tutti i metodi di Object sono ereditati, l'unico modo per permettere questo era di rendere clone di Object non accessibile (protected)

Soluzione (parziale)

Si può fare solo per oggetti specifici:

  static LinkedList invertiListaPoint(LinkedList l) {
    LinkedList nuova;
    nuova=new LinkedList();

    int i;

    for(i=l.size()-1; i>=0; i--) {
      Point p;
      p=(Point) l.get(i);

      Point q=(Point) p.clone();

      nuova.add(q);
    }

    return nuova;
  }

Eliminazione elementi

Metodo remove

Si passa un indice intero

Toglie dalla lista l'elemento:

Prima:      [abcd, efgh, eft]
Istruzione: l.remove(1);
Dopo:       [abcd, eft]

Viene eliminato l'elemento che sta in posizione 1

Esercizio

Scrivere un metodo statico che elimina la prima stringa di lunghezza pari da una lista di stringhe

Lista di stringhe=so che tutti gli elementi sono stringhe
(non esiste il tipo ``lista di stringhe'', si tratta comunque di una lista di Object)

Soluzione

Faccio un ciclo di scansione

Quando trovo una stringa di lunghezza pari, la elimino

Codice della soluzione

Quando ho trovato l'elemento, posso anche uscire dal ciclo

  static void eliminaPrimaPari(LinkedList l) {
    int i;
    String s;

    for(i=0; i<l.size(); i++) {
      s=(String) l.get(i);

      if(s.length()%2==0) {
        l.remove(i);
        break;
      }
    }
  }

Variante più difficile

Eliminare tutte le stringhe di lunghezza pari

Sembra più facile, ma non lo è

Soluzione che non funziona

Ciclo di scansione con eliminazione di tutte le stringhe di lunghezza pari

  static void eliminaPariSbagliato(LinkedList l) {
    int i;
    String s;

    for(i=0; i<l.size(); i++) {
      s=(String) l.get(i);

      if(s.length()%2==0)
        l.remove(i);
    }
  }

Perchè non funziona?

Un programma su cui non funziona (prox pagina)

Un programma con cui non funziona

Eseguendo questo programma:

  public static void main(String args[]) {
    LinkedList l;
    l=new LinkedList();

    l.add("abcde"); l.add("efg");
    l.add("ef"); l.add("efgh");
    l.add("xxx");

    System.out.println(l);

    eliminaPariSbagliato(l);

    System.out.println(l);
  }
}

Viene stampato:

[abcde, efg, ef, efgh, xxx]
[abcde, efg, efgh, xxx]

La stringa efgh non è stata eliminata!

Assunzione del ciclo

Quando ho scritto il ciclo, ho fatto queste assunzioni:

le stringhe di lunghezza pari che ho già considerato sono state tutte eliminate dalla lista
ad ogni iterazione del ciclo, considero una nuova stringa

In questo caso, l'assunzione 2 è sbagliata!

Cosa è successo

Lista di partenza:

Lista: [abcde, efg, ef, efgh, xxx]
Indici: 0      1    2   3     4

Quando i=2 ho s="ef", che è di lunghezza pari

La elimino, e ottengo:

Lista: [abcde, efg, efgh, xxx]
Indici: 0      1    2     3

Ora, il corpo del ciclo è finito, per cui si incrementa i e si passa alla prossima iterazione

Prossima iterazione: i=3, per cui considero la stringa s="xxx"

La stringa "efgh" è stata saltata

L'assunzione che non vale

Non è vero che ogni iterazione considera un nuovo elemento

Ci sono elementi che vengono saltati

Quando elimino un elemento, quello successivo viene ignorato, e si passa subito a quello dopo ancora

Altra soluzione

Se ho eliminato un elemento, considero anche il successivo:

  static void eliminaPariSbagliatoDue(LinkedList l) {
    int i;
    String s;

    for(i=0; i<l.size(); i++) {
      s=(String) l.get(i);

      if(s.length()%2==0) {
        l.remove(i);
        s=(String) l.get(i);

        if(s.length()%2==0) 
          l.remove(i);
      }
    }
  }

Non funziona se la lista contiene tre stringhe di lunghezza pari in sequenza

Progettazione

L'algoritmo di partenza è corretto:

  per ogni elemento della lista
    se e' di lunghezza pari, eliminalo

L'errore è che il ciclo non considera tutti gli elementi

Raffinamento dell'algoritmo

La frase per ogni elemento della lista la traduco in un ciclo:

  elemento=primo elemento

  finche' non sono alla fine della lista {
    elimina elemento se e' pari
    passa al prossimo elemento
  }

L'errore è che passa al prossimo elemento non è i++

Se ho eliminato un elemento, non serve fare i++ per passare al prossimo

Implementazione

Scrivo lo stesso ciclo di prima

Però i++ lo eseguo solo se non ho eliminato l'elemento

  static void eliminaPari(LinkedList l) {
    int i;
    String s;

    i=0;
    while(i<l.size()) {
      s=(String) l.get(i);

      if(s.length()%2==0)
        l.remove(i);
      else
        i++;
    }
  }

Attenzione alla terminazione!

Quando si scrivono cicli while, bisogna verificare che il ciclo prima o poi termini

Come: quando si esegue il corpo del ciclo, deve cambiare qualcosa

Alla fine, la condizione deve diventare falsa

Liste di dati scalari

In una LinkedList ci posso mettere solo oggetti, non interi, reali, ecc.

Come posso realizzare una lista di interi?

Soluzione

Definisco una classe con una sola componente intera

Questa classe esiste già:

La classe Integer è una classe in cui posso mettere un intero:

  Integer i;

È un oggetto!

creare un oggetto: i=new Integer(12); gli passo il valore da mettere dentro
trovare il valore: i.intValue() ritorna il valore intero

Esempio: creazione di una lista di interi

Ogni volta che devo inserire un valore, devo creare l'oggetto con dentro il valore

import java.util.*;

class ListaInteri {
  public static void main(String args[]) {
    LinkedList l;
    l=new LinkedList();

    int i;
    for(i=0; i<10; i++)
      l.add(new Integer(i));

    System.out.println(l);
  }
}

Usare i valori

Scrivere un metodo che somma i valori di una lista di interi

Nota: non si possono sommare gli oggetti di tipo Integer con +

Soluzione

Dato che so che la lista contiene solo interi, posso fare il cast

  static int somma(LinkedList l) {
    int i;
    int somma=0;
    Integer v;

    for(i=0; i<l.size(); i++) {
      v=(Integer) l.get(i);
      somma=somma+v.intValue();
    }

    return somma;
  }

Osservazioni

Attenzione: l.get(i).intValue() non funziona!

Motivo: l.get(i) è un Object

È vero che il metodo invocato è quello dell'oggetto,
ma questo succede solo se è un metodo ridefinito

Non funziona se il metodo non si trova anche nella sovraclasse

Nel nostro caso, Object non ha il metodo intValue

Esercizio

Data una lista di interi, eliminare l'elemento immediatamente successivo a ogni elemento di valore pari

Soluzione provvisoria

Ciclo: per ogni elemento, se è pari, elimino il successivo

  static void dopoPari(LinkedList l) {
    int i;
    Integer v;

    for(i=0; i<l.size(); i++) {
      v=(Integer) l.get(i);

      if(v.intValue()%2==0)
        l.remove(i+1);
    }
  }

Attenzione ai casi limite!

Il metodo va quasi bene

Se però l'ultimo elemento della lista è pari, si cerca di eliminare un elemento che non c'è

Questo genera un errore in esecuzione

Varianti

faccio il ciclo solo fino al penultimo

    for(i=0; i<l.size()-1; i++) {
      v=(Integer) l.get(i);

      if(v.intValue()%2==0)
        l.remove(i+1);
    }

controllo prima di eliminare

    for(i=0; i<l.size(); i++) {
      v=(Integer) l.get(i);

      if(v.intValue()%2==0)
        if(i+1<l.size())
          l.remove(i+1);
    }

Caso limite sul primo elemento

Se un elemento ha valore pari, eliminare quello prima

Non va eliminato l'elemento prima di quello in posizione 0, anche se è di valore pari

Esercizio facile

Scrivere un metodo statico che conta quante volte un oggetto appare in una lista

  static int conta(LinkedList l, Object o) {
    ...
  }

Tempo: 2 minuti max

Soluzione

Uso un contatore: ogni volta che trovo un elemento che è equals a o, lo incremento di uno

  static int conta(LinkedList l, Object o) {
    int quante=0;
    int i;

    for(i=0; i<l.size(); i++)
      if(o.equals(l.get(i)))
        quante++;

    return quante;
  }

Esercizio più difficile

Data una lista, verificare se c'è qualche elemento che si ripete più di una volta

  static boolean ripetizioni(LinkedList l) {
    ...
  }

Come si risolve:

dare la soluzione a parole
tradurla in codice

Soluzione a parole

per ogni elemento della lista
  se appare piu' di una volta
    ritorna true

ritorna false

A questo punto, si tratta di tradurre ogni parte di questo algoritmo

Per ogni elemento

È chiaramente un ciclo:

for(i=0; i<l.size(); i++)
  se l.get(i) c'e' piu' di una volta
    ritorna true;

ritorna false;

I due ritorna sono chiaramente dei return

Manca solo da tradurre: sta piu' di una volta nella lista

Più di una volta?

Posso risolvere il problema cosí:

  conta quante volte c'e' l'elemento
                          [nella lista
  vedi se e' >1

Vantaggio:

so già come è fatto il metodo per contare
il resto è facile

Scrivo il metodo per contare, anche se poi mi serve solo per vedere se un elemento è ripetuto!

Il metodo fa qualcosa in più: va bene lo stesso

Soluzione complessiva

Serve anche il metodo conta

  static int conta(LinkedList l, Object o) {
    int quante=0;
    int i;

    for(i=0; i<l.size(); i++)
      if(o.equals(l.get(i)))
        quante++;

    return quante;
  }

  static boolean ripetizioni(LinkedList l) {
    int i;

    for(i=0; i<l.size(); i++)
      if(conta(l, l.get(i))>1)
        return true;

    return false;
  }

Nota sui requisiti

Quando un problema richiede: ``scrivere un metodo che...''

Si intende: ``ed, eventualmente, tutti i metodi ausiliari necessari''

Scrivere metodi ausiliari ha due vantaggi:

spesso, sono uguali/simili a metodi visti a lezione
il codice del metodo da scrivere risulta più semplice

Semplicità del codice

Se il codice è più semplice, è più facile non commettere errori

Codice senza metodo ausiliario:

  static boolean
      ripetizioniNoAux(LinkedList l) {
    int i, j;
    int conta;

    for(i=0; i<l.size(); i++) {
      conta=0;

      for(j=0; j<l.size(); j++) 
        if(l.get(i).equals(l.get(j)))
          conta++;

      if(conta>1)
        return true;
    }

    return false;
  }

Nei cicli nidificati (l'uno dentro l'altro), è facile sbagliare

Esempio:

usare i al posto di j,
mettere conta=0 fuori da tutti e due i cicli,
mettere return true all'interno di tutti e due i cicli
ecc.

A volte i cicli nidificati servono

Meglio fare due metodi, se la cosa che fa il ciclo interno si può realizzare con un metodo

Unico metodo con doppio ciclo

Altra soluzione

per ogni elemento
  se si trova anche in un'altra posizione
    return true;

return false;

Implementazione

In questo modo, non funziona:

  static boolean ripetizioni(LinkedList l) {
    int i, j;

    for(i=0; i<l.size(); i++)
      if(l.contains(l.get(i)))
        return true;

    return false;
  }

Motivo: l.get(i) si trova nella lista

Se faccio l.contains(l.get(i)) ritorna per forza true

Altra implementazione

Dato che l.contains non va bene, faccio cosí:

per ogni elemento della lista, faccio un ciclo che, per ogni altro elemento della lista, verifica l'uguaglianza

  static boolean ripetizioni(LinkedList l) {
    int i, j;

    for(i=0; i<l.size(); i++)
      for(j=0; j<l.size(); j++)
        if(l.get(i).equals(l.get(j)))
          return true;

    return false;
  }

Non funziona nemmeno questo!

Cicli nidificati

Quando ho una coppia di cicli nidificati:

    for(i=0; i<l.size(); i++)
      for(j=0; j<l.size(); j++)
        corpo;

Questo corrisponde a:

i=0;
for(j=0; j<l.size(); j++)
  corpo;
i=1;
for(j=0; j<l.size(); j++)
  corpo;
...

Quindi, la prima volta che eseguo il corpo risulta i=0 e j=0

Per un qualsiasi valore di i, il ciclo su j viene eseguito tutto, per cui c'è una iterazione in cui j vale quanto i

Soluzione numero 1

Stesso ciclo, ma controllo che sia i!=j

Ossia, la lista contiene due elementi uguali se ci sono due indici diversi i e j che contengono due elementi uguali

  static boolean ripetizioni(LinkedList l) {
    int i, j;

    for(i=0; i<l.size(); i++)
      for(j=0; j<l.size(); j++)
        if((i!=j) && (l.get(i).equals(l.get(j))))
          return true;

    return false;
  }

Soluzione numero 2

Per ogni elemento, verifico solo se c'è un elemento uguale nelle posizioni successive

Perchè funziona?

Se sono arrivato all'elemento 4 vuol dire che non ci sono ripetizioni, fino a questo momento

Quindi, non possono esserci elementi prima uguali a questo

Quindi, devo guardare solo gli elementi successivi

  static boolean ripetizioni(LinkedList l) {
    int i, j;

    for(i=0; i<l.size(); i++)
      for(j=i+1; j<l.size(); j++)
        if(l.get(i).equals(l.get(j)))
          return true;

    return false;
  }

Nota sui cicli nidificati

Quando ci sono due cicli:

  for(i=0; i<n, i++) {

    for(j=0; j<m; j++) {
      istruzioni;
    }

  }

Le istruzioni più interne vengono eseguite n*m volte

Dopo aver scritto un programma con due cicli, l'uno dentro l'altro, verificate se effettivamente bisognava fare n*m iterazioni

Per vedere se ci sono elementi ripetuti: è necessario. Infatti, per ogni elemento devo fare la scansione di tutta la lista per vedere se c'è un elemento uguale

Unfolding dei cicli nidificati

  for(i=0; i<n, i++)
    for(j=0; j<m; j++)
      corpo;

L'unfolding del ciclo esterno si può vedere cosí:

i=0;
for(j=0; j<m; j++)
      corpo;
i=1;
for(j=0; j<m; j++)
      corpo;

...

Il ciclo interno viene eseguito una volta per ogni valore di i

Facendo anche l'unfolding del ciclo interno:

i=0;
j=0;
corpo;
j=1;
corpo;
j=2;
corpo;
...

i=1;
...

I valori di i,j seguono questa sequenza:

0,0
0,1
0,2
0,3
...
0,m

1,0
1,1
1,2
...
1,m

...

Differenza liste-array

Nelle liste si possono eliminare/aggiungere elementi in mezzo

L'accesso agli elementi di un array è più efficiente (non richiede di guardare gli oggetti precedenti della catena)

Liste

Breve riepilogo

Ridefinizione dei metodi di Object

Oggetti con dentro altri oggetti

Catene di tre oggetti

Catene di lunghezza arbitraria

Nomenclatura

Creazione di una lista

Aspetto di una lista collegata

Creazione primo oggetto

Creazione secondo nodo

Situazione alla fine

Liste con oggetti arbitrari

Catene di oggetti, in memoria

Cosa posso fare con una lista

Cosa succede se si inserisce un elemento

Eliminazione di un elemento

Come si fanno le operazioni

Tipo LinkedList

Come si usa

Stampa della lista

Stampa della lista

Trovare la lunghezza di una lista

Inserire un elemento in mezzo

Numerazione degli elementi

Regola degli indici

Dove va l'elemento?

Esercizio

Soluzione

Mettere null

Variante

Soluzione

Ordine risultante

Trovare un elemento

Cast sugli elementi

Perchè devo fare il cast?

Conversione a Object

Graficamente

Esercizio

Soluzione

Osservazione

Esercizio

Soluzione

Implementazione della soluzione

Più facile

Verifica coordinate negative

Metodo del risultato parziale

Non esiste la componente x

Variabile e oggetto

Cast

Soluzione corretta

Osservazione

Altro esercizio

Soluzione

Trovare la posizione giusta

Versione che non funziona

Non esiste la componente x

Variabile e oggetto

Cast

Soluzione corretta

Metodi non ridefiniti

Metodi e componenti

Caso tipico

Soluzione alternativa

Il problema

Cicli e operazioni da fare una volta

Versione corretta

Programma di prova

Soluzione

Esercizio difficile

Soluzione

Soluzione 1

Soluzione 2

Codice della soluzione 1

Codice della soluzione 2

Osservazione

Copiare un oggetto arbitrario

Soluzione (parziale)

Eliminazione elementi

Esercizio

Ridefinizione dei metodi di `Object`

Tipo `LinkedList`

Mettere `null`

Conversione a `Object`

Non esiste la componente `x`

Non esiste la componente `x`