Liste

 
 O lista este o colecție de elemente de informație (noduri) aranjate într-o
 anumită ordine. Lungimea unei liste este numărul de noduri din lista. Structura
 corespunzătoare de date trebuie să˜ ne permită să determinăm eficient care este
 primul/ultimul nod din structură și care este predecesorul/succesorul unui nod dat
 (dacă există). Iată cum arată cea mai simplă lista, lista liniară:
 
 

 O listă circulară este o lista în care, după ultimul nod, urmează primul nod,
 deci fiecare nod are succesor și predecesor.
 Câteva dintre operațiile care se efectuează asupra listelor sunt: inserarea
 (adăugarea) unui nod, extragerea (ștergerea) unui nod, concatenarea unor liste,
 numărarea elementelor unei liste etc.
 Implementarea unei liste se realizează în două moduri: secvențial și înănțuit.
 Implementarea secvențială se caracterizează prin plasarea nodurilor în locații
 succesive de memorie, în conformitate cu ordinea lor în listă. Avantajele acestui
 mod de implementare sunt accesul rapid la predecesorul/succesorul unui nod și
 găsirea rapidă a primului/ultimului nod. Dezavantajele sunt modalitățile relativ
 complicate de inserarea/ștergere a unui nod și faptul că, în general, nu se folosește
 întreaga memorie alocată listei.
 Implementarea înlănțuită se caracterizează prin faptul că fiecare nod conține
 două părți: informația propriu-zisă și adresa nodului succesor. Alocarea memoriei
 pentru fiecare nod se poate face n mod dinamic, în timpul rulării programului.
 Accesul la un nod necesită parcurgerea tuturor predecesorilor săi, ceea ce conduce
 la un consum mai mare de timp pentru această operatie. †In schimb, operatiile
 de inserare/ștergere sunt foarte rapide. Se consumă exact atât spațiu de memorie
 cât este necesar dar, evident, apare un consum suplimentar de memorie pentru
 inregistrarea legăturii către nodul succesor. Se pot folosi două adrese in loc de
 una, astfel incat un nod să conțină pe lângă adresa nodului succesor și adresa
 nodului predecesor. Obținem astfel o lista dublu inlantuita, care poate fi traversată
 in ambele directii.
 Listele inlantuite pot fi reprezentate prin tablouri. În acest caz, adresele
 nodurilor sunt de fapt indici ai tabloului.
 
 O alternativă este să folosim două tablouri val și next astfel: să memorăm
 informația fiecarui nod din locatia val[i], iar adresă nodului sau succesor din locația
 next[i]. Indicele locatA¸iei primului nod este memorat in variabila p. Vom conveni că,
 pentru cazul listei vide, să avem p =0¸ si next[u] = 0 unde u reprezintă ultimul nod
 din lista. Atunci, val[p] va conține informația primului nod al listei, next[p] adresă
 celui de-al doilea nod, val[next[p]] informația din al doilea nod, next[next[p]]
 adresă celui de-al treilea nod, etc. Acest mod de reprezentare este simplu dar apare problema gestionarii locațiilor libere.