O listă liberă este o structură de date care conține adresele locațiilor de memorie ale computerului care sunt disponibile pentru utilizare de către un program care rulează atunci când se utilizează alocarea dinamică a memoriei. Lista devine necesară atunci când un program trebuie să aloce spațiu dintr-o zonă de memorie liberă numită heap.Implementarea unei liste libere poate fi o simplă listă legată sau poate fi o structură de date mai complexă, cum ar fi o Arborele de sortare Majoritatea limbajelor de programare de nivel înalt se ocupă automat de lista gratuită, eliminând nevoia de gestionare manuală.
Când un program necesită spațiu pentru a stoca informații în timpul execuției programului, trebuie să solicite o anumită cantitate de memorie de la sistemul de operare de bază.Locațiile blocurilor de memorie care pot fi utilizate sunt stocate în spațiul liber. listă. Pentru ca alocarea să aibă succes, cantitatea de memorie solicitată trebuie să fie disponibilă în unul sau mai multe dintre aceste blocuri. Când este returnat un pointer către o locație de memorie adecvată, acel element al listei este eliminat.
După ce un program s-a terminat folosind memoria, îl poate de-aloca. Aceasta implică trecerea indicatorului către blocul de memorie înapoi în lista liberă, unde va deveni disponibil data viitoare când este o alocare. Este posibil ca alocarea memoriei să eșueze deoarece lista este goală sau pentru că nu există blocuri de memorie disponibile suficient de mari pentru a îndeplini cererea programului.
Cea mai simplă formă de gestionare a memoriei se numește sistemul first fit.Acest sistem menține o singură listă de locații de memorie libere.La trimiterea unei cereri de memorie, lista este parcursă și primul bloc care este suficient de mare este returnat. Dacă blocul este mai mult de două ori dimensiunea cerută, atunci este redus la jumătate, iar jumătatea nefolosită este adăugată înapoi la listă. Această metodă comercializează codificarea simplă pentru riscul de a avea zone de memorie fragmentate care s-ar putea să nu fie returnate niciodată pe listă.
O formă diferită de gestionare a memoriei se numește sistem de alocare a prietenilor. Spre deosebire de sistemul de primă adaptare, alocarea de prieteni păstrează mai multe liste libere, fiecare deținând blocuri deschise de o singură dimensiune anume. Aceasta înseamnă că atunci când se primește o cerere de alocare, se consultă lista care conține blocuri care sunt suficient de mari pentru a completa cererea și se returnează o locație deschisă. Dacă nu există blocuri libere care au mai puțin de două ori dimensiunea sunt disponibile, un bloc mai mare este împărțit în două pentru a îndeplini cerințele.
Termenul „listă liberă” se poate referi fie la o singură listă legată de adrese de memorie, fie se poate referi la un tip mult mai complex de structură de date. Diferite tipuri de arbori de sortare, dacă sunt menținute simple și echilibrate, poate ajuta la creșterea vitezei de găsire a blocurilor de memorie deschise în detrimentul complicării codului sursă. O listă legată poate fi mai lentă decât un arbore de sortare specializat, dar creează cod de programare care este mult mai ușor de citit, depanați și modificați.
Unele limbaje de programare și sisteme de operare folosesc un mecanism special numit colectare de gunoi. Acesta este un proces care poate ajuta la preluarea diferitelor intrări dintr-o listă liberă și la consolidarea spațiilor libere astfel încât acestea să fie învecinate. efectul de a preveni fragmentarea și de a permite alocarea unor blocuri mai mari de memorie.