Versione delle 15:31, 5 nov 2020

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"). ^{[Nota 1]}

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.

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 i 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 i = 2 To 10
' Crea il nuovo "elemento" della "Lista" concatenato al precedente:"
   ap.prossima = New ELEMENTO
   ap = ap.prossima
   ap.i = 100 * i
 Next
 
 
' Mostra quindi il risultato:"
 While Not IsNull(p)
   Print p.i
   p = p.prossima
 Wend
 
End

Note

[1] Vedi anche le seguenti pagine:

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