Una lista libre (o lista libre ) es una estructura de datos utilizada en un esquema de asignación dinámica de memoria . Funciona conectando regiones de memoria no asignadas entre sí en una lista enlazada , utilizando la primera palabra de cada región no asignada como un puntero a la siguiente. Es más adecuada para la asignación desde un grupo de memoria , donde todos los objetos tienen el mismo tamaño.
Las listas libres hacen que las operaciones de asignación y desasignación sean muy sencillas. Para liberar una región, basta con vincularla a la lista libre. Para asignar una región, basta con eliminar una única región del final de la lista libre y utilizarla. Si las regiones son de tamaño variable, es posible que haya que buscar una región de tamaño suficientemente grande, lo que puede resultar costoso.
Las listas libres tienen la desventaja, heredada de las listas enlazadas, de una localidad de referencia deficiente y, por lo tanto, una utilización deficiente de la memoria caché de datos , y no consolidan automáticamente las regiones adyacentes para cumplir con las solicitudes de asignación de regiones grandes, a diferencia del sistema de asignación de amigos . Sin embargo, siguen siendo útiles en una variedad de aplicaciones simples donde un asignador de memoria completo es innecesario o requiere demasiada sobrecarga.
El entorno de ejecución de OCaml utiliza listas libres para satisfacer las solicitudes de asignación, [1] al igual que RosAlloc en el entorno de ejecución de Android. [2]