10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
IMPLEMENTAZIONE DELLE STRUTTURE DATI ASTRATTE LINEARI
A livello di codifica sono possibili due strategie implementative per le struttura dati astratte( ADT) descritte precedentemente:
a) attraverso strutture dati SEQUENZIALI, AD ALLOCAZIONE STATICA ED AD ACCESSO DIRETTO del linguaggio di programmazione scelto( ossia attraverso array o vettore);
b) attraverso strutture dati NON SEQUENZIALI, AD ALLOCAZIONE DINAMICA ED AD ACCESSO SEQUENZIALE del linguaggio di programmazione scelto( ossia attraverso le cosiddette liste linkate);
Limiti dell’ utilizzo di strutture dati SEQUENZIALI, AD ALLOCAZIONE STATICA ED AD ACCESSO DIRETTO
L’ allocazione statica della memoria presenta senza dubbio molti VANTAGGI tra i quali segnaliamo:
1) semplicità degli algoritmi che devono gestire la struttura dati così allocata; 2) accesso diretto ai nodi( poiché vengono utilizzati gli array o vettori).
Nonostante ciò tale metodo di memorizzazione possiede degli innegabili SVANTAGGI in quanto è poco flessibile per quanto riguarda:
a) occupazione di memoria: gli array in genere sono sovradimensionati non potendo stimare a priori la dimensione del problema;
b) velocità in fase di esecuzione: gli array sono strutture rigide e la loro gestione richiede a volte tempi che non sono accettabili;
c) linearità della soluzione: talvolta la soluzione offerta dall’ allocazione statica della memoria per questo tipo di strutture dati fornisce un risultato negativo sia in relazione alla bontà dell’ algoritmo, sia dal punto di vista del rispetto dei criteri generali della programmazione.
VANTAGGI nell’ utilizzo di strutture dati NON SEQUENZIALI, AD ALLOCAZIONE DINAMICA ED AD ACCESSO SEQUENZIALE
L’ utilizzo di strutture dati concatenate e dinamiche dette LISTE LINKATE( al posto di quelle sequenziali, statiche ad accesso diretto) permettono di gestire con molta più semplicità numerose operazioni di inserimento e di cancellazione.
Grazie al loro utilizzo non è più necessario neanche definire a priori la dimensione massima occupata in memoria dalla struttura dati in quanto esse hanno la caratteristica di essere dinamiche, ossia di potere modificare la dimensione occupata in memoria nel corso dell’ esecuzione del programma che le utilizza.
LA LISTA LINKATA
DEF. La lista( semplicemente) concatenata o linkata è la struttura dati di base ad allocazione dinamica. Essa è formata da una successione di nodi che occupano in memoria posizioni qualsiasi. Ciascun nodo è legato o collegato o linkato al suo successivo mediante un puntatore.
In una lista linkata ogni nodo P( quindi tutti i nodi hanno lo stesso formato) possiamo immaginarlo formato da un tipo di dati strutturato( RECORD) costituito da due campi:
- un campo informativo( che chiameremo Info) che può contenere qualsiasi tipo di dato( semplice o strutturato a sua volta);
- un campo puntatore( che chiameremo pNext) che contiene l’ indirizzo di memoria in cui è possibile reperire il nodo successivo.
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 40