Strutture dati dinamiche: liste concatenate e cancellazione elementi

Strutture dati dinamiche

RICORDATI DI PRENDERE APPUNTI Le slide non sono esaustive

Introduzione alle Liste

Per lista si intende un insieme di elementi collegati tra loro da un rapporto di sequenzialità (lista della spesa, elenco delle cose da fare), cui si può accedere solo in maniera sequenziale, cioè partendo dal primo elemento arrivando fino all'ultimo. La lista concatenata è una struttura di dati in cui gli elementi sono organizzati in sequenza. Ogni elemento conosce qual è il suo successore e in questo modo, a partire dal primo elemento, è possibile ricostruire tutti gli elementi presenti nella lista.

Vantaggi delle Liste

Oltre a gestire strutture ordinate, la lista ha il vantaggio di inserire e cancellare i dati in modo più veloce rispetto ad altre soluzioni. Con le liste concatenate, dopo che è stata trovata la posizione, l'inserimento è immediato; la stessa operazione eseguita con un array risulta molto più lunga in quanto, per fare spazio al nuovo elemento, si devono spostare tutti gli elementi di un posto Ogni elemento della lista è composto da due parti

Componenti di un Elemento della Lista

Ogni elemento della lista è composto da due parti: una con il dato (o i dati) vero e proprio e l'altra con l'indicazione (link) dell'elemento successivo. Ogni elemento della lista ha un predecessore e un successore, tranne il primo elemento, che non ha predecessore, e l'ultimo, che non ha successore. A diffe- renza delle strutture statiche, in una struttura dinamica non si può accedere di- rettamente a un elemento: l'accesso è possibile solo con la scansione di tutti gli elementi della lista, a partire dal primo fino a quando non si incontra l'elemen- to desiderato. figura 1 La lista TESTA DATO 1 C DATO 2 C DATO 3 O DATO 4 O

Nodi e Riferimenti in una Lista

Una lista può essere vista come una successione di nodi, in cui ogni nodo è costituito dai dati relativi all'elemento stesso e da un riferimento al nodo successivo. Per tenere traccia di questa successione è necessario conoscere il riferimento al primo elemento della lista (testa) e all'ultimo elemento (coda). Il riferimento alla testa è utile perché, partendo da questo, è possibile scorrere l'intera lista eseguendo un'operazione chiamata di attraversamento. Il riferimento alla coda è utile per aggiungere rapidamente un elemento in fondo alla lista senza doverla scorrere per recuperare l'ultimo nodo

Rappresentazione Grafica di una Lista Concatenata

Graficamente, una lista concatenata può essere rappresentata nel seguente modo: LISTA testa coda null NODO NODO NODO

Allocazione in Memoria di una Lista

Fisicamente in memoria centrale gli elementi di una lista non occupano celle adiacenti di memoria ma sono allocati in celle di memoria arbitrarie: il link, che contiene l'indirizzo dell'elemento successivo, permette di definire la sequenza logica degli elementi. Per esempio, l'allocazione in memoria della lista della Figura 1 potrebbe essere quella mostrata nella figura 2. DATO3 DATO2 DATO1 Testa DATO4

Esempio di Allocazione in Memoria

In figura 3 è rappresentata la situazione della memoria centrale nel momento in cui il primo elemento della lista è allocato all'indirizzo 400, il secondo all'indi- rizzo 200, il terzo all'indirizzo 150 e il quarto all'indirizzo 560. Come si vede dalla figura, all'interno di ciascun elemento il campo link contiene l'indirizzo dell'elemento successivo, tranne per l'ultimo, che contiene un valore speciale che indica la fine della lista. DATO3 560 DATO2 150 DATO1 200 400 DATO4 X

Inserimento di un Dato in una Lista

È possibile inserire un nuovo elemento in qualunque posizione all'interno di una lista modificando in modo opportuno i collegamenti. Volendo inserire DATO5 dopo DATO1, è necessario modificare il link dell'elemento che lo precede (DATO1) assegnandogli il link DATO5 e, nel campo link di DATO5 , inserire il valore del link che inizialmente era contenuto in DATO1 (cioè il link a DATO2) figura 4 Inserimento di un dato in una lista TESTA DATO 1 O DATO 5 0 DATO 2 O DATO 3 O DATO 4 0

Memoria Centrale dopo l'Inserimento di DATO5

Nella figura 5 è rappresentata la situazione della memoria centrale quando è in- serito DATO5 dopo DATO1 all'indirizzo 640. DATO3 560 DATO2 150 DATO1 640 400 DATO4 X DATO5 200 figura 5 Memoria centrale dopo l'inserimento di DATO5

Cancellazione di un Elemento da una Lista

È possibile eliminare un elemento assegnando al link dell'elemento che lo precede l'indirizzo di quello che lo segue. Volendo cancellare DATO3 è sufficiente modificare il valore del link dell'elemento che lo precede (DATO2) assegnandogli il valore del link dell'elemento che deve essere cancellato. In questo modo DATO3 non è più raggiungibile e quindi non viene più preso in considerazione. figura 6 Cancellazione di un elemento da una lista TESTA DATO 1 O DATO 5 O DATO 2 O DATO 3 0 DATO 4 O

Memoria Centrale dopo la Cancellazione

Nella figura 7 è rappresentata la situazione della memoria centrale quando vie- ne eliminato DATO3: DATO2 560 DATO1 640 400 DATO4 X DATO5 200 figura 7 Memoria centrale dopo la cancellazione

Liste Concatenate in C++ e Java

Nel linguaggio C++ le liste concatenate vengono gestite utilizzando i puntatori. In Java vengono invece utilizzati i riferimenti agli oggetti che in pratica svolgono lo stesso ruolo dei puntatori, ma la cui gestione è in buona parte demandata al modulo runtime di Java. La lista concatenata viene schematizzata con il seguente diagramma di classe Lista concatenata testa coda inserisci elimina contiene

Operazioni di Modifica nelle Liste

Le operazioni di modifica sono:

• inserisci, che inserisce un elemento nella lista;
• elimina, che preleva un elemento specifico dalla lista

L'operazione di inserimento può essere a sua volta di vari tipi a seconda di come si vuole aggiungere l'elemento alla lista: gli elementi potrebbero essere aggiunti in te- sta, in coda oppure all'interno della lista, se occorre rispettare un particolare ordine nella generazione della lista. Ogni operazione di inserimento deve essere implementata con un metodo diverso.

Operazioni di Interrogazione nelle Liste

L'operazione principale di interrogazione è contiene, che controlla se nella lista è presente un particolare elemento. Esistono anche altre operazioni minori di interrogazione, per esempio un'operazione che controlla se la lista è vuota o un'operazione che conta gli elementi nella lista

Laboratorio: Gestione Appuntamenti Studio Dentistico

Si deve realizzare un'applicazione per la gestione dell'agenda degli appuntamenti di uno studio dentistico. Ogni appuntamento è caratterizzato dal nominativo del paziente e dalla data e ora dell'appuntamento. Gli appuntamenti devono essere memorizzati in ordine cronologico e in ogni momento deve essere possibile inserire un nuovo appuntamento, eliminare un appuntamento, e stampare l'elenco di tutti gli appuntamenti. Realizzare il diagramma delle classi e implementare l'applicazione, robusta e affidabile, tramite il linguaggio Java.

Le Liste per la Gestione degli Appuntamenti

Per realizzare un'agenda per la gestione degli appuntamenti, a seconda delle necessità, dovremo aggiungere nuovi appuntamenti, oppure eliminarne altri. In casi di questo tipo l'utilizzo di un array non offre la necessaria flessibilità: infatti fissare a priori un determinato numero di elementi può comportare un eccesso di elementi inutilizzati, oppure il trovarsi senza posizioni disponibili se il numero degli elementi cresce oltre il previsto.

Rappresentazione Grafica degli Appuntamenti

head info link info link info link info link null Appuntamento 1 Appuntamento 2 Appuntamento n-1 Appuntamento n

Inserimento di un Nuovo Appuntamento

Nuovo appuntamento 1 head 3 2 null + Appuntamento 1 Appuntamento 2 Appuntamento n-1 Appuntamento n

Diagramma UML delle Classi

Nodo -head : Nodo 1 0 .. 1 0 .. 1 -elementi : integer +Agenda() +Nodo(in appuntamento : Appuntamento) +getInfo() : Appuntamento +getLink() : Nodo +setLink(in link : Nodo) +aggiungi(in appuntamento : Appuntamento) +elimina(in data_ora : LocalDate Time) +appuntamenti() : Appuntamento [] 1 1 Appuntamento -data_ora : LocalDate Time -descrizione : string +Appuntamento(in anno : integer, in mese : integer, in giorno : integer, in ora : integer, in minuto : integer, in descrizione : string) +getDataOra() : LocalDate Time +getDescrizione() : string Nel diagramma UML precedente è evid ente che ogni oggetto di classe Nodo h a: · un attributo info (la componente inf ormativa) che riferisce un oggetto di classe Appuntamento; · un attributo link di classe Nodo che realizza il collegamento con un altro oggetto dello stesso tipo allo scopo di costituire l'intera sequenza. Gli oggetti di classe Agenda hanno co me attributi: · il riferimento al nodo iniziale head d ella lista; · il numero di nodi che in un determin ato istante sono concatenati nella lis ta. Agenda -info : Appuntamento -link : Nodo

Liste vs Array: Vantaggi e Svantaggi

	Vantaggi	Svantaggi
Array	· Semplicità di gestione. · Accesso diretto agli elementi.	· Gestione statica del numero degli elementi. · Difficoltà delle operazioni d'inserimento e cancellazione di elementi con criteri di ordinamento.
Lista	· Gestione dinamica del numero degli elementi. · Facilità nelle operazioni d'inserimento e cancellazione di elementi anche in presenza di criteri di ordinamento.	· Maggiore complessità di gestione rispetto all'array. · Struttura ad accesso strettamente sequenziale.

Rappresentazione Grafica di una Lista

head info link info link info link info link - null Appuntamento 1 Appuntamento 2 Appuntamento n-1 Appuntamento n · head è il riferimento d'ingresso alla struttura; · ogni elemento, denominato «nodo», della struttura è un oggetto ripartito logicamente in due componenti: una informativa (info), e una che realizza il collegamento all'elemento successivo (link); · l'ultimo nodo ha la componente link con valore null;

Implementazione in Java di una Lista: Classe Nodo

public class Nodo { private Tipo info; private Nodo link; public Nodo (Tipo oggetto) { info = new Tipo (oggetto) ; link = null; } public Tipo getInfo () { return new Tipo (info) ; } public void setLink (Nodo link) - this.link = link; } public Nodo getLink () { return link; } }

Implementazione in Java di una Lista: Classe Lista

public class Lista { private Nodo head; // riferimento al nodo iniziale // della lista private int elementi; // numero di elementi (nodi) della // lista public Lista () { head = null; elementi = 0; } . .. . . . . .. }