Media aritmetică

Prezentarea tipului de date abstracte numit lista

In domeniul calculatoarelor o lista inlantuita este una dintre structurile de date fundamentale folsita in programarea calculatoarelor.Ea consista intr-o secventa de noduri, fiecare nod contine arbitrar randuri de date si una sau doua referinte ("legaturi") care indica informatii despre nodul de dinainte sau despre urmatorul nod.Avantajul principal al listelor inlantuite fata de listele conventionale este ca ordinea termenilor inlantuiti ar putea fi diferita de ordinea in care datele acestor termenilor sunt stocate in memorie sau pe hard-disk, atfel listele inlantuite pot fi parcurse intr-o alta ordine.O lista inlantuita este un tip de date referential pentru ea insusi deaorece contine un indiciu sau legatura catre alte date de acelasi tip.Listele inlantuite permit operatii de insertie si suprimare a nodurilor la oricare punct din cadrul listei intr-un timp constant, insa nu permite un acces aleator in structura ei.Sunt mai multe tipuri de liste inlantuite: liste simplu-inlantuite, liste dublu-inlantuite, liste circular-inlantuite.Unul din cele mai mari avantaje ale listelor inlantuite este ca nodurile ar putea avea mai multe legaturi cu alte noduri, permitand acelorasi noduri sa apara simultan in diferite ordini in mai multe liste inlantuite.

Listele inlantuite pot fi implementate in mai multe limbaje de programare.Limbajele de programare cum sunt Lisp sau Scheme au structura bazata pe liste inlantuite, detinand si operatii pentru a acesa aceste liste inlantuite.Limbajele de programare procedurale (de exemplu limbajul C), sau orientate pe obiecte (de exemplu limbajul C++, sau Java) se bazeaza pe referinte care pot fi inlocuite pentru a putea crea o lista inlantuita.

Tipuri de liste inlantuite

1. Liste liniare simplu inlantuite.

Cel mai simplu tip de liste inlantuite este o lista liniara limplu-inlantuita, care are o singura legatura la fiecare nod.Aceasta legatura indica intotdeauna urmatorul nod din lista, sau o valoare nula, sau o lista libera daca aceasta reprezinta un nod final.

Lista liniar inlantuita care contine trei valori de tip intreg.

2. Liste liniare dublu-inlantuite.

Un tip de lista inlantuita mai sofisticat decat primul tip prezentat este o lista liniara dublu-inlantuita sau denumita altfel lista inlantuita pe doua cai.Fiecare nod din lista liniara dublu inlantuita are doua legaturi: una leaga nodul actual de nodul de dinaintea lui, sau leaga nodul actual cu o lista libera, sau cu o lista care are o valoare nula daca aceasta este la inceputul primului nod,iar cealalta legatura leaga nodul actual de o lista care are o valoare nula sau cu o lista libera daca aceasta reprezinta nodul final.

Exemplu de lista liniara dublu-inlantuita.

In unele limbaje de programare de nivel foarte scazut, inlantuirea prin sau-exclusiv ofera o modalitate de a implementa listele liniare dublu-inlantuite folosind un sungur cuvant binar pentru limita listelor, oricum folosirea acestei tehnici este ineficeinta.

3. Liste circular inlantuite.

Intr-o lista circular inlantuita primul nod si cu ultimeul dunt legati impreuna.Aceasta poate fi facuta pentru limitarea listelor simplu si dublu-inalntuite.Pentru a parcurge o lista circular inlantuita se incepe de la oricare nod si se urmareste lista prin aceasta directie aleasa pana cand se ajunge la nodul de unde s-a pornit parcurgerea.Prin alta procedura listele circular inlantuite pot fi vazute ca find liste care nu detin noduri de inceput sau de sfarsit.Acest tip de liste este utilizat foarte mult in manuirea datelor aduse in avans, iar in alte cazul in care s-a implementat un obiect intr-o lista si se doreste toate obiectele din lista.Legatura care indica o lista plina (intrega) se numeste legatura de capat a listei.

4. Liste circulare simplu-inlantuite.

Intr-o lista circulara simplu-inalntuita, fiecare nod are o singura legatura, similar cu listele liniare simplu-inlantuite,insa, diferenta la listele circulare simplu-inlantuite consta in legatura aflata dupa ultimul nod il leaga pe acesta de primul nod.La fel ca si in listele liniare simplu-inlatuite, nodurile noi pot fi inserate eficient numai daca acestea se afla dupa un nod care are referinte la acesta.Din acest motiv este necesar sa se mentina numai o referinta catre ultimul element dintr-o lista circulara simlu-inlantuita, caci aceasta permite o insertie rapida la nodul de inceput al listei, si de asemeni permite accesul la primul nod prin legatura dintre acesta si ultimul nod.

5. Liste circulare dublu-inlantuite.

Intr-o lista circulara dublu-inlantuita fiecare nod are doua legaturi, asemanator ca si la listele liniare simplu-inlantuite, insa diferenta este ca listele circulare dublu-inlantuite legatura dinaintea primului nod il leaga pe acesta de ultimul nod, si legatura de dinaintea ultimului nod catre il leaga pe aceste de primul nod.La fel ca si in listele liniare dublu-inaltuite, operatiile de inserie si suprimare pot fi facute la orice punct din lista cu acces la oricare nod apropiat.