Structuri liniare
Liste alocate secvential
Stiva
Coada
Liste alocate dinamic
Inserare la inceput
Inserare la final
Stergere
Alte tipuri de liste
Skip lists
Relatie de ordine totala pe multimea elementelor
Fiecare element are un singur element precedent (prev) si un singur element succesor (next).
Exemple de structuri liniare
liste
stive
cozi
Exemple de structuri neliniare
arbori
grafuri
Dupa localizarea elementelor:
• succesorul unui element e in zona imediat alaturata (liste secventiale = array)
• orice element retine si adresa succesorului (liste înlantuite).
Dupa modul de efectuare al operatiilor de intrare (inserarile) si de iesire (stergerile):
• Structuri liniare fara restrictii de intrare/iesire
• Structuri liniare cu restrictii de intrare/iesire (stive si cozi)
Traversarea - operatia care acceseaza fiecare element al structurii, o singura data, in vederea procesarii (vizitarea elementului).
Cautarea - se cauta un element cu cheie data in structura (cu sau fara succes) : consta dintr-o traversare - eventual incompleta a structurii, in care vizitarea revine la comparatia cu elementul cautat.
Inserarea - adaugarea unui nou element, cu pastrarea proprietatilor structurii.
Stergerea - extragerea unui element al structurii (eventual in vederea unei procesari), cu pastrarea proprietatilor structurii pe elementele ramase.
Operatii:
insertie pe pozitii arbitrare
stergere de la pozitii arbitrare
Date de acelasi tip stocate in locatii de memorie contigue in ordinea indicilor (Nodurile se afla in pozitii succesive de memorie)
Avantaj: acces direct la orice nod
Dezavantaj: multe deplasari la operatiile de inserare si stergere
Operatii:
push = insertie
pop = extragerea celui mai nou element inserat
Operatii:
enqueue = insertie
dequeue = extragerea celui mai vechi element inserat
Operatii:
insertie la inceput/final/pe pozitii arbitrare
stergere de la inceput/final/pozitii arbitrare
Pointerul prim retine adresa primului nod din lista, iar ultim retine adresa sfarsitului listei;
Fiecare nod conţine:
un câmp de date notat info, pe care se reprezintă un element al mulţimii;
un pointer către nodul următor, notat next.
Datele (info) pot fi:
de tip simplu (int, float etc.)
multiple tipuri simple (de exemplu punem doua campuri int pentru a implementa o lista de perechi de intregi)
alti pointeri (la vectori, la siruri de caractere sau la alte obiecte)
liste circulare (ultimul element este legat de primul)
liste dublu inlantuite (au pointer si catre elementul anterior, memoria suplimentara folosita pentru retinerea pointerului de dinainte micsoreaza timpul necesar parcurgerii/prelucrarii listei in sens invers)
liste circulare cu nod marcaj (lista vida contine un singur element alocat, a carei informatie nu se utilizeaza, adresa lui se foloseste la parcurgere -> incepem din dreapta lui si cand il intalnim din nou inseamna ca a fost parcursa lista)
liste de liste (se pot utiliza pentru matrici rare, alocam noduri doar pentru elementele nonzero ale matricii, daca exista o lista de tip coloana, aceasta memoreaza indicii liniilor si cate un pointer pentru fiecare lista-linie, ale carei elemente contin indicii de coloana, valoarea nonzero si pointer catre urmatorul element lista-linie)
Structura probabilista, sortata:
Avem un numar de benzi express cu mai putine elemente:
cand dorim sa inseram, stergem sau updatam un element: cautam pozitia lui pornind cu benzile express cele mai rare.
cand il inseram in lista are 50% sanse sa fie inserat in banda express superioara. Pentru fiecare succes, are din nou 50% sanse sa fie inserat in banda express superioara.
Insertia elementelor: