Giorgio De Chirico
DEFINIZIONE DI LISTA CONCATENATA
• Consideriamo una nuova modalità di memorizzare i dati in cui l’accesso non avviene più tramite un indice, che individua la posizione del dato nella struttura, ma tramite un indirizzo di memoria.
• Per costruire una sequenza di informazioni è necessario che ogni dato della struttura memorizzi l’indirizzo di memoria dell’elemento successivo.
• Si costruisce pertanto una struttura di dati collegata, chiamata lista concatenata.
Un elemento, o nodo, di una lista concatenata oltre all’informazione memorizza anche il riferimento dell’elemento successivo: per rappresentare il nodo, abbiamo bisogno di un record con due (o più) campi di tipo diverso:
dato: info
riferimento: succ
NODO
• Il nodo sarà composto da :
• l’informazione: un elemento di tipo base o un record o un array, …
• il riferimento sarà un riferimento ad un nodo: un riferimento ad un elemento dello stesso tipo del nodo.
DIFFERENZA RISPETTO UN ARRAY
• Le informazioni memorizzate non sono più necessariamente contigue in memoria, come nell’array
• La lista concatenata non ha una dimensione stabilita a priori; dobbiamo però individuarne la fine, vale a dire un valore per il riferimento con il quale non si acceda ad alcun nodo.
• Tale valore nel C++ è NULL
Sintassi della definizione della lista:
Confronto molto sintetico tra utilizzo di un array o l’utilizzo di una list:
L’array richiede “spostamento” di dati (O(n)) nel caso di inserimento e cancellazione, che per la lista sono O(1);
- possiede invece accesso diretto, che è O(1), mentre la lista accesso sequenziale, che è O(n).
Meglio:
per un’alta movimentazione di dati conviene usare una lista per un’accesso puntuale meglio un vettore.
INSERIMENTO DI UN ELEMENTO IN UNA LISTA
| p=new tipolista | inizializzo il nodo |
| p->info=1; | inserisco 1 nel campo info del nodo |
| p->succ=inizio; | metto a null il campo puntatore essendo il primo della lista e per adesso non punta a nessun altro nodo |
| inizio=p; | il puntatore inizio punta al primo nodo |
| fine=p; | il puntatore fine punta all’ultimo nodo che in questo caso è anche il primo, serve per inserire un nodo alla coda della lista |
INSERIMENTO DI UN NUOVO ELEMENTO ALL’INIZIO DELLA LISTA
questa volta il puntatore non è null ma memorizzerà l’indirizzo di memoria del nodo che era in testa che era memorizzato nel puntatore inizio.
Meglio: il puntatore inizio è fondamentale per tenere sempre in memoria l’indirizzo del nodo di partenza della lista.
I nodi sono collegati tra loro solo dalla memorizzazione dell’area di memoria che potrebbe essere anche non contigua!
INSERIMENTO DI UN NUOVO ELEMENTO IN CODA
da notare che per poter inserire in coda ad una lista si deve aver definito precedentemente un puntatore che punta sempre alla coda della lista.
PRIMA CONCLUSIONE
Si crea ogni volta un oggetto formato da un binomio: il dato ed un contenitore per l’indirizzo di memoria. Quest’ultimo assumerà sempre il valore null se è l’ultimo nodo altrimenti l’indirizzo di memoria del nodo successivo.
Sono isole separate che si collegano solo mediante degli indirizzi.
LETTURA DELLA LISTA
come si nota copio il puntatore che punta sempre al primo elemento (ha l’indirizzo di memoria del primo elemento) e poi per scorrerla copio sempre il contenuto dei singoli nodi.
Ecco il listato completo
