Home

Federica EU

1/32

Valeria Vittorini » 13.Esercitazione. Strutture Dati: Lista Concatenata

Liste concatenate

In una lista concatenata gli elementi sono memorizzati in strutture (che chiameremo NODI) allocate dinamicamente
Ciascun nodo deve mantenere -oltre all’elemento della lista- anche l’indirizzo in memoria del nodo successore, cioè del nodo che mantiene l’elemento successivo nella lista secondo l’organizzazione lineare degli elementi
Pertanto in una lista concatenata:
Gli elementi non sono memorizzati in locazioni contigue di memoria
Ciascun elemento deve essere memorizzato in un nodo (record) che mantiene anche il collegamento all’elemento successivo
I nodi sono allocati dinamicamente
NOTA: Una lista concatenata può anche essere doppia: in questo caso ogni nodo porta il riferimento sia al suo predecessore che al suo successore. Le liste trattate in questo corso sono liste semplicemente concatenate (è previsto solo il collegamento al nodo successivo) ma per brevità ci riferiremo ad esse come a “liste concatenate”.

Rappresentazione della struttura dati

La struttura dati è costituita da un puntatore che memorizza l’indirizzo del primo elemento della lista.
Se la lista è vuota il puntatore alla testa è posto a 0 (NULL)
Avendo a disposizione l’indirizzo del primo elemento, è possibile raggiungere da esso tutti gli altri elementi nella lista, seguendo la “catena” di puntatori
In figura è mostrato il concetto di catena: a partire dal puntatore alla testa (chiamato l) tutti i nodi sono collegati tra loro grazie all’informazione mantenuta in ogni nodo:
l punta al primo nodo, in cui un campo contiene un puntatore che punta al secondo nodo della lista che a sua volta ha un campo contenente un puntatore che punta al terzo nodo e così via fino a raggiungere l’ultimo nodo, il cui campo “puntatore al prossimo” contiene il valore 0.

Lista concatenata.

Il NODO della lista

La realizzazione di una lista concatenata richiede quindi che venga definito un record per rappresentare il “nodo” della lista.
In figura è mostrata una definizione del tipo Record, “nodo della lista”.Il Record è logicamente costituito da due campi:
- Un campo elem di tipo E (defnito ad esempio mediante un tpedef) che rappresenta il contenuto informativo (può essere di tipo atomico o a sua volta un tipo strutturato).
- Un campo punt di tipo puntatore che serve a creare il collegamento tra un nodo della lista ed il prossimo nodo.

Definizione del "nodo" della lista concatenata

Collegamento tra due nodi

Ogni nodo deve essere allocato dinamicamente in area heap.
Il campo puntatore di ogni nodo deve contenere l’indirizzo di memoria del nodo sussessivo nella lista.
Nell’esempio in figura, il tipo E è il tipo intero. Il nodo contenente l’elemento informativo di valore 5 è allocato in memoria all’indirizzo 01011001. Il nodo successivo il cui elemento informativo è 6, si trova all’indirizzo 01011010. Pertanto collegare i due nodi significa assegnare al campo puntatore al prossimo del primo nodo il valore 01011010
Graficamente questo collegamento è rappresentato da una freccia da un nodo al successivo
Si noti che campo puntatore al prossimo del nodo contenente l’elemento 6 è posto a 0 (zero, o NULL). Questo significa che non c’è un nodo successivo a quello di elemento 6.

Collegamento tra due nodi

Definizione della Struttura Dati

Nel seguito supponiamo che la sttruttura dati sia definita come in figura.
La predichiarazione del tipo Record può rendersi necessaria alla compilazione del codice relativo alla definizione della struct Record che è “ricorsiva”a causa della presenza del campo punt.
Il nome L (associato tramite typedef al tipo Record *) è utile per sottolineare che il puntatore alla testa della lista rappresenta di fatto la lista stessa.

Definizione della Struttura Dati

Creazione e collegamento dei nodi della lista

Le seguenti linee di codice C++ mostrano come creare e inizializzare i nodi e come realizzare il collegamento tra due nodi.

Allocazione dinamica del nodo: Record * q=new Record;

L’operatore new alloca lo spazio di memoria necessario a mantenere una variabile di tipo Record e ritorna l’indirizzo all’area di memoria allocata in area heap. Per poter raggiungere il nodo allocato tale indirizzo viene assegnato ad un puntatore (q) di tip Record *

