Emulare una Lista Lineare

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

Ogni Struttura rappresenta un "elemento" dell'intera "Lista lineare concatenata ".

L'ultimo membro di ciascuna Struttura (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. All'interno della prima struttura, oltre ai dati rilevanti, c'è - come ultimo suo membro - un Puntatore alla Struttura successiva, e così via a catena.

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

In Gambas è possibile riprodurre il comportamento e il funzionamento di una "Lista Lineare" mediante una variabile del tipo della Struttura modello, posta alla testa della Lista concatenata, della quale ci si servirà in modo particolare del suo ultimo membro di tipo Puntatore, che punta all'area di memoria, opportunamente ed preventivamente riservata, che ospiterà la Struttura/elemento successiva, appartenente alla Lista Lineare.

Al riguardo va sottolineato che nel codice Gambas il membro della Struttura, che fa da Puntatore alla successiva nuova Struttura concatenata, non deve essere dichiarato con la parola-chiave "As Struct", bensì soltanto con "As".

Mostriamo un semplice esempio per creare e gestire una "Lista Lineare":

Public Struct ELEMENTO
  i As Integer
  prossima As ELEMENTO
End Struct


Public Sub Main()

' Dichiara le seguenti variabili del tipo Struttura "LISTA":
' - "p", puntatore alla testa della "Lista";
' - "ap", puntatore ausiliario che permette la creazione degli elementi della "Lista" successivi al primo.
 Dim p, ap As ELEMENTO
 Dim n As Integer
 
' Crea una "Lista": la variabile "p" punta alla testa di tale "Lista":"
 p = New ELEMENTO
 
' Assegna un valore al primo membro (di tipo Integer) del primo elemento della "Lista":"
 p.i = 100
 
' Assegna ad "ap" il valore di "p".
' Entrambe le variabili fanno riferimento al primo elemento della "Lista":"
 ap = p
 
' Esegue un ciclo per creare i nuovi "elementi" della "Lista" concatenata successivi al primo, assegnando anche un valore al primo membro dell'elemento appena creato:"
 For n = 2 To 10
' Crea il nuovo "elemento" (ossia quello successivo) della "Lista" concatenato al precedente:"
   ap.prossima = New ELEMENTO
' Attualizza la variabile ausiliaria "ap", in modo da farla puntare al nuovo elemento (Struttura) della "Lista":"
   ap = ap.prossima
' Assegna un valore al primo membro (di tipo Integer) del nuovo elemento della "Lista":"
   ap.i = 100 * n
 Next

' Mostra quindi il risultato:"
 While Not IsNull(p)
   Print p.i
   p = p.prossima
 Wend
 
End

Mostriamo un altro analogo semplice esempio:

' 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 successivo elemento della "Lista Lineare":
  p As Pointer
End Struct


Public Sub Main()
 
 Dim st As STRUTTURA
 Dim i As Integer
 
' Crea il primo 'elemento-Struttura' della "Lista Lineare":
 st = New STRUTTURA
  
' Va a creare i restanti elementi della "Lista Lineare":
 Crea_Lista(st)
  
 Visualizza_Dati(st)
  
 Free(st.p)
  
End


Private Function Crea_Lista(nw As STRUTTURA)   ' Passaggio della Struttura per "Indirizzo"
 
 Dim sr As STRUTTURA
 Dim b As Byte
   
' Immette il dato del primo elemento-Struttura della lista:
 nw.i = 100
     
 sr = nw
  
' Alloca un'area di memoria riservata per il secondo elemento della "Lista Lineare":
 sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
  
' Crea una catena di altri 9 elementi/Strutture, in modo tale che la "Lista Lineare" sarà formata in totale da 10 elementi/Strutture":
 For b = 2 To 10
   sr = sr.p
' Immette i dati dei successivi elementi-Struttura della lista:
   sr.i = 100 * b
' Alloca un'area di memoria riservata per il nuovo-successivo elemento della "Lista Lineare":
   sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
 Next
     
