Liste alocate dinamic
Listele alocate dinamic reprezintă modalități de organizare a datelor în memorie. Sunt utile ]n anumite situații când dorim să stocăm informații în mod secvențial
Memoria alocată fiecărui element al listei se face dinamic, la executie (atunci când este nevoie de acel element) iar legătura între elementele listei se face prin intermediul adreselor la care acestea se află.
- fiecare element (nod) stochează informațiile sale specifice dar și adresa elementului ce îl urmează în listă;
- (2) mai este necesară o variabilă externă nodurilor alocate dinamic, în care se stochează adresa primului nod;
- (3) avem nevoie de un marcaj special în câmpul de adresă al ultimului nod pentru a putea detecta finalul listei;
În acest fel, putem traversa lista element cu element, pornind de la primul nod - a cătui adresă o găsim în variabila descrisă la (2). Este avantajos să inserăm, să ștergem elemente (dacă suntem deja poziționați în locul unde facem operația), sau să concatenăm liste, întrucât aceste operații presupun doar atribuiri de pointeri (nefiind necesară deplasarea element cu elemt ca în cazul tablourilor de memorie).
- liste liniare circulare (în câmpul de adresă al "ultimului" nod punem adresa "primului" nod);
- liste liniare dublu înlănțuite (fiecare nod memorează, pe lângă informațiile efective, două adrese, una către nodul ce îl urmează și alta către cel care îl precede);
- arbori alocați dinamic (în fiecare nod avem adrese ale tuturor fiilor săi, iar în frunze, în locul acestor adrese, marcaje de final). Este interesant de remarcat că fiecare lanț de la rădăcină în jos este de fapt o listă simplu înlănțuită;
- grafuri alocate prin liste de vecini;