Creazione e collegamento dei nodi della lista (segue)

2. Inizializzazione del nodo:

Lo spazio allocato da new non è inizializzato. Le due istruzioni seguenti inizializzano i campi del record, elem viene inizializzato al valore 5 e punt al valore 0 (NULL). Il nodo creato ed inizializzato è rappresentato in figura.

q->elem=5; q->punt=0;

RICHIAMO: Si ricorda che l’operatore -> viene applicato ad una variabile puntatore a record per accedere direttamente ai campi del record puntato. La notazione ptr->nomecampo ha pertanto il seguente significato: il puntatore ptr viene de-referenziano e viene effettuato l’accesso al campo nomecampo del record puntato da ptr.

Un nodo inizializzato

Creazione e collegamento dei nodi della lista

3. Collegamento di due nodi:

Si supponga di aver creato ed inizializzato un secondo nodo al valore intero 6 ed il suo puntatore al prossimo al valore 0 ripetendo i passi 1. e 2. appena descritti. Si supponga che l’indirizzo in memoria di questo secondo nodo sia stato assegnato al valore del puntatore p. Collegare i due nodi significa assegnare al campo puntatore al prossimo del primo nodo l’indirizzo del secondo (che è memorizzato nel puntatore p):

q->punt=p;

La precedente istruzione sovrascrive il valore 0 nel campo punt del nodo puntato da q. La situazione è ora quella in figura. Graficamente, come si è già detto, l’avvenuto collegamento è rappresentato dalla freccia orientata dal nodo “5″ al nodo “6″.

Collegamento tra due nodi

Operazioni su una lista concatenata

Vediamo ora come si realizzano le principali operazioni su una lista concatenata.
Esamineremo inizialmente le operazioni già prese in considerazione nella progettazione delle strutture dati pila e coda:
- Start (Inizializzazione della struttura dati)
- Inserimento in testa
- Inserimento in coda
- Ricerca sequenziale
- Eliminazione in testa
- Analisi dell’elemento di testa
- Calcolo dei predicati empty e full
In un secondo momento discuteremo il caso della lista ordinata

Start, Empty e Full

La funzione Start deve creare la lista vuota. A tale scopo è sufficiente porre il puntatore alla testa a zero. L’implementazione della funzione è dunque la seguente:

void start(L& l) {l=0;}

I predicati Empty e Full hanno lo stesso significato introdotto in precedenza. Si noti che nel caso di lista concatenata la funzione full deve essere fornita solo per mantenere la compatibilità dell’interfaccia con la rappresentazione mediante vettore: la lista concatenata infatti non ha limiti di capacità.

La lista è vuota se e solo se il puntatore alla testa è posto a zero. Pertanto l’implementazione della funzione empty è la seguente:

bool empty(const L& l) { return (l==0); }

L’implementazione della funzione full per quanto sopra osservato è:

bool full(const L& l) { return false; }

Inserimento in testa

Per inserire un nuovo nodo in testa ad una lista bisogna effettuare i seguenti passi:

Creare ed inizializzare il nuovo nodo
Collegare il nuovo nodo alla lista in modo che il successore del nuovo nodo sia l’attuale primo elemento della lista
Aggiornare il puntatore alla testa della lista

Il primo ed il secondo passo sono stati appena discussi, il collegamento deve essere effettuato quindi tra il nuovo nodo allocato (il cui indirizzo è memorizzato dal puntatore q) al primo elemento della lista (il cui indirizzo è memorizzato nel puntatore alla testa della lista l).
Le istruzioni corrispondenti ai tre passi sopra definiti sono riportati in figura (dove è omessa l’inizializzazione del valore informativo del nuovo nodo).
Qui e nel seguito ono riportati in blu i collegamenti che vengono modificati/eliminati, in rosso i nuovi collegamenti.

Inserimento in testa

Osservazione

L’operazione di inserimento di un elemento in testa alla lista che abbiamo esaminato può essere effettuata anche nel caso in cui la lista sia vuota.
Se la lista è vuota infatti il puntatore alla testa l assume il valore 0. L’istruzione q->punt=l quindi sovra-scrive il campo puntatore al prossimo del nuovo nodo…riassegnadogli il valore 0! (come è giusto che sia, visto che in questo caso il nuovo nodo si trova ad essere il primo e l’ultimo nodo presente nella lista).

