Un argomento che difficilmente affronto a lezione di informatica in un istituto tecnico e perlopiù lo accenno in C/C++. Interessante però vederne una realizzazione in Java sfruttando i paradigmi della programmazione ad oggetti e senza usare strutture dati notevoli e preconfezionate come gli ArrayList. L’esercizio è piuttosto ampio ma ricopre diverse richieste e difficoltà classiche degli esercizi su liste, dalla ricerca, ordinamento, scambio di elementi ed, ovviamente, inserimento e cancellazione testa/coda o posizione scelta.
L’esempio scelto è volutamente generico: un nodo su cui effettuare i vari ragionamenti di lista e un contenuto del nodo, in questo caso il classico oggetto Persona. Sostituendo Persona con una qualsiasi classe a scelta o utilizzando il template generico Object, l’esempio di questo articolo può facilmente essere adattato a molti altri esercizi analoghi.
Commentiamo i vari listati individuando possibili criticità.
Indice dei contenuti
Classe Persona
Il primo è della classe Persona. Se l’alunno ha affrontato con successo l’approccio alla programmazione ad oggetti, la classe Persona non dovrebbe presentare alcuna difficoltà di implementazione e, probabilmente, è un esempio standard già affrontato. Qui si è riscritto e semplificato il metodo toString() per una stampa personalizzata. Il resto presenta costruttori e metodi di accesso piuttosto semplici.
package liste;
/**
*
* @author alfredo centinaro
*/
class Persona {
// Attributi
private String nome;
private String cognome;
private String indirizzo;
private int annonascita;
private char sesso;
// Costruttori
public Persona()
{
this.nome = "";
this.cognome = "";
this.indirizzo = "";
this.annonascita = 1970;
this.sesso = 'M';
}
public Persona(String nome, String cognome, String indirizzo, int annonascita) {
this.nome = nome;
this.cognome = cognome;
this.indirizzo = indirizzo;
this.annonascita = annonascita;
this.sesso = 'M';
}
public Persona(String nome, String cognome, String indirizzo, int annonascita, char sesso) {
this.nome = nome;
this.cognome = cognome;
this.indirizzo = indirizzo;
this.annonascita = annonascita;
this.sesso = sesso;
}
public String getNome() {
return nome;
}
public void setNome(String nome) {
this.nome = nome;
}
public String getCognome() {
return cognome;
}
public void setCognome(String cognome) {
this.cognome = cognome;
}
public String getIndirizzo() {
return indirizzo;
}
public void setIndirizzo(String indirizzo) {
this.indirizzo = indirizzo;
}
public int getAnnonascita() {
return annonascita;
}
public void setAnnonascita(int annonascita) {
this.annonascita = annonascita;
}
@Override
public String toString() {
return "Persona{" + "nome=" + nome + ", cognome=" + cognome +
", indirizzo=" + indirizzo + ", annonascita=" + annonascita + '}';
}
}Classe Nodo
A questo punto per preparare la nostra lista dobbiamo costruire una classe Nodo. Ogni Nodo si concatena agli altri con un puntatore next e “porta con se” una istanza di Persona nella componente info. E’ una classe piuttosto standard nella sua funzione di lista. Lasciamo l’approfondimento ai manuali di testo dell’alunno che legge.
Uniche scelte forse meno intuitive sono sul costruttore. Ne abbiamo uno per creare una istanza di nodo sia vuota, sia con parametro Persona, il più intuitivo, sia il costruttore di copia che prende come parametro un altro nodo per copiarne il contenuto. Il metodo toString( ) è personalizzato per stampare non le informazioni del nodo, quanto quelle dell’istanza di Persona che contiene.
package liste;
/**
*
* @author alfredo centinaro
*/
public class Nodo
{
protected Persona info;
protected Nodo next;
//costruttori
public Nodo()
{
this.info = null;
this.next = null;
}
public Nodo(Persona p)
{
this.info = p;
this.next = null;
}
public Nodo(Nodo n)
{
this.info = n.getInfo();
this.next = null;
}
public Persona getInfo() {
return info;
}
public void setInfo(Persona info) {
this.info = info;
}
public Nodo getNext() {
return next;
}
public void setNext(Nodo next) {
this.next = next;
}
@Override
public String toString() {
return this.info.toString();
}
}
Classe Lista
A questo punto dobbiamo creare una lista di nodi e contemplare i vari frammenti di codice che servono alla sua gestione. Essendo in OOP, niente di meglio che creare una classe Lista e creare i vari metodi per la sua gestione direttamente immersi nella classe. Qui la parte di codice sicuramente più impegnativa. Suggerisco però al lettore più attento, di non avventurarsi subito nella scrittura del codice in base alle richieste ma di affrontare prima la stesura di metodi di “utilità”. I metodi di utilità apparentemente sono insignificanti ma semplificano poi la scrittura del codice di richieste più complesse, permettendo di concentrarsi solo sulle difficoltà non legate strettamente ad iteratori o particolarità delle liste.
I metodi/problemi affrontati sono aggiungi un nodo in testa alla lista. E’ stato sviluppato in due modalità o prende un nodo e quindi procede con l’aggiunta, oppure prende una istanza di persona, crea un nodo e quindi procede ad aggiungere in testa spostando opportunamente i puntatori.
Analogamente per aggiungi un nodo in coda. Sfruttiamo il comodo metodo di utilità ultimo per posizionarci in fondo alla coda e procedere all’aggiunta o di un nodo o di un nodo costruito partendo da una persona.
Più ostici i metodi di cancellazione, soprattutto se in mezzo alla lista con la ricerca di un nodo che risponde a determinate caratteristiche. Qui si deve operare un taglia e cuci procurandosi però i riferimenti ai nodi precedenti e successivo a quello da eliminare.
package liste;
import java.util.Random;
/**
*
* @author alfredo centinaro
*/
public class Lista
{
private Nodo testa;
public Lista()
{
this.testa = null;
}
Nodo ultimo()
{
Nodo iteratore = this.testa;
if (this.testa == null)
return null;
while (iteratore.getNext() != null)
{
iteratore = iteratore.getNext();
}
return iteratore;
}
int lunghezza()
{
Nodo iteratore = this.testa;
int contatore = 0;
if (this.testa == null)
return 0;
while (iteratore != null)
{
contatore++;
iteratore = iteratore.getNext();
}
return contatore;
}
Nodo posizione(int _posizione)
{
int posizione = 0;
Nodo tmp = this.testa; //individua il nodo cercato
while(tmp != null)
{
if (posizione == _posizione)
{
return tmp;
}
tmp = tmp.getNext();
posizione++;
}
return null; //non dovrebbe mai presentarsi!
}
public void aggiungiInCoda(Nodo n)
{
if (this.testa == null)
{
this.testa = n;
return;
}
Nodo ultimo = this.ultimo();
//System.out.println(ultimo.toString());
ultimo.setNext(n);
//System.out.println(n.toString());
}
public void aggiungiInCoda(Persona p)
{
Nodo n = new Nodo(p);
this.aggiungiInCoda(n);
}
public void aggiungiInTesta(Nodo n)
{
Nodo tmp = testa;
this.testa = n;
this.testa.setNext(tmp);
}
public void aggiungiInTesta(Persona p)
{
Nodo n = new Nodo(p);
aggiungiInTesta(n);
}
public String toString()
{
String stampa = "";
Nodo tmp = this.testa;
while(tmp != null)
{
stampa += tmp.toString() + "\n";
tmp = tmp.getNext();
}
return stampa;
}
public void eliminaPerNomeCognome(String _nome, String _cognome)
{
Nodo tmp = this.testa; //individua il nodo cercato
Nodo precedente = null; //tiene traccia del nodo prima di quello cercato
while(tmp != null)
{
if (tmp.info.getNome() == _nome && tmp.info.getCognome() == _cognome)
{
//trovato il nodo, "cucio" il precedente, annullo il trovato
precedente.setNext(tmp.getNext());
tmp = null;
return; //forzo uscita finita l'eliminazione
}
precedente = tmp;
tmp = tmp.getNext();
}
}
public void eliminaInTesta()
{
this.testa = this.testa.getNext();
}
public void eliminaInPosizione(int _posizione)
{
int posizione = 0;
Nodo tmp = this.testa; //individua il nodo cercato
Nodo precedente = null; //tiene traccia del nodo prima di quello cercato
if (_posizione == 0)
{
this.eliminaInTesta();
return;
}
while(tmp != null)
{
if (posizione == _posizione)
{
//trovato il nodo, "cucio" il precedente, annullo il trovato
// se non è l'ultimo
if (tmp.getNext() != null)
precedente.setNext(tmp.getNext());
//annullo il nodo trovato
tmp = null;
return; //forzo uscita finita l'eliminazione
}
precedente = tmp;
tmp = tmp.getNext();
posizione++;
}
}
public void aggiungiInPosizione(Nodo n, int _posizione)
{
int posizione = 0;
Nodo tmp = this.testa;
Nodo precedente = null; //tiene traccia del nodo prima di quello cercato
if (_posizione == 0)
{
this.aggiungiInTesta(n);
return;
}
while(tmp != null)
{
if (posizione == _posizione)
{
precedente.setNext(n);
n.setNext(tmp);
return;
}
precedente = tmp;
tmp = tmp.getNext();
posizione++;
}
}
public void aggiungiInPosizione(Persona p, int _posizione)
{
Nodo n = new Nodo(p);
aggiungiInPosizione(n,_posizione);
}
public void aggiungiInPosizioneCasuale(Persona p)
{
Nodo n = new Nodo(p);
Random r = new Random();
int posizione = r.nextInt(0, this.lunghezza());
aggiungiInPosizione(n, posizione);
}
public int annoDiNascitaMedio()
{
int media = 0;
int somma = 0;
Nodo iteratore = this.testa;
while(iteratore != null)
{
somma += iteratore.getInfo().getAnnonascita();
iteratore = iteratore.getNext();
}
media = (int)(somma / this.lunghezza());
return media;
}
/**
* sposta il nodo in _posizione alla _posizione -1
* @param _posizione
*/
public void spostaNodoAlPrecedente(int _posizione)
{
Nodo posizione = this.posizione(_posizione);
Nodo precedente = this.posizione(_posizione - 1);
Nodo pre_precedente = this.posizione(_posizione - 2);
if (_posizione > 1)
{
pre_precedente.setNext(posizione);
precedente.setNext(posizione.getNext());
posizione.setNext(precedente);
}
if (_posizione == 1) //invertire testa con prim nodo
{
//scambio testa e secondo nodo!
Nodo tmp = this.testa;
this.testa = posizione;
tmp.setNext(posizione.getNext());
this.testa.setNext(tmp);
System.out.println("Scambio in testa");
}
}
public void spostaNodoAlSuccessivo(int _posizione)
{
Nodo posizione = this.posizione(_posizione);
Nodo successivo = posizione.getNext();
Nodo precedente = this.posizione(_posizione -1);
precedente.setNext(successivo);
posizione.setNext(successivo.getNext());
successivo.setNext(posizione);
}
/**
* qui imbroglio, non sposto proprio il nodo
* ma i loro contenuti
* TODO: prevedere la versione con taglia e cuci dei due nodi
* @param da posizione
* @param a posizione
*/
public void spostaNodo(int da, int a)
{
Nodo nodoDa = this.posizione(da);
Nodo nodoA = this.posizione(a);
Nodo nodoTMP;
nodoTMP = new Nodo(nodoDa);
nodoDa.setInfo(nodoA.getInfo());
nodoA.setInfo(nodoTMP.getInfo());
}
public void riordinoCasuale()
{
//creo una lista copia
Nodo new_head;
Nodo iteratore;
int posizione = 0;
boolean duplicato = true;
Random r = new Random();
int[] numeriCasuali = new int[100];
for (int i =0; i < this.lunghezza(); i++)
{
while(duplicato)
{
posizione = r.nextInt(0, this.lunghezza());
duplicato = false;
for (int j =0; j < i; j++)
if (posizione == numeriCasuali[j] )
duplicato = true;
}
duplicato = true;
numeriCasuali[i]= posizione;
}
//scelgo un elemento da mettere/copiare in testa
//System.out.print(posizione);
new_head = new Nodo(this.posizione(numeriCasuali[0]));
iteratore = new_head;
for (int i =1; i < this.lunghezza(); i++)
{
posizione = numeriCasuali[i];
//System.out.println(posizione);
iteratore.setNext(new Nodo(this.posizione(numeriCasuali[i])));
iteratore = iteratore.getNext();
}
//sovrascrivo la lista originale con la copia
this.testa = new_head;
}
public void ordinaPerDataNascita()
{
Nodo iteratore1;
Nodo iteratore2;
for (int i = 0; i < (this.lunghezza()-1); i++)
{
iteratore1 = this.posizione(i);
for (int j=i+1; j < (this.lunghezza()); j++)
{
iteratore2 = this.posizione(j);
if (iteratore2.getInfo().getAnnonascita() <
iteratore1.getInfo().getAnnonascita())
{
this.spostaNodo(i, j);
}
}
}
}
}
Metodi di utilità
Notiamo i metodi di utilità:
- Nodo ultimo() -> restituisce un iteratore che si posiziona sull’ultimo nodo
- int lunghezza() -> torna la lunghezza della lista, molto utile se si aggiungono nodi in diversi elementi del programma
- Nodo posizione(int) -> restituisce un iteratore sul nodo posto in posizione da parametro, partendo da zero. Evita di dover ripetere cicli
- void spostaNodo(int , int) -> scambia i lcontenuto di due nodi individuati dalla loro posizione
lunghezza e posizione sono decisamente molto utilizzati negli altri metodi e snellscono decisamente il codice.
Classe Main
Infine la classe di test col metodo Main. Gli alunni trascurano spesso di testare il codice, di fatto mettendosi un brutto voto da soli. Non sottovalutare mai di testare il codice, al di la che venga richiesto o meno dall’esercizio. Qui abbiamo creato una lista con alcuni nodi di prova. Abbiamo quindi lanciato tutti i metodi scritti curando di suddividere la stampa con delle linee tratteggiate. Abbiamo anche scritto codice in modo da verificare l’esito dei metodi attivi, stampando la lista prima e dopo le varie modifiche effettuate. Qualche riga di codice in più ma ne guadagna pulizia e chiarezza di quello che si testa. Il concetto sfugge forse all’alunno che mira solo al risultato: scrivere codice di qualità, commentare e stampar una descrizione in più a video fa la differenza.
package liste;
/**
*
* @author alfredo centinaro
*/
public class Main {
public static void main(String[] args)
{
Lista lis = new Lista();
lis.aggiungiInCoda(new Persona("Alfredo", "Centinaro", "paizza Garibaldi 4", 1982));
lis.aggiungiInCoda(new Persona("Mario", "Rossi", "paizza Verdi 10", 1980));
lis.aggiungiInCoda(new Persona("Luigi", "Pallavicini", "paizza Covour 21", 1992));
lis.aggiungiInCoda(new Persona("Ludovico", "Betoven", "via Mozart 1", 1770));
lis.aggiungiInCoda(new Persona("Leonardo", "Da Vinci", "via firenze 11", 1452));
System.out.println("------------------------------------------------------------------------");
System.out.println("Lista: ");
System.out.print(lis.toString());
System.out.println("------------------------------------------------------------------------");
System.out.println("Lunghezza lista: " + lis.lunghezza());
System.out.println("Anno medio: " + lis.annoDiNascitaMedio());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
lis.aggiungiInTesta(new Persona("Dante", "Alighieri", "via dei Guelfi 29", 1200));
System.out.println("Lista Aggiunto in testa: ");
System.out.print(lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Elimina per nome/cognome: ");
lis.eliminaPerNomeCognome("Mario", "Rossi");
System.out.print(lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Aggiungi in posizione 1 (parto da 0): ");
lis.aggiungiInPosizione(new Persona("Cristoforo", "Colombo", "via Vespucci 11", 1450),1);
System.out.print(lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Elimina in testa: ");
lis.eliminaInTesta();
System.out.print(lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Elimina in posizione 2: ");
lis.eliminaInPosizione(2);
System.out.print(lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Aggiungi in posizione casuale: ");
lis.aggiungiInPosizioneCasuale(new Persona("Alessandro", "Manzoni", "via Napoleone 12", 1745));
System.out.print(lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Sposta in posizione precedente il 4: ");
System.out.print("PRIMA: \n" + lis.toString());
lis.spostaNodoAlPrecedente(4);
System.out.print("DOPO: \n" + lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Sposta in posizione successiva il 4: ");
System.out.print("PRIMA: \n" + lis.toString());
lis.spostaNodoAlSuccessivo(3);
System.out.print("DOPO: \n" + lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Riordino casuale: ");
System.out.print("PRIMA: \n" + lis.toString());
lis.riordinoCasuale();
System.out.print("DOPO: \n" + lis.toString());
System.out.println("");
System.out.println("------------------------------------------------------------------------");
System.out.println("Riordino per data: ");
System.out.print("PRIMA: \n" + lis.toString());
lis.ordinaPerDataNascita();
//lis.spostaNodoAlPrecedente(5);
System.out.print("DOPO: \n" + lis.toString());
}
}
Listati
Codice su GitHub -> https://github.com/alfredocentinaro/esercizi-java/tree/main/gestione-liste
Ultima modifica 26 Ottobre 2022