En ledig lista är en datastruktur som innehåller adresserna till datorminnesplatser som är tillgängliga för användning av ett program som körs vid användning av dynamisk minnesallokering. Listan blir nödvändig när ett program måste allokera utrymme från ett område med ledigt minne som kallas heapen. Implementeringen av en ledig lista kan vara en enkel länkad lista eller kan vara en mer komplex datastruktur som t.ex. De flesta datorprogrammeringsspråk på hög nivå hanterar automatiskt den fria listan, vilket tar bort behovet av manuell hantering.
När ett program kräver utrymme för att lagra information under programkörning, måste det begära en specifik mängd minne från det underliggande operativsystemet. Platserna för minnesblock som kan utnyttjas lagras i det fria lista. För att allokeringen ska lyckas måste mängden begärt minne vara tillgängligt i ett eller flera av dessa block. När en pekare till en lämplig minnesplats returneras, det elementet i listan tas bort.
Efter att ett program har gjorts med hjälp av minnet, kan det deallokera det.Detta innebär att pekaren skickas till minnesblocket tillbaka till den fria listan, där den blir tillgänglig nästa gång en allokering sker Det är möjligt att minnesallokering misslyckas eftersom listan är tom eller för att det inte finns några tillgängliga minnesblock som är tillräckligt stora för att uppfylla programmets begäran.
Den enklaste formen av minneshantering kallas first fit-systemet. Detta system upprätthåller en enda lista med lediga minnesplatser. När en begäran om minne skickas, genomkorsas listan och det första blocket som är tillräckligt stor returneras. Om blocket är mer än dubbelt så stor som den begärda, halveras det och den oanvända halvan läggs tillbaka till listan. Denna metod byter ut enkel kodning mot risken att ha fragmenterade minnesområden som kanske aldrig kommer tillbaka till listan.
En annan form av minneshantering kallas kompisallokeringssystemet. Till skillnad från first fit-systemet håller kompisallokering flera lediga listor, var och en har öppna block av endast en viss storlek. Detta innebär att när en tilldelningsbegäran tas emot, konsulteras listan som innehåller block som är precis stora nog att fylla begäran, och en öppen plats returneras. Om inga lediga block är mindre än dubbelt så stora efterfrågade är tillgängliga, ett större block delas i två för att uppfylla kraven.
Termen ”fri lista” kan hänvisa till antingen en enda länkad lista med minnesadresser, eller så kan den hänvisa till en mycket mer komplex typ av datastruktur. Olika typer av sorteringsträd, om de hålls enkla och balanserade, kan hjälpa till att öka hastigheten för att hitta öppna minnesblock på bekostnad av att komplicera källkoden. En länkad lista kan vara långsammare än ett specialiserat sorteringsträd men skapar programmeringskod som är mycket lättare att läsa, felsöka och ändra.
Vissa programmeringsspråk och operativsystem använder sig av en speciell mekanism som kallas skräpinsamling. Detta är en process som kan hjälpa till att ta de olika posterna på en ledig lista och konsolidera de lediga utrymmena så att de hänger samman. effekten av att förhindra fragmentering och möjliggöra att större minnesblock allokeras.