Inserimento in coda

Definiamo un nuovo puntatore a Record temp. Supponiamo che temp sia stato assegnato all’indirizzo dell’ultimo nodo nella lista (basta scorrere la lista utilizzando temp come vedremo tra breve). Per inserire un nuovo nodo in testa ad una lista bisogna effettuare i seguenti passi:

Creare ed inizializzare il nuovo nodo.
Collegare il nuovo nodo alla lista in modo che il successore dell’ultimo elemento della lista sia il nuovo nodo.

Il collegamento tra l’ultimo nodo della lista (puntato da temp) ed il nuovo nodo (puntato da q) è effettuato semplicemente assegnando q al campo puntatore al prossimo dellultimo nodo temp->punt, come in figura.

Inserimento in coda

Osservazione

Anche l’operazione di inserimento di un nodo in coda alla lista può essere effettuata correttamente nel caso in cui la lista sia vuota, a patto che il nuovo nodo sia stato correttamente inizializzato. In questo caso infatti il campo puntatore al prossimo del nuovo nodo (q->punt) contiene il valore 0.

Eliminazione in testa

Eliminare il nodo in testa da una lista comporta la modifica del puntatore l alla testa in modo che punti al nodo successivo all’attuale primo. In questo modo l’elemento da eliminare viene “staccato” dalla lista e il puntatore alla testa della lista è posizionato su quello che era il secondo nodo. Bisogna quindi effettuare i seguenti passi:

Salvare l’indirizzo dell’attuale primo elemento della lista in un puntatore temporaneo.
Modificare il puntatore alla testa l assegnandoli l’indirizzo del nodo successivo.
Deallocare il nodo eliminato in modo da liberare lo spazio da esso occupato in area heap. Questa ultima operazione non è funzionale alla eliminazione, che è avvenuta al passo 2, ma è necessaria se il nodo non deve essere riutilizzato al fine di non produrre aree di memoria non più raggiungibili (e quindi inutilizzabili).

Si noti che l’indirizzo del secondo nodo si trova nel campo puntatore al prossimo del primo elemento della lista, memorizzato nel puntatore alla testa. Pertanto modificare l affichè punti al nodo successivo significa assegnare ad l l’indirizzo contenuto nel campo l->punt.
Le istruzioni corrispondenti ai tre passi sopra definiti sono riportati in figura a lato.

Eliminazione in testa

Osservazione

Nel caso in cui il nodo da eliminare sia l’unico nodo presente nella lista, l’operazione di eliminazione in testa produce correttamente la lista vuota.
Infatti, se nella lista è presente un unico nodo, il suo campo puntatore al prossimo deve contenere il valore zero. L’istruzione l=l->punt quindi assegna al puntatore alla testa l il valore 0.

Eliminazione in coda

Definiamo un nuovo puntatore a Record temp. Supponiamo che temp sia stato assegnato all’indirizzo del PENULTIMO nodo nella lista (anche questa volta basta scorrere la lista utilizzando temp). Eliminare il nodo in coda significa assegnare al campo puntatore al prossimo del puntatore temp il valore 0. In questo modo l’ultimo nodo da eliminare viene “staccato” dalla lista. Bisogna quindi effettuare i seguenti passi:

Salvare l’indirizzo dell’attuale ultimo elemento della lista in un puntatore temporaneo.
Modificare il puntatore al prossimo del penultimo elemento assegnandogli il valore 0.
Deallocare il nodo eliminato in modo da liberare lo spazio da esso occupato in area heap. Vale quanto detto per il passo 3) della eliminazione in testa.

Le istruzioni corrispondenti ai tre passi sopra definiti sono riportati in figura a lato.

Eliminazione in coda

Visita di una lista concatenata

Con il termine “visita” si intende lo scorrimento sequenziale della lista, a partire dall’elemento di testa. Durante lo scorrimento su ogni nodo si può eventualmente effettuare una elaborazione (ad esempio la stampa a video dell’elemento informativo).

Per scorrere una lista è necessario utilizzare un puntatore di appoggio che viene inizializzato al valore del puntatore alla testa.
Al generico passo il puntatore di appoggio viene aggiornato con il valore del campo puntatore al prossimo.
Lo scorrimento ha termine quando il puntatore di appoggio assume il valore 0 (posizionato cioè oltre l’elemento di coda).
Il codice riportato nell’esempio si riferisce alla implementazione della visita di una lista concatenata ai fini della stampa a video degli elementi informativi in essa contenuti. L’algoritmo è iterativo.

