Una lista libre es una estructura de datos que contiene las direcciones de las ubicaciones de la memoria de la computadora que están disponibles para que las use un programa en ejecución cuando se usa la asignación de memoria dinámica. La lista se vuelve necesaria cuando un programa debe asignar espacio desde un área de memoria libre llamada montón. La implementación de una lista libre puede ser una lista enlazada simple o podría ser una estructura de datos más compleja, como un árbol de clasificación La mayoría de los lenguajes de programación de computadoras de alto nivel manejan automáticamente la lista libre, eliminando la necesidad de administración manual.
Cuando un programa requiere espacio para almacenar información durante la ejecución del programa, debe solicitar una cantidad específica de memoria del sistema operativo subyacente. Las ubicaciones de los bloques de memoria que se pueden utilizar se almacenan en el archivo libre lista. Para que la asignación sea exitosa, la cantidad de memoria solicitada debe estar disponible en uno o más de estos bloques. Cuando se devuelve un puntero a una ubicación de memoria adecuada, ese elemento de la lista se elimina.
Una vez que un programa ha terminado de usar la memoria, puede desasignarlo. Esto implica pasar el puntero al bloque de memoria de nuevo a la lista libre, donde estará disponible la próxima vez que se realice una asignación. Es posible que la asignación de memoria falle porque la lista está vacía o porque no hay bloques de memoria disponibles lo suficientemente grandes para cumplir con la solicitud del programa.
La forma más simple de administración de memoria se llama primer sistema de ajuste. Este sistema mantiene una lista única de ubicaciones de memoria libres. Cuando se envía una solicitud de memoria, se recorre la lista y se recorre el primer bloque que es lo suficientemente grande se devuelve. Si el bloque es más del doble del tamaño solicitado, entonces se divide a la mitad, y la mitad no utilizada se agrega de nuevo a la lista. Este método intercambia la codificación simple por el riesgo de tener áreas de memoria fragmentadas que quizás nunca regresen a la lista.
Una forma diferente de administración de memoria se llama sistema de asignación de amigos. A diferencia del primer sistema de ajuste, la asignación de amigos mantiene varias listas gratuitas, cada una con bloques abiertos de un solo tamaño en particular. Esto significa que cuando se recibe una solicitud de asignación, se consulta la lista que contiene los bloques que son lo suficientemente grandes para llenar la solicitud, y se devuelve una ubicación abierta. Si no hay bloques libres que tengan menos del doble del tamaño solicitados están disponibles, un bloque más grande se divide en dos para cumplir con los requisitos.
El término «lista libre» puede referirse a una sola lista enlazada de direcciones de memoria, o puede referirse a un tipo mucho más complejo de estructura de datos. Diferentes tipos de árboles de clasificación, si se mantienen simples y equilibrados, puede ayudar a aumentar la velocidad de búsqueda de bloques de memoria abiertos a expensas de complicar el código fuente. Una lista vinculada puede ser más lenta que un árbol de clasificación especializado, pero crea un código de programación que es mucho más fácil de leer. depurar y modificar.
Algunos lenguajes de programación y sistemas operativos hacen uso de un mecanismo especial llamado recolección de basura. Este es un proceso que puede ayudar a tomar las diferentes entradas en una lista libre y consolidar los espacios libres para que sean contiguos. el efecto de prevenir la fragmentación y permitir que se asignen bloques de memoria más grandes.