End

  
Private Procedure Visualizza_Dati(tt As STRUTTURA)
  
 Print "\nValori inseriti nella 'Lista Lineare':\n"
  
 While tt.p > 0
   Print tt.i
   tt = tt.p
   Free(tt.p)
 Wend
  
End

Altra modalità:

Public Struct LISTA
  sh As Short
  i As Integer
  succ As Pointer
End Struct


Public Sub Main()
 
 Dim lst, lst2 As New LISTA
 
 CreaStruttura(lst, 4)
 
 lst2 = lst
 
 While lst.succ > 0
   Print lst.sh, lst.i
   lst = lst.succ
 Wend
 
 Dealloca(lst2)
 
End


Private Function CreaStruttura(sl As LISTA, c As Short)
 
 Dim n As Short
 
 For n = 1 To c
   sl.sh = n * c
   sl.i = n * c * 1000
   If n <= c Then
     sl.succ = Alloc(Object.SizeOf(sl), 1)
     sl = sl.succ
   Endif
   sl.succ = 0
 Next
 
End


Private Procedure Dealloca(sl As ListA)
 
 While sl.succ > 0
   Free(sl.succ)
   sl = sl.succ
 Wend
 
End

Emulare una Lista Lineare mediante i soli Puntatori

E' possibile emulare in Gambas il loro comportamento e funzionamento delle "Liste Lineari " (Linked List) anche mediante le sole variabili di tipo Puntatore.

Mostriamo un esempio commentato:

' Impostiamo la "Struttura" modello: ci servirà soltanto per definire la dimensione delle aree di memoria da allocare, ciascuna delle quali rappresenterà un elemento della "Lista Lineare" concatenata:
Public Struct STRUTTURA
  b As Byte
  s As Short
  i As Integer
' L'ultimo membro della Struttura modello nelle "Linked List" è rappresentato da un "Puntatore", il quale serve - come si sa - a creare e connettere un elemento della "Lista Lineare" a quello successivo:
  p As Pointer
End Struct


Public Sub Main()
 
 Dim p, prm As Pointer
 Dim i As Integer
 Dim st As Stream
    
' Alloca un'area di memoria riservata per il primo elemento della "Lista Lineare":
 p = Alloc(Object.SizeOf(STRUTTURA))
 prm = p
          
 For i = 1 To 4
   st = Memory p For Write
' Scrive nell'area riservata, puntata dal Puntatore, il primo valore (in questo caso è di tipo Byte):
   Write #st, 11 * i As Byte
' Nel rispetto delle norme dell'allineamento effettua uno spostamento in avanti dell'indice nell'area riservata puntata dal Puntatore:
   Seek #st, 2
' Scrive nell'area riservata, puntata dal Puntatore, il secondo valore (in questo caso è di tipo Short):
   Write #st, 1111 * i As Short
' Scrive nell'area riservata, puntata dal Puntatore, il terzo valore (in questo caso è di tipo Integer):
   Write #st, 111111 * i As Integer
   If i < 4 Then
' Alloca un'area di memoria riservata per il nuovo elemento della "Lista Lineare":
     p = Alloc(Object.SizeOf(STRUTTURA))
' Se non si è giunti all'ultimo elemento dela Lista, scrive nell'area riservata, puntata dal Puntatore, il quarto valore (in questo caso è l'indirizzo di memoria della successiva area di memoria riservata per il nuovo elemento della Lista:
     Write #st, p As Pointer
   Endif
   st.Close
 Next
   
 VisualizzaLista(prm)
   
End


Private Procedure VisualizzaLista(po As Pointer)
 
 Dim b As Byte
 Dim pu As Pointer
   
 For b = 1 To 4
   Print Byte@(po)
   Print Short@(po + 2)
   Print Int@(po + 4)
   pu = po
   po = Pointer@(po + 8)
' Libera la memoria precedentemente allocata:
   Free(pu)
 Next
  
End