Un elenco libero è una struttura dati che contiene gli indirizzi delle posizioni di memoria del computer disponibili per l’uso da parte di un programma in esecuzione quando si utilizza l’allocazione dinamica della memoria.L’elenco diventa necessario quando un programma deve allocare spazio da un’area di memoria libera chiamata heap. L’implementazione di una lista libera può essere una semplice lista concatenata o potrebbe essere una struttura dati più complessa come un sort tree La maggior parte dei linguaggi di programmazione per computer di alto livello gestisce automaticamente l’elenco libero, eliminando la necessità di una gestione manuale.
Quando un programma richiede spazio per memorizzare informazioni durante l’esecuzione del programma, deve richiedere una quantità specifica di memoria dal sistema operativo sottostante.Le posizioni dei blocchi di memoria che possono essere utilizzate sono memorizzate nel elenco. Affinché l’allocazione abbia successo, la quantità di memoria richiesta deve essere disponibile in uno o più di questi blocchi. Quando viene restituito un puntatore a una posizione di memoria appropriata, quell’elemento dell’elenco viene rimosso.
Dopo che un programma ha terminato di utilizzare la memoria, può deallocarla, ovvero riportare il puntatore al blocco di memoria nella lista libera, dove sarà disponibile la prossima volta che verrà effettuata un’allocazione. È possibile che l’allocazione della memoria non riesca perché l’elenco è vuoto o perché non sono disponibili blocchi di memoria sufficientemente grandi da soddisfare la richiesta del programma.
La forma più semplice di gestione della memoria è detta first fit system.Questo sistema mantiene un unico elenco di locazioni di memoria libere.Quando viene inviata una richiesta di memoria, l’elenco viene attraversato e il primo blocco che è abbastanza grande viene restituito. Se il blocco è più del doppio della dimensione richiesta, viene dimezzato e la metà non utilizzata viene aggiunta all’elenco. Questo metodo scambia la codifica semplice per il rischio di avere aree di memoria frammentate che potrebbero non essere mai restituite alla lista.
Una diversa forma di gestione della memoria è chiamata sistema di allocazione degli amici.A differenza del primo sistema di adattamento, l’allocazione degli amici mantiene diverse liste libere, ognuna delle quali contiene blocchi aperti di una sola dimensione particolare.Ciò significa che quando viene ricevuta una richiesta di allocazione, viene consultata la lista che contiene blocchi appena sufficienti per soddisfare la richiesta e viene restituita una posizione aperta.Se non ci sono blocchi liberi di dimensioni inferiori al doppio richieste sono disponibili, un blocco più grande viene diviso in due per soddisfare i requisiti.
Il termine “lista libera” può riferirsi sia a un singolo elenco concatenato di indirizzi di memoria, sia a un tipo di struttura dati molto più complesso.Diversi tipi di alberi di ordinamento, se mantenuti semplici ed equilibrati, può aiutare ad aumentare la velocità di trovare blocchi di memoria aperti a scapito di complicare il codice sorgente.Un elenco collegato può essere più lento di un albero di ordinamento specializzato ma crea codice di programmazione molto più facile da leggere, eseguire il debug e modificare.
Alcuni linguaggi di programmazione e sistemi operativi utilizzano uno speciale meccanismo chiamato garbage collection, un processo che può aiutare a prendere le diverse voci in un elenco libero e a consolidare gli spazi liberi in modo che siano contigui. l’effetto di prevenire la frammentazione e consentire l’allocazione di blocchi di memoria più grandi.