Esempio. Funzione per la stampa di una lista concatenata

Osservazione

E’ possibile “fermare” lo scorrimento nel punto desiderato della lista modificando la condizione nel while.
Nel caso ad esempio in cui si voglia scorrere la lista per posizionare il puntatore temp sull’ultimo nodo, la condizione richiesta è che il suo campo puntatore al prossimo sia 0: while(temp->punt).
L’inserimento e l’eliminazione in coda possono quindi avvalersi di una visita (specificando l’opportuna condizione di terminazione del ciclo) per posizionare il puntatore temp.

Lista Ordinata: rappresentazione con lista concatenata

Lista ordinata

La struttura dati è quella descritta in precedenza, i nodi sono allocati dinamicamente e la struttura dati è assimilata al puntatore alla testa della lista.
Le operazioni devono garantire l’ordinamento.
Detto “L” il tipo Lista e T il tipo degli elementi da gestire, una progettazione dell’interfaccia è riassunta in figura.

Progettazione dell'interfaccia della struttura dati Lista Ordinata

Inserimento in ordine

Supposto per ipotesi che la lista sia ordinata secondo una relazione d’ordine totale definita sugli elementi in essa contenuti, l’inserimento di un nuovo elemento deve mantenere l’ordinamento e richiede che vengano effettuati i seguenti passi:

Ricerca della posizione di inserimento.
Creazione e inizializzazione del nuovo nodo.
Aggiornamento dei puntatori per l’inclusione del nuovo nodo.

Si noti che possono verificarsi le seguenti situazioni:

La lista è vuota oppure la posizione di inserimento è la testa della lista.
La posizione di inserimento è in coda.
La posizione di inserimento è interna alla lista.

Nel primo caso il problema è risolto effettuando un inserimento in testa.
Il secondo ed il terzo caso possono essere trattati insieme.

Inserimento di un elemento interno alla lista (segue)

La ricerca della posizione richiede la visita della lista confrontando al generico passo del ciclo l’elemento informativo contenuto nel nodo corrente con il valore dell’elemento da inserire.
Lo scorrimento in questo caso termina quando si raggiunge un nodo che secondo l’ordinamento definito sugli elementi dovrà essere il successivo a quello da inserire.
Poiché la lista è semplicemente concatenata, durante lo scorrimento sarà necessario utilizzare due distinti puntatori, in modo da mantenere sia l’indirizzo dell’elemento corrente sia l’indirizzo del suo predecessore, in modo da avere tutte le informazioni necessarie all’aggiornamento dei puntatori coinvolti nell’inclusione nella lista del nuovo nodo.

Inserimento di un elemento interno alla lista

Siano pertanto prec il puntatore al nodo che deve precedere il nodo da inserire nella lista, e succ il puntatore al nodo che deve seguire il nodo da inserire nella lista. Bisogna eseguire i seguenti passi:

Creare ed inizializzare il nuovo nodo;
Modificare i collegamenti in modo che il successore del nuovo nodo sia il nodo il cui indirizzo è mantenuto dal puntatore succ;
Modificare i collegamenti in modo che il predecessore del nuovo nodo sia il cui indirizzo è mantenuto dal puntatore prec.

Le istruzioni corrispondenti ai tre passi sopra definiti sono riportati in figura a lato.

Inserimento di un nodo interno alla lista

Osservazione

Nel caso in cui il nuovo nodo debba essere inserito in coda, il puntatore succ assumerà valore 0 all’uscita da ciclo, pertanto l’istruzione: q->punt=succ; assegnerà il valore 0 al campo puntatore al prossimo del nuovo nodo che infatti deve risultare l’ultimo nodo della lista.

Eliminazione di un elemento da una lista ordinata

Supposto per ipotesi che la lista sia ordinata secondo una relazione d’ordine totale definita sugli elementi in essa contenuti, e che inoltre siano verificate le precondizioni “lista non vuota” e “esistenza dell’elemento nella lista“, l’eliminazione di un elemento richiede che vengano effettuati i seguenti passi:

Ricerca della posizione di eliminazione;
Aggiornamento dei puntatori per “staccare” il nodo da eliminare dalla lista;
Deallocazione del nodo eliminato.

