Un alt dezavantaj al listelor inlantuite este utilizarea unui
spatiu de memorie prea mare pentru a memora indicii, caz in care spatiul
de memorie devine ineficient utilizat atunci cand se listeaza un numar
mic de elemente cum sunt de exemplu caracterele sau valorile booleene.In
astfel de cazuri elementele listele inlantuite pot avea un comportament
greoi, rezultand risipa de memorie pentru a aloca memorie separata pentru
fiecare element nou inserat.Acest dezavantaj poate fi anulat prin paginarea
memoriei.
Exista mai multe variante de liste inalntuite care pot ameliora
problemele descrise mai sus.De exemplu listele inlantuite tabelate
stocheaza pot stoca mai multe elemente in fiecare nod al listei, crescand
astfel performanta accesului in cadrul datelor aflate in memoria CACHE,
si nu se mai face prea mare risipa de memorie pentru a memora fiecare
element al listei intr-un spatiu separat.
5.2. Listele dublu-inlantuite comparate
cu listele simplu-inlantuite. >>>
Listele dublu inlantuite necesita mai mult spatiu de memorie
pentru un nod (mai putin cu unu daca se foloseste listarea prin sau-exclusiv),
iar operatiile elementare devenind mult mai extinse, insa sunt mai usor
de manevrat deoarece listele dublu-inlantuite permit un acces segvential
asupra elementelor in ambele directii: de la nodul de inceput pana la
nodul din capat si invers.In particular, o lista poate insera sau suprima
un nod intr-un numar constant de operatii numai daca se ofera adresa exacta
a nodului asupra caruia trebuie sa se execute operatile prezentate.(In
comparatie cu listele simplu-inlantuite, care necesita furnizarea adresei
nodului din fata nodului care trebuie inserat sau suprimat).Unii algoritmi
aplicati in cadrul listelor dublu-inlantuite trebuie sa aiba acces in ambele
directii.Adica, sunt si algoritmi care nu permit utilizarea metodelor care
ofera lucrul numai cu sfarsitul listelor, caci astfel listele nu se pot
utiliza ca structuri de date persistente.
5.3. Listele circular-inalntuite comparate cu
listele liniar-inlantuite. >>>
Listele circular-inlantuite sunt mult mai utilizabile in descrierea
structurilor de date de natura circulara, si au avantajul unui structuri
regulate care permite traversarea listei incepand de la oricare punct.Acestea
permit accesul catre prima sau ultima inregistrare printr-un singur
indiciu (adresa ultimului element).Principalul dezavantaj al listelor
circular-inlantuite consta in complexitatea iteratiilor.
6. Operatii asupra listelor inlantuite. >>>
Cand se lucreaza cu liste inlantuite trebuie sa se aiba in vedere
evitarea utilizarii valorilor nestabilite in operatiile anterioare.
Operatiile efectuate asupra listelor utilizeaza algoritmi care
insereaza sau suprima noduri intr-un mod oarecum subtil.In aceasta sectiune
se vor prezenta cateva pseudocoduri care vor aplica metode de insertie
sau suprimare "pe loc" asupra listelor simplu, dublu si circular inlantuite.Astfel
ca se va aborda utilizarea unui nod nul pentru a fi un indiciu
sau "santinela" pentru a reprezenta sfarsitul unei liste, si care se
poate implementa in mai multe moduri.
6.1. Operatii in cadrul listelor liniare simplu-inlantuite. >>>
Se doreste ca nodul structurii de date utilizate sa aiba doua campuri.Astfel
se va implica o variabila numita primulNod care intotdeauna va
indica primul nod al listei, care va avea si valoarea nula
daca lista este libera.
record Nod
{ date // Acestea sunt datele stocate in nod
next // O referinta catre nodul urmator; are valoare nula pentru ultimul nod. }
record Lista
{Nod primulNod // indica primul nod al listei; are valoare nula in listele libere. }
Traversarea unei liste simplu-inlantuite este usoara, parcurgerea
se incepe de la primul nod al listei si se va pargurge fiecare nod urmator
pana cand se va ajunge la ultimul nod:
nod:= lista.primulNod
while nodul nu are valoare nula
{ (aplica o metoda pentru nod.data)
nod:= nod.urm }
Urmatorul cod insereaza un nod nou dupa un nod deja existent in lista
simplu-inlantuita.Diagrama arata procedura acestei insertii.Inserarea
unui nod nou inaintea un nod deja existent nu poate fi realizata; in
schimb, aceasta se poate localiza atat timp cat se cunoaste drumul catre
nodul anterior:
function insereazaDupa(Nod nod, Nod nodulNou) { // insereaza nodulNou dupa acest nod
nodulNou.urm:= nod.urm
nod.urm := nodulNou }
Inserarea unui nod la inceputul listei necesita o functie separata,
adica se va imbunatatii primulNod
function insereazaInceput(Lista list, Nod nodulNou) { // insereaza nodul inaintea primului nod actual
nodulNou.urm := lista.primulNod
lista.primulNod := nodulNou }
Asemanator se poate folosii functii pentru suprimarea nodului care
se afla situat dupa un nod dat, totodata si pentru suprimarea unui
nod aflat la inceputul listei.Diagrama urmatoare demonstreaza procedura.Pentru
a gasii si suprima un nod particular trebuie ca prima data sa se faca
cunoscut drumul catre nodul aflat inaintea acestui nod:
function suprimaDupa(Node node)
{ // suprima nodul aflat dupa primul nod
nodTemporar := nod.urm
nod.urm := nod.urm.urm
suprima nodTemporar }
function suprimaInceput(List lista)
{ // suprima primul nod
nodTemporar := lista.primulNod
//segventa urmatoare va indica ultimul nod sters
lista.primulNod := lista.primulNod.urm
suprima nodTemporar
}
Se poate observa ca in functia suprimaInceput()
se abordeaza lista.primulNod ca fiind de valoare nula
atunci cand se suprima ultimul nod din lista. Astfel nu se
va mai putea itera inapoi, caci nu este posibila o comportare eficienta
a operatiilor "insereazaNod" sau "suprimaNod".Inscrierea unei liste inlantuite
in cadrul alteia poate fi o metoda ineficienta numai daca o referinta
catre capatul (coada) acestei liste este vazuta ca o parte a listei in
care a fost inscrisa, deoarece va trebui sa se traverseze in intregime
prima lista pentru ai gasii capatul si numai dupa aceeia sa se inscrie
in cadrul ei a doua lista.Acum, daca doua liste liniar inlantuite au
acceasi lungime n, lista inscrisa are un timp asimptotic
de complexitate determinata de functia O(n).In familia limbajelor
de programare Lisp o lista se poate inscrie in cadru alteia prin procedura
append
In majoritatea cazurilor speciale a listelor inlantuite operatiile
pot fi realizate mai usor daca se introduce un element artificial la
inceptul listei.Acesta va asigura in aceste cazuri ca nu se vor aborda
metode speciale pentru inceputurile listelor si si restituirea limitelor
InsereazaInceput si suprimaInceput
nu va mai fi necesara.In acest caz, prima data care va fi cea mai utilizata
in cadrul listei se va putea gasii la lista.primulNod.urm.
6.2. Operatii pentru listele liniare dublu-inlantuite. >>>
Cand se foloseste liste dublu-inlantuite, algoritmii in care
acestea sunt abordate dispun de mai multe indicii, deoarece este necesara
detinerea catorva informatii despre listele cu care se lucreaza, avand astfel
si avantajul ca aceste indicii pot fi parcursi inapoi pentru ca se poata
observa care sunt elementele precedente ale listei.Aceasta implica noi operatii
si elimina functiile pentru cazurile speciale.In exemplul de mai jos se doreste
sa se aduca un un rand anterior in cadrul unor noduri, si care va
indica elementul anterior al nodurilor, si un alt rand numit ultimulNod
amplasat in structura litei in care se afla nodurile, si care va indica intotdeauna
ultimul nod al listei.Limitele lista.primulnod si lista.ultimulnod
vor fi nule pentru o lista libera (fara elemente).
record Nod {date // Datele care au fost stocate in nod
urm // o referinta catre nodul urmator; ea va fi nula pentru ultimul nod in lista
ant //O referinta catre nodul anterior, ea va avea valoare nula pentru primul nod }
record Lista {Nod primulNod // indica primul nod al listei; are valoare nula pentru liste libere
Nod ultimulNod // indica ultimul nod al listei; are valoare nula pentru liste libere }
Iterarea realizata in cadrul unei liste liniare dublu-inlantuite poate
fi facuta in orcare directie.Asadar directile se pot schimba in functie de
preferinte.Iata doua implementari care abordeaza parcurgerea in cela doua
directii prezentate in cod Pascal:
Inainte
nod := lista.primulNod
while nod ≠ null ( executa operatii pentru nod.date)
nod := nod.urm
Inapoi
nod := lista.ultimulNod
while nod ≠ null ( executa operatii pentru nod.date)
nod := nod.ant
Aceste functii simetrice vor insera un nod oarecare dupa sau inaintea unui
nod dat, asa cum este si in diagrama de mai jos:
function insertieDupa(Lista lista, Nod nod,Nod nodulNou) nodulNou.ant := nod
nodulNou.urm := nod.urm
if nod.urm = nulllista.ultimulNod := nodulNou elsenod.urm := nodulNou
function inseretieInainte(Lista lista, Nod nod, Nod nodulNou) nodulNou.ant := nod.ant
nodulNou.urm := nod
if nod.ant is nulllista.primulNod := nodulNou elsenod.ant := nodulNou
Acum va trebui sa se abordeze o functie pentru a insera un nod la inceputul
unei posibile liste libere:
function insertieInainte(Lista lista, Nod nodulNou) if lista.primulNod = nulllista.primulNod := nodulNou
lista.ultimulNod := nodulNou
nodulNou.ant := null
nodulNou.urm := null elseinsereazaInainte(lista, lista.primulNod, nodulNou)
O functie asimetrica insereaza un nod la sfarsitul unei posibile liste libere:
function insertieDupa(Lista lista, Nod nodulNou) if lista.ultimulNod = nullinsereazaInceput(lista, nodulNou) elseinsereazaDupa(lista, lista.ultimulNod, nodulNou)
Suprimarea unui nod se executa usor:
function suprima(Lista lista, Nod nod) if nod.ant = nulllista.primulNod := nod.urm elseif nod.urm = nulllista.ultimulNod := nod.ant elsesuprima nod
O consecinta subtila pentru aceasta procedura este suprimarea ultimului element
al listei incadrata in limitele primulNod si ultimulNod care au valori
nule, si astfel se executa suprimarea corecta a ultimului
nod dintr-un singur element al listei.Se observa ca nu este novoie sa se
desparta metodele "suprimaInainte" sau "suprimaDupa", deoarece intr-o lista
liniara dublu-inlantuita se poate folosii numai "suprima(nodul.anterior)"
sau "suprima(nodul.urmator)" numai daca acestea sunt valide.
6.3. Operatii in listele circular inlantuite. >>>
Oricare din listele circular inlantuite pot sa fie simplu-inlantuite,
sau dublu inlantuite.Intr-o lista circular inlantuita toate nodurile
sunt inlantuite ca intr-un cerc, fara sa aiba noduri nule la
capatul listei.Pentru listele circular inlantuite care dispun de o parte
de inceput si una de capat, atunci una dintre aceste parti va stoca obligatoriu
o referinta catre ultimul nod al listei.Urmatorul nod care se afla
dupa ultimul nod al acestor tip de liste inlantuite este de fapt primul
nod.Elementele pot fi inserate la capatul listei si suprimate din varful
acesteia prin metode specifice care se executa intr-un timp constant.
Limitele listelor circular inlantuite au avantajul ca aceste
liste pot sa fie parcurse in intregime incepand de la oricare nod dat.Aceasta
nu utilizeaza metoda stocarii primuluinod si ultimuluiNod,
astfel daca lista ar puta fi libera atunci va fi necesar o reprezentare
speciala pentru aceasta lista libera, cum ar fi de exemplu utilizarea
variabilei ultimulNod care va indica unele noduri ale listei
sau se va folosii valoarea null daca lista este libera.Aceasta
reprezentare simplifica semnificativ inserarea cat si suprimarea nodurilor
cu o lista ocupata (non-libera), numai listele libere reprezinta un caz
special.
Listele circulare au fost utilizate ca structura de date principala
de catre Anders Hejlsberg, creatorul limbajului LINQ (Language Integrated
Query).
6.4. Operatii pentru listele circulare
dublu-inlantuite. >>>
Presupunand ca nodOarecare este un nod oarecare in cadrul
unei liste ocupate, aceasta implementare itereaza prin inceputul listei
presupunand ca ea incepe de la un nodOarecare (si orice nod al
listei poate fi reprezentat prin nodOarecare):
Inainte
nod := nodOarecare
do (executa operatii pentru nod.valoare)
nod := nod.urm while nod ≠ nodOarecare
Inapoi
nod := nodOarecare
nod := nodOarecare
do (executa operatii pentru nod.valoare)
nod := nod.ant while nod ≠ nodOarecare
Se obesrva ca testul se executa la sfarsitul buclei.Aceasta este foarte
important pentru cazul in care listele contin numai un singur nodOarecare.Aceasta
simpla functie insereaza un nod intr-o lista circulara dublu-inlantuita
dupa un element dat:
function insertieDupa(Nod nod, Nod nodulNou) nodulNou.urm := nod.urm
nodulNou.ant := nod
nod.urm.ant := nodulNou
nod.urm := nodulNou
Prin introducerea metodei "insereazaIceput" se simplifica "insereazaDupa(nod.ant,
nodulNou)".Inserarea unui nod intr-o lista posibil libera necesita o functie
speciala:
function insertieSfarsit(Lista lista, Nod nod) if lista.ultimulNod = nullnod.ant := nod
nod.urm := nod elseinsertieDupa(lista.ultimulNod, nod) lista.ultimulNod := nod
Pentru a insera la inceputul listei se simplifica metoda "insertieDupa(lista.ultimulNod,
nod)".Pe urma, suprimarea unui nod trebuie tratata cu cazul in care listele
sunt libere:
function suprima(Lista lista, Nod nod) if nod.urm = nodelsenod.urm.ant := nod.ant
nod.ant.urm := nod.urm
if nod = lista.ultimulNodlista.ultimulNod := nod.ant; suprima nod
Ca si in cazul listelor liniare dublu-inlantuite, metodele "suprimaDupa"
si "suprimaInainte" pot fi implementate cu "suprima(lista, nod.ant)" si
"suprima(lista, nod.urm)".
7. Liste inlantuite ce utilizeaza tablouri
de noduri. >>>
Limbajele de programare care nu au suport de utilizare a oricarui
tip de referinta, pot crea legaturi prin inlocuirea indicilor cu indici
de tablou.Aceasta implementare se poate realiza prin aborderea un tablou
de inregistrari, unde fiecare inregistrare dispunde de campuri de valori
intregi care indica pozitia urmatorului, si posibil nodul anterior din
tablou, insa nu toate nodurile din tablou trebuiesc folosite.
Aici este prezentat un exemplu.Se considera ca urmatoarele inregistrari
ale unei liste inlantuite folosesc tablouri de indicii:
record Intrare
{ integer urm; // indicele urmatoarei intrari in tablou
integer ant; // urmatoarea inrare in tablou (daca lista este dublu-inlantuita)
string nume;
real echilibru; }
Prin crearea unui tablou al acestor structuri, si o variabila de tip
intreg care indica pozitia primului element, o lista inlantuita poate
fi construita astfel:
integer inceputulListei;
Intrare Inregistrari[1000];
Legaturile dintre elementele listei sunt formate prin plasarea in
tablou a indiciului urmatoarei, sau anterioarei coloane, in carul campurilor
specifice "Urmatorul" sau "Anteriorul" fara sa se detina o element dat.De
exemplu:
Indice |
Urmator |
Anterior |
Numele |
Suma cont |
0 |
1 |
4 |
Augustin, Aruncatu |
123.45 |
1 |
-1 |
0 |
Lopata, Lolica |
234.56 |
2 (inceputulListei) |
4 |
-1 |
Adams, Adam |
0.00 |
3 |
|
|
Fugaritu, Florin |
999.99 |
4 |
0 |
2 |
Anescu, Anita |
876.54 |
5 |
|
|
|
|
6 |
|
|
|
|
7 |
|
|
|
|
In exemplul de mai sus, InceputulListei va fi pozitionata
la 2, aceasta fiind locatia primei intrari in lista.Se observa ca intrarile
3 si 5 pana la 7 nu sunt reprezinta parti din lista.Aceste coloane sunt
valabile pentru a se realiza noi adaugiri in lista.Prin crearea variabilei
de tip intreg ListaLibera poate fi realizata
o lista libera pentru a tine legaturile dintre coloanele care sunt folosite.Daca
taote intrarile sunt utilizate, dimensiunea tabloului va trebui sa creasca
sau unele elemente vor trebui sterse inainte ca noile intrari sa fie
stocate in lista.
Urmatorul cod travesrseaza lista afisand numele si contul echilibrului:
i := inceputulListei;
while i >= 0 { '// se executa mai multe treceri prin lista print i, Records[i].nume, Records[i].cont // afiseaza intrarea
i = Records[i].urm; }
Cand se produce o schimbare, advantajele acestei implementari includ:
* Listele inlantuite sunt realocabile, in sensul ca se pot plasa oriunde
dorim in memorie, aceaste liste putand firapid si direct serializate
pentru a putea fi stocate pe hard-disk sau transferate prin retea.
* Cazurile speciale reprezinta listele de mici dimensiuni, tablourile
indexate putand ocupa un spatiu de memorie de dimensiuni semnificativ
de mici dacat un indicator plin.
* Localizarea referintelor pot fi realizate prin stocarea alaturata
a tuturor nodurilor in memorie urmand ca acestea sa fie rearanjate periodic,
insa aceasta poate fi realizata si printr-o stocare (inmagazinare) generala.
* Alocarile naive ale memoriei dinamice poate produce o depasire
a spatiului de memorie disponibil pentru fiecare nod alocat, find posibile
si cazurile in care nu se dispune de memorie suplimentara pentru nodul
care si-a depasit spatiul initial alocat.
* Dimensionarea unei intrari din lista printr-un tablou pre-alocat
este realizata mai rapid daca se foloseste pentru fiecare nod un spatiu
din memoria dinamica, astfel alocarea memoriei dinamice necesita o cautare
pentru a afla un bloc de memorie potrivita pentru a fi posibila stocarea
intrarii.
Aceasta implementare are un dezavantaj principal: ea creaza si
detine un spatiu privat pentru toate nodurile, ceea ce implica urmatoarele
situatii:
* Contribuie la cresterea complexitati pentru implemetari.
* Redimensionarea unui tablou cand aceasta este plin cu elemente
ar putea devenii dificial sau imposibila, pe cand gasirea unui spatiu
pentru noua lista inlantuita intr-o memorie interna de mari dimensiuni
poate fi realizata usor.
* Inserarea elementelor intr-un tablou dinamic se poate ca ocazional
(cand tabloul este plin) sa nu se execute liniar in interiorul acestuia
intr-un timp constant.
* Utilizand memoria interna s-ar putea ca nodurile afalte la
sfarsitul listei sa necesite mai mult spatiu pentru date daca lista
de care apartin are dimensiuni foarte mici, sau daca cele mai multe
noduri nu contin date.
Din aceste motive limbajele de programare care nu dispun de
un suport de alocare a momoriei dinamice utilizeaza in mod special listele
inlantuite.Aceste dezavantaje sunt atenuate daca dimensiunea maxima a
listei cu care se lucreaza este cunoscuta la crearea tabloului.
8. Limbaje care utilizeaza listele inlantuite. >>>
Unele limbaje de programare cum sunt de exemplu Lisp si Scheme
sunt construite in baza unor liste simplu-inlantuite.In unele limbaje
de programare functionale listele sunt construite din noduri, fiecare
fiind numit ca fiind o componenta sau celula componenta.Aceasta
componenta are doua campuri: car acre este o referinta a datelor
continute de nod, si campul cdr care reprezinta o referinta catre
nodul urmator.Oricum celulele compnente poti fi utilizate pentru a construi
alte structuri de date, aceste fiind de fapt si scopul lor.
In alte limbaje de programare. listele inlantuite sunt construite
folosindu-se referintele alaturi de inregistrari.Aici este un exemplu
de program in limbajul C:
#include /* pentru printf */
#include /* pentru malloc */
typedef struct ns {
int data;
struct ns *urmator;
} nod;
nod *creaza_lista(nod **p, int i) {
nod *n = malloc(sizeof(nod)); /* in mod normal nu se poate returna o valoare pentru "malloc" */
n->urmator = *p;
*p = n;
n->data = i;
return n;
}
void sterge_lista(nod **p) { /* se sterge capatul superior al listei */
if (*p != NULL) {
nod *n = *p;
*p = (*p)->urmator;
free(n);
}
}
nod **cauta_lista(nod **n, int i) {
while (*n != NULL) {
if ((*n)->data == i) {
return n;
}
n = &(*n)->urmator;
}
return NULL;
}
void afiseaza_lista(nod *n) { //list_print
if (n == NULL) {
printf("Lista este libera\n");
}
while (n != NULL) {
printf("Afiseaza %p %p %d\n", n, n->urmator, n->data);
n = n->urmator;
}
}
int main(void) {
nod *n = NULL;
creaza_lista(&n, 0); /* listeaza: 0 */
creaza_lista(&n, 1); /* listeaza: 1 0 */
creaza_lista(&n, 2); /* listeaza: 2 1 0 */
creaza_lista(&n, 3); /* listeaza: 3 2 1 0 */
creaza_lista(&n, 4); /* listeaza: 4 3 2 1 0 */
afiseaza_lista(n);
sterge_lista(&n); /* se sterge prima lista (4) */
sterge_lista(&n->urmator); /* se sterge noua lista, devenita acum a doua (2) */
sterge_lista(cauta_lista(&n, 1)); /* stergerea coloanelor care contin valoarea 1 (prima) */
sterge_lista(&n->urmator); /* se sterg nodurile incepand de al al doilea pana la ultimul (0) */
sterge_lista(&n); /* se sterg ultimele noduri (3) */
afiseaza_lista(n);
return 0;
}
9. Stocarea interna si externa a listelor inlantuite. >>>
Cand se construieste o lista inlantuita, una este implementata
conform alegerii pentru a stoca date direct in nodurile listei fiind
astfel denumita stocare interna, sau numai pentru a
stoca referinte ale datelor - stocare externa.Stocare interna
are avantajul de a realiza un acces la datele listei mult mai eficient,
necesitand un mic spatiu de memorie pentru fiecare si detinand astfel
cea mai buna localizare a referintelor, simplificand si administrarea
memoriei cu care lista operareaza (datele listei sunt alocate si distriuite
in acelasi timp pentru ca reprezinta de fapt nodurile acestei liste).
Stocarea externa, in alta ordine de idei, are avantajul de a fi
mult mai simpla, in sensul ca datele care au aceeasi structura si acelasi
cod masina pot fi utilizate in cadrul unei liste inlantuite fara sa se
tina cont de dimensiunea datelor.Aceasta deoarece este usor sa se incadreze
aceleasi date in mai multe liste inlantuite.Astfel stocand intern acelasi
tip de date acestea pot fi introduse in mai multe liste care vor avea o
referinta numita referinta catre lista uramatoare inclusa
in structura de date a nodurilor, ea fiind necesara pentru a crea rutine
separate pentru a insera sau suprima celule de la baza oricarui camp de
date.
In general, daca un grup de structuri de date trebuiesc incluse
in mai multe liste inlantuite, stocare exerna este cea mai buna implementare.Daca
un grup de structuri de date trebuiesc sa fie incluse intr-o singura
lista inlantuita, atunci stocarea interna reprezinta cu siguranta cea
mai buna implementare, insa doar daca un grup de liste inlantuite dispune
de o implementare care sa faca valabila stocarea externa, aceastea pot
fi stocate si extern.
De asemenea, daca un grup de date de tip diferit pot fi stocate
in aceeasi structura de date, atunci ele pot fi stocate si intr-o singura
lista inlantuita, astfel o procedura de stocare interna poate fi valabila.
O alta implementare care poate fi utilizata in cadrul unor limbaje
de programare care ofera posibilitatea lucrului cu structuri de date
diferite, insa numai daca toate aceste date dispun de campuri care sa
includa referinte catre nodul urmator (sau anterior daca
este o lista dublu-inlantuita) in aceasi locatie.Dupa definirea separata
pentru fiecare tip de date, poate fi definita o structura generica care
va contine un numar minimum despre datele oferite catre alte structuri
de date si care sa fie continute la inceputul (in varful) acestora.Apoi
structurile generice pot fi create, deoarece se utilizeaza o structura
minima pentru a putea realiza operatii specifice listelor inlantuite, insa
separarea rutinelor se produce atunci cand se utilizeaza acelasi tip de
date.Aceasta implementare este adesea folosita in distrubuirea (comunicarea)
rutinelor de definire a datelor, mai ales in aplicatiile in care sunt mai
multe tipuri de date, insa toate aceste distribuiri pornesc de la acelasi
grup de campuri de date, cateodata se poate include si un camp de stocare
a tipurilor de distribuiri.Campul tipului de distribuire este folosit atunci
cand se doreste o abordare corecta a rutinei care proceseaza un tip specific
de comunicare.
10. Exemplu de stocari interne si externe. >>>
Se presupune ca se doreste a se crea o lista inlantuita pentru
un numar de familii si care sa includa si numarul de membrii ale acestora.Folosind
o stocare interna a datelor, structura aplicatiei va arata in felul
urmator:
record membru { //indice pentru membrul familiei membru urmator
string nume
integer varsta }
record familie { //familia propriu-zisa familie urmatoare
string prenume
string adresa
membru membrii // inceptul listei membrilor acestei familii }
Pentru a vedea lista completa a familiilor si a numarului de membrii
a lor printr-o stocare interna, se poate scrie:
oFamilie := Familii // inceputul listei familiilor
while oFamilie ≠ null // se parcurge lista famililor si se afiseaza informatiile despre aceastea
{ unMembru := oFamilie.membrii // se construieste inceptul listei membrilor familiei.
while unMembru ≠ null
{ // se parcurge lista membrilor si se afiseaza informatii despre fiecare membru.
unMembru := unMembru.urmator }
oFamilie := oFamilie.urmatoare }
Daca se doreste sa se foloseasca o stocare externa atunci se poate
crea urmatoare structura:
record nod
{ nod urmatorul
referinta date // referinta generica pentru datele din nod }
record membru // structura membrilor familiei
{ string prenumele
integer varsta }
record familie // structura familiei
{string numele
string adresa
node membrii // inceputul listei membrilor din aceasta familie }
Pentru a vizualiza lista completa a famililor cat si a numarului de membrii
folosind o stocare de date externa, atunci se poate scrie:
nodulFamiliilor := Familii // inceputul listei famililor
while nodulFamiliilor ≠ null // se parcurge lista familiilor
{ // se vor extrage familiile din nod si se vor afisa informatii despre acestea
oFamilie = (familie)nodulFamiliilor.date
nodulMembrilor := oFamilie.membrii // se formeaza lista membrilor familiilor
while nodulMembrilor ≠ null // se parcurge lista membrilor familiilor
{// se vor extrage memberii din nod si se vor afisa informatii despre acestia
unMembru := (membru)nodulMembrilor.date
nodulMembrilor := nodulMembrilor.urmator }
nodulFamiliilor := nodulFamiliilor.urmator }
In exemplul de mai sus de remarcat este faptul ca atunci cand se utilizeaza
o stocare externa, va fi necesar un pas in plus pentru a extrage inregistrarea
dintr-un nod si apoi sa se defineasca aceasta in tipul propriu de date.Aceasta
este necesar deoarece limita listei de familie din exemplul nostru si
lista membrilor din familie sunt stocate in doua liste inlantuite folosindu-se
aceeasi structura de date (nod).
Se poate insa ca un membru sa apartina numai unei familii, astfel
procedeul de stocare interna devine favorit.Daca sunt colectii de date
referitoare la mai multe generatii asa incat o persoana sa apara ca fiind
un fiu intr-o familie, iar parintele in alta familie, atunci va fi necesar
o procedura de stocare externa.
11. Rapititatea procesului de cautare
in liste. >>>
Gasirea unui element specificat intr-o lista inlantuita, chiar
daca aceasta este sortata, in mod normal necesita un timp de O(n)
daca se prefera o cautare liniara.Acesta este unul din principalele
dezavantaje ale listelor inlantuite in comparatie cu alte structuri
de date.Intr-o lista nesortata, o simpla euristica pentru a reduce din
timpul mediu de cautare este bazata pe principiul "pune uristica mai
in fata", astfel se va realiza o simpla mutare a unui element catre
inceputul listei daca acesta este gasit.O alta implementare des utilizata
este "indexarea" unei liste inlantuite folosindu-se o structura de date
externa mult mai eficienta.De exemplu o lista poate construi un arbore
rosu-negru sau un tablou de dispersie a caror elemente vor fi referinte
catre nodurile listei inlantuite.Mai multe liste inlnatuite indexate pot
fi grupate (construite) intr-o singura lista.Dezavantajul este ca aceste
liste inlantuite indexate ar putea necesita inbunatatiri de fiecare data
cand un nod este inserat sau suprimat. | 
