Structuri de Date - Curs 3

Intr-un vector

elementele ocupa zone de memorie adiacente

se aloca, static sau dinamic, spatiu pentru numarul maxim de elemente

este posibila adresarea indexata

inserarea / eliminarea unui element in / din interiorul colectiei implica deplasarea succesorilor la dreapta / stanga

Intr-o lista (simplu sau dublu inlantuita)

elementele ocupa zone de memorie neadiacente

fiecare element trebuie insotit de cel putin o informatie de legatura - adresa succesorului, la care se adauga, in cazul listelor dublu inlantuite, adresa predecesorului. Elementul si informatia de legatura se grupeaza intr-o structura numita celula.

in cazul listelor alocarea de spatiu se realizeaza la nivel de celula, numai atunci cand este necesar

pentru localizarea unui element trebuie parcursa lista predecesorilor

inserarea / eliminarea oriunde in lista nu necesita deplasarea altor elemente, ci alocarea, respectiv eliberarea de spatiu si actualizarea unor informatii de legatura.

Vector:

deplaseaza dreapta succesorii

copiaza noul element

Lista:

aloca spatiu pentru o celula si copiaza noul element (1)

actualizeaza legaturi (2,3)

deplaseaza stanga succesoriiLista:

memoreaza adresa celulei eliminate (1)

actualizeaza legatura (2)

elibereaza spatiul ocupat de celula eliminata (3)

Curs 3