Liste Collegate Singolarmente (Forward-Linked Lists)

Sebbene le reference siano formidabili, alcuni algoritmi e strutture dati richiedono l’uso dei puntatori a causa della loro abilità di venire riassegnati e della loro capacità di indicare un nodo vuoto tramite nullptr.

La struttura dati canonica basata sui puntatori è la lista collegata singolarmente (forward-linked list).

Una forward-linked list è una semplice struttura costituita da una serie di elementi (o nodi). Ogni elemento contiene i propri dati e un puntatore al prossimo elemento. L’ultimo elemento della lista possiede un puntatore impostato su nullptr per segnalare la fine della catena.

A differenza degli array contigui, inserire nuovi elementi in mezzo a una lista collegata è incredibilmente efficiente (basta riassegnare due puntatori) e gli elementi in memoria non devono per forza risiedere vicino l’uno all’altro.

Implementazione di Base

Come visto nel codice, l’inserimento nella lista si basa puramente sull’alterazione dei valori dei puntatori next. Gli oggetti veri e propri non vengono minimamente mossi nella memoria fisica!