O structura de date presupune un mod de organizare a datelor (Œn tablouri, structuri, etc), si definirea operatiilor acceptate. Deci, o structura de date reprezinta o colectie organizata de date si un set de operatii definite. q8t11tl
Si notiunea de tip de date presupune:
|--- reprezentare
|--- operatii acceptate

De exemplu, pentru tipul int:
|--- reprezentare: pe doi octeti: cod complementar
|---operatii acceptate: +, -, *, /, &, |, etc.

Daca pentru un tip de date nu intereseaza reprezentarea, ci doar operatiile acceptate,Œnseamna ca tipul de date este abstract.

Structuri de date
Tablouri
Tabloul este o colectie de date Œn care fiecare element poate fi identificat pe baza unui index, colectia asigurƒnd timp de acces constant pentru fiecare element. Prin reprezentarea tabloului se intelege plasarea elementelor Œn locatii succesive de memorie:

Locatiile de memorie pot fi numerotate, putƒnd accesa direct orice element.
Timpul de accesare al elementului numar, de exemplu, fiind acelasi cu timpul de accesare al elementului n.

Liste
O lista este o multime de obiecte, numite atomi, pentru care este definita o ordine:

Operatiile principale care se pot se face Œn cadrul listei: inserare: introducerea unui nou element Œntr-o anumita pozitie; stergere: scoaterea unui element dintr-o anumita pozitie; consultare: accesul asupra fiecarui element din lista; parcurgere.
Tipuri speciale de liste

Stive
O stiva este o lista Œn care operatiile de inserare, stergere si consultare se efectueaza asupra unui capat al listei. Stiva se poate asemana cu un recipient
Œn care se pun si se pot scoate diferite obiecte. Operatia care pune obiectele
Œn stiva se numeste push, iar cea care scoate obiecte din stiva se numeste pop.
Capatul accesibil pentru stiva se numeste vƒrful stivei:
Asadar: push insereaza un element Œn vƒrful stivei; pop sterge un element din vƒrful stivei; top consulta (citeste) elementul din vƒrful stivei; top(S) citeste vƒrful stivei.

Cozi
O coada este o lista Œn care inserarea se face la un capat (la sfƒrsit), iar stergerea se face de la celalalt capat al cozii (de la Œnceput). Partea din fata a cozii (a primului element) se numeste front, iar partea din spate
(a ultimului element) se numeste end.
Operatia de inserare Œn coada add (put)
Operatia de stergere din coada del (get)

Implementari de liste
O lista poate fi realizata ca: lista ordonata sau lista Œnlantuita
Lista ordonata tine cont de o ordine a pozitiilor elementelor listei, nu de continutul elementelor.
Inserarea Œntr-o lista de forma:

se face cu deplasare de o pozitie la stƒnga din punctul Œn care dorim sa inseram (pentru a face acest loc noului element).
Deplasarea se face Œnspre zona de memorie libera (cea hasurata) presupunem ca dorim sa inseram pe a Œn pozitia i):

Presupunƒnd acum hasurat corpul de elemente din lista si nehasurata zona de memorie libera, inserarea s-ar putea figura astfel:

Stergerea: deplasarea cu o pozitie la stƒnga din acel punct.

Liste Œnlantuite
Intr-o lista Œnlantuita, ordinea din memorie nu mai corespunde cu ordinea din lista. Fiecare element al listei Œnlantuite va avea urmatoarea structura:
(a(i) , succesor(a(i))) unde a(i) este atomul listei Œnlantuite, iar informatia succesor(a(i)) ne permite sa identificam un nou element de lista Œnlantuita. Ordinea din memorie a elementelor listei nu conteaza. Informatia care indica primul element al listei se numeste "capul" listei. Informatiei succesor(a(i)) i se potriveste notiunea de pointer (identificator), pointer-ul fiind o variabila care pastreaza o adresa din memorie. El indica pozitia elementului urmator. Cƒnd informatiile de Œnlantuire sunt pointeri, putem utiliza urmatoarea reprezentare:

Capul de lista este un pointer separat care duce la primul element din lista, iar 0 este pointer-ul nul (NULL) cu valoare zero. La implementarea listei
Œnlantuite concentrarea se face la fluxul instructiunilor, nu la declaratiile de variabile.

In programe vom utiliza urmatoarele notatii: x adresa unui element din lista, deci un pointer; data(x) atomul memorat Œn elementul de lista indicat de x; link(x) informatia de legatura memorata Œn elementul de lista indicat de x, adica adresa elementului urmator; y = get_sp() y (de acelasi tip cu x) primeste adresa unei zone de memorie
Œn care se poate memora un element din lista (get space sau alocare de memorie cƒnd este vorba de pointer); ret_sp(x) elibereza memoria ocupata de elementul de lista indicat de x (din momentul respectiv acolo se poate memora altceva).

Un element de lista va fi o astfel de structura:

struct Element A
Atom data;
Element* link;
S;
Se va scrie: tipul lui x ---------------- Element* x data(x) ---------------- x data link(x) ---------------- x link y = get_sp() ---------------- y = new Element ret_sp() ---------------- delete x

Deoarece lucram cu conceptul de lista vom face declaratia : typedef Element* Lista;
Un pointer la un element de lista considerat aproximeaza lista ce porneste cu elementul indicat.

Operatii primitive pentru liste Œnlantuite

1.Inserarea
Inserarea se face: Œn fata, sau
Œn interior (la mijloc ori la sfƒrsit) a) Inserarea Œn fata

1 - Prima atribuire: link(x) = l
2 - A doua atribuire: l = x

Observatie: daca lista este vida, l are valoarea 0 (capatul listei) iar atribuirile de mai sus ramƒn valabile:

b) Inserarea la mijloc

Analog pentru inserarea la sfƒrsit.
1 - Prima atribuire: link(x) = link(y)
2 - A doua atribuire: link(y) = x

2.a)Stergerea (stergerea din fata):

1 - Prima atribuire: p = l
2 - A doua atribuire: l = link(l)
3 - ret_sp(p)
Sau, stergerea din fata s-ar mai putea reprezenta astfel:
Situatia initiala:

Situatia finala:

(1) p = cap;
(2) cap = cap link; delete p ; // Elibereaza zona de memorie

Elementul care a fost izolat de lista trebuie sa fie procesat Œn continuare, cel putin pentru a fi eliberata zona de memorie pe care o ocupa, de aceea adresa lui trebuie salvata (sa zicem Œn variabila pointer p).
2.b)Stergerea de la mijloc sau de la sfƒrsit

Varibila q va indica elementul din fata celui care va fi sters.

Situatia initiala:

Situatia finala:

(1) p = q->link;
(2) q-> link = p->link; // sau q->link = q->link->link; delete p;

Observatii:
Atunci cƒnd q indica penultimul element dintr-o lista, atribuirile de mai sus functioneaza corect si sterg ultimul element din lista.
Nu se poate face stergerea elementului indicat de q fara parcurgerea listei de la capat.