O listă liniară simplu înlănțuită conține elemente (noduri) a căror valori constau din două părți: informația utilă și informația de legătură. Informația utilă reprezintă informația propriu-zisă memorată în elementul liste (numere, șiruri de caractere, etc.), iar informația de legătură precizează adresa următorului element al listei. În C/C++ putem folosi următorul tip de date pentru a memora elementele unei liste liniare simplu înlănțuite alocate dinamic:
struct nod{
int info;
nod * urm;
};
Câmpul info al tipului nod reprezintă informația utilă – în acest caz un număr întreg, iar câmpul urm este de tip pointer la nod și reprezintă informația de legătură.
În program vom folosi o variabilă de tip pointer (de exemplu prim) pentru a memora adresa primului element al listei și fiecare element al listei, începând cu primul, va memora în câmpul urm adresa elementului următor. Excepție face ultimul element al listei care va memora în câmpul urm valoarea NULL.
Observații:
prim va avea valoarea NULL, cu semnificația că lista este vidă. Dacă la un moment dat lista redevine vidă (de exemplu se șterg toate elementele ei) variabila prim va avea valoarea NULL.new și gestionate prin intermediul pointerilor. Variabila prim este de tip pointer, dar este (în cele ce urmează) statică.4 octeți. Astfel, fiecare element al unei liste de tipul de mai sus va ocupa în memorie 4+4=8 octeți.O secvență C++ care conține declarațiile corespunzătoare poate fi:
struct nod{
int info;
nod * urm;
};
nod * prim = NULL;
În continuare vom prezenta secvențe/funcții C++ pentru principalele operații:
Funcțiile care urmează vor avea ca parametru adresa primului element al listei și eventual alți parametri. În funcție de situație, parametrul care reprezintă adresa primului element ale listei va fi transmis prin valoare sau prin referință.
Numeroase operații cu liste solicită crearea unui nou element/nod. Pentru aceasta trebuie să ținem cont de următoarele:
new, care are ca rezultat adresa variabilei nou create. Aceasta va fi memorată într-un pointer de tip nod *. Să-l numim p: nod * p = new nod;info și urm. Accesul la câmpuri se va face prin intermediul pointerilor, cu ajutorul operatorului ->, astfel: p->info și p->urm. Accesul la câmpuri se poate face și după dereferențierea pointer-ului: (* p).info și (* p).urm.p->urm va memora adresa următorului element, sau NULL dacă nu există următorul element!p este pointer la nod; este de tip nod *;*p este variabila de tip nod – este nod din listăp->info este informația utilă din nodul listei, de tip intp->urm este pointer. Memorează adresa elementului următor!
Secvența C++:
nod * p = new nod; p->info = ..... ; // cin >> p->info; p->urm = NULL;
Ne imaginăm lista în felul următor; săgețile simbolizează legăturile dintre nodurile listei. Vârful săgeții reprezintă elementul următor. Ultimul element nu are săgeată. Valoarea corespunzătoare din câmpul urm este NULL.

În exemplul de mai sus au loc următoarele relații:
prim este adresa elementului cu valoarea 12;prim->info==12prim->urm->info==46prim->urm este adresa elemenului cu valoarea 46prim->urm->urm==pp->info==59p->urm->urm==tt->info==17t->urm->info==25t->urm->urm->info==18t->urm->urm->urm==NULLt->urm->urm->urm->info nu există. Rezultatul acestei expresii este impredictibil!Un antet posibil pentru funcția care adaugă un element la finalul liste este:
void AdaugaFinal(nod * & prim , int val);
Parametru prim este transmis prin referință pentru a trata corespunzător situația când lista este vidă. În acesta caz, valoare de intrare a lui prim este NULL, iar valoarea de ieșire este adresa primului element al listei – element nou creat.
Practic, vom trata două situații:
prim este NULL, creăm un nod nou, care va fi primul și totodată ultimul element al listei, memorăm în el valoarea dorită și prim devine adresa acestui nod;void AdaugaFinal(nod * & prim , int x)
{
// creăm nod nou
nod * q = new nod;
q -> info = x;
q -> urm = NULL;
// adăugă noul nod la listă
if(prim == NULL)
{ // lista este vidă
prim = q;
}
else
{ // lista nu este vidă
nod * t = prim;
while(t -> urm != NULL)
t = t -> urm;
t -> urm = q;
}
}
Un antet posibil pentru funcția care adaugă element la începutul liste este:
void AdaugaInceput(nod * & prim , int val);
Parametru prim este transmis prin referință deoarece la fiecare apel al funcției primul element se modifică; se creează un element nou care devine prim element al listei. Astfel, adresa primului element se modifică.
Procedăm astfel:
prim memorează adresa primului elementnod * t = new nod;t->info = ....t->urm = prim;prim = t;Obs: Nu este necesară tratarea diferențiată a situațiilor când lista este vidă (prim==NULL), respectiv când lista conține elemente (prim memorează adresa primului element). În ambele situații atribuirea prim = t; are efectul dorit!
void AdaugaInceput(nod * & prim , int x)
{
// creăm nod nou
nod * t = new nod;
t -> info = x;
// legam nodul de lista
t -> urm = prim;
// valoarea lui prim se modifică, pentru a ieși din funcție cu valoarea corectă
prim = t;
}
Parcurgerea listei reprezintă vizitarea succesivă a elementelor pentru a realiza diverse operații cu valorile lor. Un antet posibil pentru o funcție care parcurge lista este:
void Parcurgere(nod * prim);
Parcurgerea se realizează secvențial, element cu element:
nod * p în care vom memora, pe rând, adresele elementelor din listă;p = prim;p->info)p = p->urm;void Parcurgere(nod * prim)
{
nod * p = prim;
while(p != NULL)
{
//prelucrăm nodul curent
// trecem la următorul nod
p = p->urm;
}
}
Ștergerea unui element al listei constă în două etape: ștergerea propriu-zisă a variabilei dinamice în care este stoca nodul de șters și refacerea legăturilor, astfel încât lista să fie consistentă. Tehnic, modul de ștergere diferă după cum nodul de șters este primul din listă sau nu.
Dacă ștergem primul element al listei vom proceda astfel:
nod * t = prim;prim devine primul nod al listei: prim = prim->urm;t: delete t;Dac ștergem un element oarecare al listei, trebuie să cunoaștem într-un pointer oarecare, să spunem p, adresa elementului din fața nodului de șters. Acest lucru este necesar pentru refacerea corectă a legăturilor dintre elementele listei:
p, adică vom șterge p->urm;nod * t = p->urm;p: p->urm = t->urm;t: delete t;Și inserarea se face diferit, în funcție de poziția noului nod în listă; inserarea unui nod nou înaintea primului nod al listei (adresa sa este memorată în pointer-ul prim) se face astfel:
nod * t = new nod;t->info = ...;t->urm = prim;prim = t;Dacă nodul nou creat nu va fi primul din listă, îl vom insera după un nod cu adresa cunoscută, memorată în pointer-ul p:
nod * t = new nod;t->info = ...;p: t->urm = p->urm;p: p->urm = t;Așa cum știm deja, fiecărui program C++ care rulează pe calculator i se alocă trei zone distincte în memoria RAM, în care se află datele pe care le prelucrează acel program:
0 și sunt vizibile pe tot parcursul programului, în toate funcțiile definite după declararea acestoraUtilizarea variabilelor dinamice reprezintă o tehnică numită alocare dinamică. Ea se implementează prin intermediul pointer-ilor și are avantajul că folosește doar atâta memorie cât este necesară.