Torna alla pagina di Algoritmi e strutture dati
:: Liste in Java ::
Questa pagina contiene la mia implementazione delle liste spiegate dall'Aringhieri in Java. Tutti gli operatori etc. sono lì e pare che funzionino anche giusti.
Si tratta di una lista che memorizza solo Integer, per pura semplicità.
Come compilare il codice
Copiate quanto scritto qua sotto in un file che chiamarete listaint.java. Per compilarlo basta fare
javac listaint.java
e per lanciarlo
java listaint
Questo presuppone però che abbiate un'ambiente di compilazione Java già funzionante...
Se invece avete solo la Java Virtual Machine, allora scaricatevi questo JAR: Liste.jar Δ.
Per farlo partire:
java -jar Liste.jar
listaint.java
import java.util.*;
/** Questa è la Cella, cioè una singola posizione della lista
* Allo stato attuale contiene solo Integer
*/
class Cella {
Integer valore;
Cella next;
Cella prev;
}
/** La Lista implementa tutte gli operatori, e come nell'implementazione del libro,
* non fa nessun controllo sulle condizioni per comodità.
* Sta quindi a chi la usa controllare di non fare porcate
*/
class Lista {
/** Il costruttore inizializza la centinella*/
Lista () {
sentinella = new Cella();
sentinella.next = sentinella;
sentinella.prev = sentinella;
}
/**Ritorna vero se la lista è vuota, ovvero se
il prossimo elemento della sentinella è essa stessa*/
boolean listaVuota () {
if (sentinella.next == sentinella) return true;
else return false;
}
/**Ritorna il primo elemento della lista, ovvero quello che sta a
destra della sentinella.
Occorre controllare manualmente che la lista non sia vuota!
*/
Cella primoLista () {
return sentinella.next;
}
/**Ritorna l'ultimo elemento della lista, e valgono le considerazioni della cella
* precedente: occorre controllare manualmente che la lista non sia vuota
*/
Cella ultimoLista () {
return sentinella.next.prev;
}
/**Ritorna la cella successiva ad una cella data*/
Cella succLista (Cella chi) {
return chi.next;
}
/**Ritorna la cella precedente ad una cella data*/
Cella predLista (Cella chi) {
return chi.prev;
}
/**Ritorna vero se la cella è l'ultima della lista*/
boolean fineLista (Cella chi) {
return (chi.next == sentinella.next);
}
/**Restituisce il valore di una cella (si può accedervi direttamente,
però l'implementazione del libro è così*/
Integer leggiLista (Cella chi) {
return chi.valore;
}
/**Cambia il valore di una cella*/
void scriviLista (Integer value, Cella chi) {
chi.valore = value;
}
/**Inserisce una cella nuova a sinistra di una cella esistente (dove)*/
void insLista (Integer value, Cella dove) {
Cella nuova = new Cella();
nuova.valore = value;
/* Se ho la lista vuota, devo agire in modo particolare*/
if (listaVuota()) {
sentinella.next = nuova;
nuova.next = nuova;
nuova.prev = nuova;
}
else {
nuova.prev = dove.prev;
nuova.next = dove;
dove.prev.next = nuova;
dove.prev = nuova;
}
// dove = nuova;
}
/**Cancella dalla lista una cella esistente*/
void cancLista(Cella chi) {
chi.prev.next = chi.next;
chi.next.prev = chi.prev;
}
Cella sentinella;
}
public class listaint {
public static void main (String[] args) {
Lista lista = new Lista();
System.out.println("La lista è vuota? " + lista.listaVuota());
lista.insLista(new Integer(20),lista.primoLista());
lista.insLista(new Integer(30), lista.primoLista());
lista.insLista(new Integer(40), lista.primoLista());
Cella primo = lista.primoLista();
while (! lista.fineLista(primo)) {
System.out.println(primo.valore);
primo = lista.succLista(primo);
}
primo = lista.ultimoLista();
System.out.println("Valore dell'ultimoLista: " + primo.valore);
System.out.println("Valore del next di ultimoLista: " + primo.next.valore);
System.out.println("lista.ultimoLista() è veramente l'ultimo della lista? "+
lista.fineLista(primo));
primo = lista.primoLista();
System.out.println("Valore di primoLista: " + primo.valore);
System.out.println("Valore del next di primoLista: "+ primo.next.valore);
System.out.println("Valore del prev di primoLista: "+ primo.prev.valore);
System.out.println("Valore del next di primoLista: "
+ lista.succLista(primo).valore);
System.out.println("Valore del prev di primoLista: "
+ lista.predLista(primo).valore);
System.out.println("La lista è vuota? " + lista.listaVuota());
}
}
Torna alla pagina di Algoritmi e strutture dati - Programmazione