C++: liste concatente con puntatori

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

 

Informazioni su Francesco Bragadin

Insegno informatica e telecomunicazioni al liceo scienze applicate ed all'indirizzo informatica e telecomunicazioni. Ho terminato gli studi in ingegneria elettronica e telecomunicazioni lavorando per molti anni come libero professionista nell'ambito della gestione storage e disaster recovery su mainframe.
Questa voce è stata pubblicata in Senza categoria. Contrassegna il permalink.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *