Lista wolna jest strukturą danych, która przechowuje adresy lokalizacji pamięci komputera, które są dostępne do użycia przez uruchomiony program podczas korzystania z dynamicznej alokacji pamięci.Lista staje się niezbędna, gdy program musi przydzielić miejsce z obszaru wolnej pamięci zwanego stertą. Implementacja wolnej listy może być prostą połączoną listą lub może być bardziej złożoną strukturą danych, taką jak drzewo sortowania Większość języków programowania wysokiego poziomu automatycznie obsługuje listę wolną, eliminując potrzebę ręcznego zarządzania.
Gdy program wymaga miejsca do przechowywania informacji podczas wykonywania programu, musi zażądać określonej ilości pamięci z bazowego systemu operacyjnego.Lokalizacje bloków pamięci, które można wykorzystać, są przechowywane w wolnym Aby alokacja się powiodła, ilość żądanej pamięci musi być dostępna w jednym lub kilku z tych bloków. Gdy zwracany jest wskaźnik do odpowiedniej lokalizacji w pamięci, ten element listy jest usuwany.
Gdy program zakończy korzystanie z pamięci, może ją cofnąć alokację.Polega to na przekazaniu wskaźnika do bloku pamięci z powrotem na listę wolnych miejsc, gdzie stanie się on dostępny przy następnym przydziale Możliwe, że alokacja pamięci nie powiedzie się, ponieważ lista jest pusta lub ponieważ nie ma dostępnych bloków pamięci wystarczająco dużych, aby spełnić żądanie programu.
Najprostszą formą zarządzania pamięcią jest system pierwszego dopasowania.System ten utrzymuje pojedynczą listę wolnych miejsc w pamięci.Po wysłaniu żądania pamięci następuje przechodzenie przez listę i pierwszy blok że jest wystarczająco duży, jest zwracany.Jeżeli blok jest większy niż dwukrotność żądanego rozmiaru, jest on zmniejszany o połowę, a niewykorzystana połowa jest dodawana z powrotem do listy.Ta metoda polega na zamianie prostego kodowania na ryzyko pofragmentowanych obszarów pamięci, które mogą nigdy nie zostać zwrócone na listę.
Inną formą zarządzania pamięcią jest system alokacji kumpli. W przeciwieństwie do systemu pierwszego dopasowania, alokacja kumpli utrzymuje kilka wolnych list, z których każda zawiera otwarte bloki tylko jednego określonego rozmiaru. po otrzymaniu żądania alokacji przeglądana jest lista zawierająca bloki, które są wystarczająco duże, aby wypełnić żądanie, i zwracana jest otwarta lokalizacja.Jeśli nie ma wolnych bloków, które są mniejsze niż dwukrotność rozmiaru wymagane są dostępne, większy blok jest podzielony na dwie części, aby spełnić wymagania.
Termin „wolna lista” może odnosić się do pojedynczej połączonej listy adresów pamięci lub do znacznie bardziej złożonego typu struktury danych.Różne typy drzew sortowania, jeśli są proste i zrównoważone, może pomóc zwiększyć szybkość wyszukiwania otwartych bloków pamięci kosztem komplikacji kodu źródłowego.Połączona lista może być wolniejsza niż wyspecjalizowane drzewo sortowania, ale tworzy kod programowania, który jest znacznie łatwiejszy do odczytania, debugować i modyfikować.
Niektóre języki programowania i systemy operacyjne korzystają ze specjalnego mechanizmu zwanego garbage collection.Jest to proces, który może pomóc w zebraniu różnych wpisów na wolnej liście i skonsolidowaniu wolnych przestrzeni tak, aby były ciągłe. efekt zapobiegania fragmentacji i umożliwiania alokacji większych bloków pamięci.