Si noti che possono verificarsi le seguenti situazioni:

Il nodo da eliminare è la testa della lista;
Il nodo da eliminare è in coda.
Il nodo da eliminare è interno alla lista.

Nel primo caso il problema è risolto effettuando una eliminazione in testa.
Il secondo ed il terzo caso possono essere trattati insieme.

Eliminazione di un elemento interno alla lista

La ricerca della posizione richiede la visita della lista confrontando al generico passo del ciclo l’elemento informativo contenuto nel nodo corrente con il valore dell’elemento da eliminare.
E’ conveniente effettuare lo scorrimento “guardando in avanti”, la visita termina quando si raggiunge il nodo che precede il nodo da eliminare nella lista.

Eliminazione di un elemento interno alla lista (segue)

Definiamo un nuovo puntatore a Record prec. Supponiamo che a seguito dello scorrimento della lista prec sia stato assegnato all’indirizzo del nodo che precede il nodo da eliminare nella lista.
Eliminare il nodo significa assegnare al campo puntatore al prossimo del puntatore prec l’indirizzo del nodo che segue il nodo da eliminare. In questo modo il nodo da eliminare viene “saltato” staccandolo dalla lista. Bisogna quindi effettuare i seguenti passi:

Salvare l’indirizzo del nodo da eliminare in un puntatore temporaneo.
Modificare il campo puntatore al prossimo del nodo che lo precede assegnandogli l’indirizzo contenuto nel campo puntatore al prossimo del nodo da eliminare.
Deallocare il nodo eliminato in modo da liberare lo spazio da esso occupato in area heap. Vale quanto detto per il passo 3) della eliminazione in testa.

Le istruzioni corrispondenti ai tre passi sopra definiti sono riportati in figura a lato.

Eliminazione di un nodo interno alla lista

Osservazione

Nel caso in cui il nodo da eliminare sia l’ultimo nodo della lista, il suo campo puntatore al prossimo contiene il valore 0. Pertanto l’istruzione: prec->punt=prec->punt->punt; assegna a prec->punt il valore 0.
Dunque il nodo puntato da prec è correttamente diventato l’ultimo nodo della lista.

Lista concatenata vs rappresentazione mediante array

L’analisi della complessità computazionale degli algoritmi sulle strutture dati non è tra i temi trattati nel presente corso. E’ opportuno però fermarsi almeno un momento per fare alcune considerazioni.
La gestione di una lista concatenata può essere molto vantaggiosa rispetto alla rappresentazione della lista tramite array. L’eliminazione o l’inserimento di un elemento in un vettore infatti richiedono l’esecuzione di un ciclo che fisicamente sposti tutti gli elementi del vettore dal punto di inserimento/cancellazione in poi.
In generale un ulteriore vantaggio è dato dalla occupazione di memoria commisurata all’effettiva necessità e alla possibilità di rilasciare le aree non più utilizzate in seguito alla cancellazione di un elemento.

Lista concatenata vs rappresentazione mediante array

Ciò nonostante in alcuni casi la rappresentazione mediante array può essere preferibile.
Ad esempio nel caso si debbano trattare liste ordinate di grandi dimensioni su cui l’operazione predominante è la ricerca. la rappresentazione mediante lista concatenata non consentirebbe di adottare un algoritmo di ricerca binaria, computazionalmente molto più vantaggioso rispetto alla ricerca lineare.
In conclusione, in generale la scelta della rappresentazione da utilizzare per una struttura dati deve essere sempre frutto di una attenta fase di analisi e progettazione, che tenga conto anche degli aspetti legati alla complessità computazionale degli algoritmi utilizzati nella implementazione delle operazioni che su di essa devono essere eseguite.

Esercizi completi

E’ fornito di seguito il codice relativo alla realizzazione di due esercizi completi:
Il primo propone una possibile implementazione di lista concatenata non ordinata.

Mostra codice
Mostra codice

Il secondo propone una possibile implementazione di lista concatenata ordinata.

Mostra codice
Mostra codice

Gli algoritmi realizzati sono iterativi, rimandando ad una successiva lezione la realizzazione di algoritmi ricorsivi sulle liste concatenate.
Si fornisce il modulo relativo all'implementazione della struttura dati. Lo studente svilupperà l'opportuno programma utente per provare il funzionamento della lista.