10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
Info( P) pNext( P) Generico Nodo P
TIPO Nodo = RECORD Info: < Tipo _ dato > pNext: PUNTATORE A Nodo
FINE RECORD
con < Tipo _ dato > semplice o strutturato a sua volta possibile anche se apparentemente sembra un riferimento circolare
Graficamente avremo:
NULL
P Testa |
P k-1 |
P k |
P k + 1 |
N. B. In una struttura dati concatenata( o LISTA LINKATA) la successione LOGICA dei nodi è arbitraria e non corrisponde in alcun modo a quella FISICA.
Infatti in queste strutture non è assolutamente necessario che la locazione( fisica) di memoria in cui si trova il nodo Pk generico debba essere successiva a quella dove si trova il nodo Pk-1 oppure debba essere precedente a quella dove si trova il nodo Pk + 1( come invece accadrebbe in un array).
Il nodo Pk può essere memorizzato dovunque: l’ importante è che il nodo Pk-1 contenga tra le sue informazioni l’ indirizzo della locazione di memoria dove si trova il nodo Pk( ossia“ punti al nodo”
Pk) e che quest’ ultimo a sua volta contenga l’ indirizzo della locazione di memoria dove si trova il nodo Pk + 1( ossia“ punti al nodo” Pk + 1)
Questa regola basilare va mantenuta per tutti i nodi della struttura concatenata ad eccezione dell’ ultimo nodo della struttura che non deve puntare a nessun nodo in quanto non ha successori.
Con questa regola abbiamo visto che ogni nodo punta al successivo( il primo al secondo, il secondo al terzo … il penultimo all’ ultimo) ma nessuno di essi è in grado di puntare al primo nodo della struttura.
N. B. L’ indirizzo di memoria del primo nodo è infatti una informazione necessaria ma esterna alla struttura dati concatenata.
Esso dovrà essere memorizzato in un apposita variabile che chiameremo puntatore alla testa( PTesta) della struttura dati che conterrà il riferimento( ossia il puntatore) al primo nodo ed è“ esterno alla lista linkata”, mentre l’ ultimo nodo, che non ha successori, non dovrà fare riferimento ad alcunchè( ossia“ punta a terra” per convenzione avrà il valore NULL).
Inoltre con le STRUTTURE DATI CONCATENATE non sarà possibile l’ accesso diretto ma quello sequenziale che prevede la scansione di tutta la struttura a partire dal primo nodo fino ad arrivare a quello desiderato.
NOTA BENE
Le LISTE A PUNTATORI sono le strutture dati messe a disposizione dai linguaggi C e C ++ per poter implementare le LISTE LINKATE appena descritte, le cui funzionalità devono, al contrario di altri linguaggi di programmazione in cui sono già previste o built-in( vedi PYTHON), essere interamente sviluppate dal programmatore attraverso le apposite funzionalità per la gestione dinamica della memoria( malloc(), calloc(), realloc(), etc.)
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 41