Liste

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


   

                O listă circulară este o lista în care, după ultimul nod, urmează primul nod, deci fiecare nod are succesor si 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 înlă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 înserarea/ș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ă operație. În schimb, operațiile  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 înregistrarea legăturii către nodul succesor. Se pot folosi două adrese în loc de  una, astfel încât un nod să conțină pe lângă adresă nodului succesor și adresă nodului predecesor. Obtinem astfel o lista dublu inlantuita, care poate fi traversată 

 în ambele direcții. 

 Listele înlănțuite 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 fiecarui nod în locația val[i], iar adresa nodului său succesor in locația next[i]. Indicele locatiei primului nod este memorat în variabila p. Vom conveni că, pentru cazul listei vide, să avem p =0 și next[u] = 0 unde u reprezintă ultimul nod din lista. Atunci, val[p] va conține informația primului nod al listei, next[p] adresa 

 celui de-al doilea nod, val[next[p]] informația din al doilea nod, next[next[p]]  adresa celui de-al treilea nod, etc. Acest mod de reprezentare este simplu dar apare problema gestionării locațiilor libere. O soluție este să reprezentăm locațiile  libere tot sub formă unei liste înlănțuite. Atunci, ștergerea unui nod din lista 

 inițială implică inserarea sa în listă cu locații libere, iar inserarea unui nod în lista  inițială implică ștergerea sa din listă cu locații libere. Pentru implementarea listei de locații libere, putem folosi aceleași tablouri dar avem nevoie de o altă variabilă, freehead, care să conțină indicele primei locații libere din val și next. Folosim 

 acelea și convenții: dacă freehead =0 înseamnă că nu mai avem locații libere, iar 

 next[ul] = 0 unde ul reprezintă ultima locație liberă.