Figura: lista linkata:
Il treno coi vagoni che abbiamo visto nella lezione 3 non e' altro che (salvo dettagli) un'implementazione del tipo di dato lista di interi (o meglio di un tipo di dato lista di interi, come vedremo).
Tipo di dati =
Il concetto di tipo di dato viene dall'algebra, dove piu' astrattamente si
studiano le proprieta' delle operazioni.
Noi invece studiamo concretamente le operazioni, cioe' come eseguirle.
Per eseguirle occorre tradurre tutto in un linguaggio di programmazione.
I linguaggi di programmazione orientati a oggetti, mediante le classi,
traducono direttamente la nozione di tipo di dato.
Un tipo di dati e' come una classe in Java:
Non esiste un solo dipo di dati, per un certo tipo (dipende dalle
operazioni che considero).
Non esiste una sola implementazione Java di un tipo di dati,
ne esistono varie...
Vediamo l'esempio delle liste di interi.
Il tipo di dato "lista di interi" ha come:
Esempi di operazioni sulle liste:
A seconda di quali operazioni scelgo, ottengo vari tipi di dati sulle liste.
Per esempio: la coda e' un tipo di dato lista che ha come operazioni:
Una volta stabilito quale tipo di dato vogliamo considerare per le liste (= quali operazioni che intendiamo considerare), dobbiamo ancora decidere come implementare:
Ci sono due modi principali di implementare le liste:
Figura: lista ad array:
Figura: lista linkata:
[Pro] Occupa meno memoria (una casella per ogni intero).
[Pro]
Veloci le operazioni che vanno direttamente ad una posizione
(es. ritornare l'elemento alla posizione i).
[Contro] lente le operazioni di inserimento e cancellazione
(deve spostare gli interi contenuti in tutte le caselle che
seguono la posizione modificata).
[Contro]
Occupa piu' memoria (due caselle per ogni intero: anche
quella per il puntatore al successivo).
[Pro]
Veloci le operazioni di inserimento e cancellazione
(basta spostare due puntatori).
[Contro]
Lente le operazioni che vanno ad una posizione specificata
(deve scorrere tutta la serie di caselle fino a quella voluta).
Un tipo di dato liste e' caratterizzato dall'insieme di operazioni. Nel nostro esempio scegliamo:
Scegliamo di implementare mediante liste linkate. La struttura del codice e' simile a quella del treno coi vagoni, dove:
class ListElem /* simile a Vagone */
{
int content; // l'intero contenuto qui
ListElem next; // collegamento al prossimo elemento
.....QUI CI SARANNO LE FUNZIONI.....
}
class List /* simile a Treno */
{
ListElem first; // collegamento al primo elemento
.....QUI CI SARANNO LE FUNZIONI.....
}
A differenza di Treno, List non ha informazioni sue, ma e' semplicemente un dispositivo di ingresso nella sequenza di ListElem che memorizzera' la sequenza di interi.
Vediamo le funzioni della classe List. Alcune di queste useranno per la loro implementazione una funzione ausiliaria di classe ListElem, che vedremo contestualmente.
Il costruttore crea la lista vuota, cioe' la lista che non ha collegata alcuna sequenza di elementi:
List() { first = null; }
La funzione che controlla se la lista e' vuota verifica se sussiste
questa condizione:
boolean isEmpty() { return (first==null); }
L'aggiunta di un intero in cima alla lista avviene sempre creando un nuovo elemento di lista per contenere tale intero. Se la lista e' vuota, semplicemente il nuovo elemento diventa il primo. Se non e' vuota, PRIMA di cio' occorre prendere l'attuale primo e porlo come prossimo del nuovo elemento.
void insert(int x)
{
ListElem n = new ListElem();
// ora n.content==0 e n.next==null
n.content = x;
if (first==null) first = n;
else
{ n.next = first;
first = n;
}
}
Devo scorrere la sequenza di elementi, partendo dal primo, fino a trovare l'intero cercato o arrivare alla fine della lista.
In programmazione orientata a oggetti si tende a far fare, ad ogni oggetto componente un oggetto complesso, la sua piccola parte di lavoro. Qui definiamo in ListElem una funzione ausiliaria che guarda se un intero e' presente in questo elemento di lista; se non puo' concludere passa poi il controllo al prossimo elemento.
// in classe ListElem
boolean isInThis(int x)
{
if (x==content) return true; // trovato, e' qui
else
{
if (next!=null) // non trovato ma la lista continua
return next.isInThis(x);
else // non trovato, finita la lista
return false;
}
}
Per quanto riguarda la lista, se e' vuota non puo' contenere
l'intero che cerco, se non e' vuota lo cerco nei vari elementi
a partire dal primo.
// in classe List
boolean isIn(int x)
{
if (first==null) return false;
else return first.isInThis(x);
}
Devo cercarlo e poi (se c'e') poi staccare l'elemento che lo contiene dalla lista. Quest'ultima cosa si fa modificando uno (o due) puntatori. Sia N l'elemento che sto staccando:
Figura: cancellazione di 34 (tratteggiati i puntatori nella situazione
precedente alla cancellazione)
Anche qui vogliamo distribuire il lavoro sui vari elementi della lista,
percio' definiamo una funzione ausiliaria nella classe ListElem.
Notiamo pero' che la modifica coinvolge due elementi: N e il suo
precedente.
La funzione ausiliaria avra' dunque due
argomenti di classe ListElem: quello implicito e un altro.
Quello implicito e' N e l'altro e' M (predecessore di N).
// in classe ListElem
void deleteFromThis(int y, ListElem prec)
{
if (y==content) // trovato, devo cancellare
{
// [*] siamo sicuri che prec!=null, ved. Nota 2 dopo
prec.next = next; // obbligatorio
next = null; // facoltativo
}
else
{
if (next!=null) next.deleteFromThis(y,this);
// altrimenti e' finita la lista, y non c'era
}
}
La funzione presente nella classe List:
// in classe List
void delete(int y)
{
if (first!=null)
{
if (first.content==y) first = first.next;
else first.deleteFromThis(y,null);
}
}
Nota 1:
Nella chiamata a deleteFromThis, il predecessore di first
non esiste ed e' rappresentato da null.