Emulare una 'Lista Lineare' mediante una Struttura di testa ed i Puntatori

Nel linguaggio C una "Lista Lineare" (Linked List) è una serie ordinata e concatenata di Strutture omogenee che occupano posizioni di memoria non necessariamente consecutive.

L'ultimo membro di ciascuna Struttura, o elemento della Lista, è un Puntatore alla Struttura successiva. In questo senso la Lista concatenata è formata - appunto - da una concatenazione di Strutture, ove ciascuna Struttura fa riferimento ad un'altra Struttura. Se si è giunti all'ultimo elemento (Struttura) della Lista Lineare, il suo Puntatore è nullo (non punta ad alcunché).

Nella sostanza le Linked List sono particolari Strutture, che si collegano fra loro come una sorta di catena e che servono a memorizzare in modo dinamico una grande quantità non predefinita di dati.

Questo genere di Strutture si usa, quando non si conosce a priori quanti dati dovranno essere memorizzati; ed allora viene occupata memoria poco per volta, quando serve. Il primo dato viene "rintracciato" da un puntatore, che punta alla prima struttura. Dentro la prima struttura, oltre ai dati rilevanti, c'è - come ultimo suo membro - un Puntatore alla Struttura successiva, e così via a catena.

Va precisato che le "Liste Lineari" (Linked List) attualmente non sono previste nel linguaggio Gambas: non esiste un oggetto "Linked List"; e pertanto non possono essere utilizzate. Possiamo, però, emulare il loro comportamento e funzionamento in Gambas mediante una variabile del tipo della Struttura modello, posta alla testa della Lista concatenata, e alcune variabili di tipo Puntatore di appoggio.

Mostriamo un esempio commentato:

' Impostiamo la "Struttura" modello, molto semplice, che rappresenterà il primo elemento della "Lista Lineare" concatenata, ed ove...
Public Struct STRUTTURA
  i As Integer
' ...l'ultimo membro è un "Puntatore" che servirà a creare e connettere questa Struttura al secondo elemento della "Lista Lineare":
  p As Pointer
End Struct


Public Sub Main()
 
 Dim st As STRUTTURA
 Dim i As Integer
  
  st = Crea_Lista()
  
  Visualizza_Dati(st)
  
  Free(st.p)
  
End


Private Function Crea_Lista() As STRUTTURA
 
 Dim nw, sr As STRUTTURA
 Dim p As Pointer
 Dim b As Byte
   
' Crea la prima 'Struttura' della "Lista Lineare":
  nw = New STRUTTURA
  
' Viene impostato il valore del membro di tipo 'Intero' della prima 'Struttura' (ossia la primo elemento "Lista Lineare"):
  Print "Immettere dato del 1° elemento/Struttura della 'Lista Lineare':"
  nw = Immette_Valore(nw)
  
' Alloca un'area di memoria riservata per il nuovo (il secondo) elemento della "Lista Lineare":
  nw.p = Alloc(Object.SizeOf(STRUTTURA), 1)
  sr = nw
  
' Creiamo una catena di altri 3 elementi/Strutture, in modo tale che
' la "Lista Lineare" sarà formata in totale da 4 elementi/Strutture:
  For b = 2 To 4
    sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
    sr = sr.p
    Print "Immettere il dato del "; b; "° elemento/Struttura:"
    sr = Immette_Valore(sr)
  Next
  sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
  sr = sr.p
  
  Return nw
  
End


Private Function Immette_Valore(ra As STRUTTURA) As STRUTTURA
   
 Dim s As String
  
  Input s
  If IsDigit(s) = False Then Error.Raise("Il valore immesso non è un numero !")
  ra.i = Val(s)
   
  Return ra
    
End


Private Procedure Visualizza_Dati(tt As STRUTTURA)
 
 Dim po As Pointer
 
  Print "\n\nValori inseriti nella 'Lista Lineare':\n"
  
  While Not IsNull(tt.p)
    Print tt.i
    po = tt.p
    tt = tt.p
    Free(po)
  Wend
  
End