Introduzione

Le liste linkate intrusive sono una implementazione particolare di una lista linkata. Le sue proprietà particolari lo rendono molto utile per alcuni casi d’uso specifici, ad esempio come struttura dati di supporto per un allocatore di memoria.

Vediamo quindi brevemente cosa differenzia una linked list intrusiva e non, partendo da quest’ultima che è sicuramente più comune.

Liste linkate non intrusive

Le liste linkate non intrusive sono esattamente le liste linkate “comuni”. Per chiarificare ulteriormente assumiamo che i dati che stiamo trattando siano oggetti di tipo “automobile”. Questa classe definisce le proprietà “colore”, “modello” e “cilindrata”.

Per implementare questo tipo di lista linkata, scriveremo probabilmente una classe / struct “nodo”, che al suo interno contiene:

  • Un puntatore al nodo successivo
  • Un puntatore al nodo precedente
  • Un puntatore a un oggetto “automobile”

La lista linkata poi, è semplicemente un insieme di funzioni per manipolare questi “nodi” e un puntatore ad un oggetto nodo / testa della lista.

Questa stessa implementazione, si può rendere generica rispetto al dato puntato nel Nodo – quindi riutilizzabile. Pensiamo alle liste linkate in Java ad esempio.

Le liste linkate intrusive

Le liste linkate intrusive sono una implementazione specifica di lista linkata in cui il puntatore all’elemento successivo e precedente fanno parte del dato stesso.

In questo caso, non avremo infatti una classe di tipo Nodo, ma i puntatore all’elemento precedente e successivo fanno parte del datum stesso.

Per utilizzare l’automobile definita sopra con una lista linkata intrusiva, avremo quindi bisogno di aggiungere i puntatore all’elemento precedente e successivo all’interno dell’automobile stessa, in modo che le sue proprietà ora diventino:

  • “colore”
  • “modello”
  • “cilindrata”
  • puntatore all’automobile successiva
  • puntatore all’automobile precedente

In generale, questo tipo di strutture dati che modificano la definizione del dato archiviato vengono chiamate “intrusive”.

A cosa servono

Come spiegato poco fa’, un utilizzo comune è per tenere traccia degli indirizzi disponibili all’interno di un allocatore di memoria. La particolarità di una struttura dati di questo tipo è che di fatto riduce di metà il numero di allocazioni necessarie per il salvataggio di un nuovo nodo.

Questo è evidente se pensiamo che non esiste più una classe “Nodo”.

Un altro motivo è perchè riducono le probabilità di trashing a livello di cache.

Se siete appassionati di Doom, le intusive lists sono state anche utilizzate in questo gioco: https://gpfault.net/posts/intrusive-lists-doom3.txt.html

E’ da notare che hanno poi dovuto scambiare questa struttura dati con una basata su array per motivi di performance.

Il kernel GNU/Linux fa ampio utilizzo delle liste linkate questa struttura dati. Una spiegazione (un po’ datata) si può trovare qui: https://isis.poly.edu/kulesh/stuff/src/klist/

Riferimenti

  • Questo è sicuramente il tutorial più completo, ed offre anche un’implementazione. Avrete bisogno però conoscere C per capire esattamente cosa succede: https://www.data-structures-in-practice.com/intrusive-linked-lists/
  • Implementazione delle intrusive linked list nel kernel Linux: https://elixir.bootlin.com/linux/v5.2/source/include/linux/list.h