Tematică științifică · 4.3

Structuri de date implementate dinamic

Liste simplu și dublu înlănțuite, liste circulare, stive, cozi, arbori cu rădăcină, arbori binari și arbori binari de căutare alocați dinamic, cu operațiile de creare, inserare, ștergere, parcurgere și căutare, în C++.

O structură de date implementată dinamic este formată din noduri alocate separat, în timpul execuției. Nodurile nu ocupă locații consecutive, ci se află oriunde s-a găsit loc liber în heap. Pentru ca ele să poată fi regăsite, fiecare nod păstrează, pe lângă informația propriu-zisă, adresele nodurilor cu care este legat.

După relația dintre elemente, structurile de date se împart în:

Tipul pointer, operatorii new și delete și înregistrarea autoreferită, pe care se bazează listele, stivele, cozile și arborii alocați dinamic, sunt prezentate în subcapitolul Operațiile de alocare și eliberare.

Lista liniară

Numărul de noduri este lungimea listei, iar lista fără niciun nod este lista vidă.

În implementarea dinamică, un nod conține două feluri de informație:

informația propriu-zisă, pentru care a fost creată lista;
informația de legătură, adică adresa nodului următor.

Legătura ultimului nod are valoarea NULL. Accesul la listă pornește de la adresa primului nod, păstrată într-un pointer numit de obicei prim; pentru adăugarea rapidă la sfârșit se păstrează și adresa ultimului nod, în pointerul ultim.

Fiecare nod are o căsuță pentru informația propriu-zisă și una pentru adresa nodului următor. Săgețile reprezintă adresele păstrate în câmpurile de legătură.

Listele se clasifică după două criterii:

Criteriul	Tipul listei	Ce o caracterizează
locul în care se fac inserările și ștergerile	listă generală	inserarea și ștergerea sunt permise oriunde în listă
	stivă	inserarea și ștergerea se fac la aceeași extremitate
	coadă	inserarea se face la o extremitate, iar ștergerea la cealaltă
legăturile păstrate în nod	listă simplu înlănțuită	fiecare nod păstrează adresa succesorului
	listă dublu înlănțuită	fiecare nod păstrează adresa succesorului și adresa predecesorului
	listă circulară	ultimul nod este legat de primul

Operațiile specifice listelor sunt:

inițializarea — se creează lista vidă;
crearea — se adaugă noduri, unul câte unul, începând cu lista vidă;
inserarea unui nod la început, la sfârșit sau în interiorul listei;
ștergerea unui nod de la început, de la sfârșit sau din interiorul listei;
parcurgerea — se vizitează nodurile, în ordinea legăturilor, pentru prelucrarea informației;
căutarea unui nod care îndeplinește o condiție;
eliberarea memoriei ocupate de toate nodurile listei.

Lista simplu înlănțuită

Nodul conține un număr întreg și adresa nodului următor. Lista vidă are prim și ultim egali cu NULL, iar testul prim == NULL arată dacă lista este vidă.

struct nod {
    int info;    // informatia propriu-zisa
    nod *urm;    // adresa nodului urmator
};

nod *prim = NULL, *ultim = NULL;   // lista vida

Inserarea la începutul listei

Pașii.

Se alocă memorie pentru nodul nou și se scrie informația în el.
Legătura nodului nou primește adresa primului nod.
Dacă lista era vidă, nodul nou devine și ultimul nod.
Nodul nou devine primul nod.

Ordinea pașilor 2 și 4 nu se poate inversa: după prim = nou, adresa vechiului prim nod nu mai este păstrată nicăieri, iar lista se pierde.

void adaugaInceput(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = prim;
    if (prim == NULL)          // lista era vida
        ultim = nou;
    prim = nou;
}

Inserarea la sfârșitul listei

Pașii.

Se alocă memorie pentru nodul nou și se scrie informația în el.
Legătura nodului nou primește valoarea NULL, fiindcă el va fi ultimul.
Dacă lista este vidă, nodul nou devine primul nod; altfel, legătura ultimului nod primește adresa nodului nou.
Nodul nou devine ultimul nod.

Crearea listei se face pornind de la lista vidă și inserând la sfârșit fiecare valoare, în ordinea citirii.

void adaugaSfarsit(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = NULL;
    if (prim == NULL)          // lista era vida
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
}

Inserarea după un nod dat

Nodul q după care se inserează este cunoscut, deci nu este nevoie de parcurgere.

Pașii.

Se alocă memorie pentru nodul nou și se scrie informația în el.
Legătura nodului nou primește adresa succesorului lui q.
Legătura lui q primește adresa nodului nou.
Dacă q era ultimul nod, nodul nou devine ultimul nod.

void adaugaDupa(nod *q, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = q->urm;
    q->urm = nou;
    if (q == ultim)
        ultim = nou;
}

Inserarea înaintea unui nod dat

Nodul nou trebuie legat de predecesorul lui q, dar într-o listă simplu înlănțuită un nod nu păstrează adresa predecesorului. Predecesorul se află prin parcurgerea listei de la început.

Pașii.

Se alocă memorie pentru nodul nou și se scrie informația în el.
Legătura nodului nou primește adresa lui q.
Dacă q este primul nod, nodul nou devine primul nod.
Altfel, se parcurge lista până la nodul p pentru care p->urm este q, iar legătura lui p primește adresa nodului nou.

void adaugaInainte(nod *&prim, nod *q, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = q;
    if (q == prim)
        prim = nou;
    else {
        nod *p = prim;
        while (p->urm != q)    // predecesorul lui q
            p = p->urm;
        p->urm = nou;
    }
}

Inserarea se poate face și fără parcurgere. Nodul nou se inserează după q, apoi informația lui q se mută în nodul nou, iar în q se scrie informația de inserat. Ordinea informațiilor în listă este aceeași ca la inserarea înaintea lui q.

Metoda schimbă însă informația păstrată la adresa q. Dacă programul reținuse adresa lui q în alt pointer, acel pointer indică de acum informația nouă.

void adaugaInainteCopiere(nod *q, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = q->info;       // nodul nou preia informatia lui q
    nou->urm = q->urm;
    q->info = x;               // in q se scrie informatia de inserat
    q->urm = nou;
    if (q == ultim)
        ultim = nou;
}

Inserarea într-o listă ordonată

Într-o listă ordonată crescător, nodul nou se inserează astfel încât lista să rămână ordonată. Dacă lista este vidă sau x este mai mic decât informația din primul nod, inserarea se face la început. Altfel, se caută nodul p după care trebuie inserat: p pornește de la primul nod, iar parcurgerea continuă cât timp există un nod următor și informația lui este mai mică decât x. Nodul nou ajunge astfel înaintea primului nod de după p care are informația mai mare sau egală cu x.

void inserareOrdonata(nod *&prim, int x) {
    nod *nou = new nod;
    nou->info = x;
    if (prim == NULL || x < prim->info) {
        nou->urm = prim;
        prim = nou;
    } else {
        nod *p = prim;
        while (p->urm != NULL && p->urm->info < x)
            p = p->urm;
        nou->urm = p->urm;
        p->urm = nou;
    }
}

Parcurgerea listei

Nodurile se vizitează de la primul la ultimul, cu un pointer p care pornește de la prim și trece la fiecare pas la adresa din p->urm. Parcurgerea se încheie când p devine NULL.

Pentru parcurgere se folosește un pointer separat. Dacă s-ar avansa chiar cu prim, adresa primului nod s-ar pierde.

void afisare(nod *prim) {
    for (nod *p = prim; p != NULL; p = p->urm)
        cout << p->info << " ";
    cout << endl;
}

Căutarea unui nod

Nodurile se verifică pe rând, începând cu primul, până la găsirea nodului căutat sau până la sfârșitul listei. Funcția întoarce adresa nodului găsit sau NULL.

Se poate căuta:

nodul care conține o valoare dată;
nodul aflat într-o poziție dată, numărând pozițiile de la 1.

Ordinea condițiilor din while contează: p != NULL se verifică primul, astfel încât p->info nu se evaluează niciodată pentru un pointer NULL.

nod *cauta(nod *prim, int x) {
    nod *p = prim;
    while (p != NULL && p->info != x)
        p = p->urm;
    return p;
}

nod *nodulDePePozitia(nod *prim, int k) {
    nod *p = prim;
    for (int i = 1; p != NULL && i < k; i++)
        p = p->urm;
    return p;
}

Ștergerea primului nod

Operația cere o listă nevidă.

Pașii.

Adresa primului nod se salvează în pointerul q.
Succesorul primului nod devine primul nod.
Se eliberează memoria de la adresa q.
Dacă lista a rămas vidă, ultim primește valoarea NULL.

void eliminaPrimul(nod *&prim, nod *&ultim) {
    nod *q = prim;
    prim = prim->urm;
    delete q;
    if (prim == NULL)          // lista a ramas vida
        ultim = NULL;
}

Ștergerea ultimului nod

Pașii.

Dacă lista are un singur nod, acesta se eliberează, iar lista devine vidă.
Altfel, se parcurge lista până la predecesorul ultimului nod, adică nodul p pentru care p->urm este ultim.
Legătura lui p primește valoarea NULL.
Se eliberează ultimul nod, iar p devine ultimul nod.

void eliminaUltimul(nod *&prim, nod *&ultim) {
    if (prim == ultim) {       // un singur nod
        delete prim;
        prim = ultim = NULL;
        return;
    }
    nod *p = prim;
    while (p->urm != ultim)    // predecesorul ultimului nod
        p = p->urm;
    p->urm = NULL;
    delete ultim;
    ultim = p;
}

Ștergerea unui nod din interiorul listei

Un nod se scoate din listă legând predecesorul lui de succesorul lui. De aceea ștergerea se exprimă prin predecesor: se elimină succesorul nodului p.

Pașii.

Adresa succesorului lui p se salvează în pointerul q.
Legătura lui p primește adresa succesorului lui q.
Dacă q era ultimul nod, p devine ultimul nod.
Se eliberează memoria de la adresa q.

Pentru a șterge un nod cu o valoare dată, se caută predecesorul lui, ca la inserarea înaintea unui nod, iar dacă nodul căutat este chiar primul, se folosește ștergerea primului nod.

void eliminaDupa(nod *p, nod *&ultim) {
    nod *q = p->urm;           // nodul care se sterge
    p->urm = q->urm;
    if (q == ultim)
        ultim = p;
    delete q;
}

Eliberarea memoriei ocupate de listă

Nodurile se eliberează pe rând, de la primul la ultimul. Înaintea eliberării unui nod se trece la succesorul lui, fiindcă după delete câmpul urm al nodului eliberat nu mai poate fi citit.

void eliberare(nod *&prim, nod *&ultim) {
    while (prim != NULL) {
        nod *q = prim;
        prim = prim->urm;
        delete q;
    }
    ultim = NULL;
}

Programul complet

Problemă. Se citesc un număr natural nenul n și apoi n numere întregi. Se construiește o listă simplu înlănțuită, alocată dinamic, cu numerele în ordinea citirii. Se șterg din listă toate nodurile care conțin numere negative și se afișează numerele rămase sau mesajul lista vida.

Exemplu: pentru n = 7 și numerele -4 2 -5 8 -1 3 -6 se afișează 2 8 3.

Descrierea soluției. Lista se creează prin inserări la sfârșit. Nodurile negative de la începutul listei se șterg cu ștergerea primului nod, până când primul nod conține un număr nenegativ sau lista devine vidă. Celelalte noduri negative au un predecesor, deci se șterg prin el: pointerul p pornește de la primul nod și, dacă succesorul lui este negativ, succesorul se șterge, iar p nu avansează, fiindcă noul succesor trebuie verificat și el; altfel, p avansează.

#include <iostream>
using namespace std;

struct nod {
    int info;
    nod *urm;
};

void adaugaSfarsit(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = NULL;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
}

void eliminaPrimul(nod *&prim, nod *&ultim) {
    nod *q = prim;
    prim = prim->urm;
    delete q;
    if (prim == NULL)
        ultim = NULL;
}

void eliminaDupa(nod *p, nod *&ultim) {
    nod *q = p->urm;
    p->urm = q->urm;
    if (q == ultim)
        ultim = p;
    delete q;
}

void eliberare(nod *&prim, nod *&ultim) {
    while (prim != NULL) {
        nod *q = prim;
        prim = prim->urm;
        delete q;
    }
    ultim = NULL;
}

int main() {
    nod *prim = NULL, *ultim = NULL;
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        adaugaSfarsit(prim, ultim, x);
    }

    // nodurile negative de la inceputul listei
    while (prim != NULL && prim->info < 0)
        eliminaPrimul(prim, ultim);

    // celelalte noduri negative se sterg prin predecesorul lor
    if (prim != NULL) {
        nod *p = prim;
        while (p->urm != NULL)
            if (p->urm->info < 0)
                eliminaDupa(p, ultim);
            else
                p = p->urm;
    }

    if (prim == NULL)
        cout << "lista vida";
    else
        for (nod *p = prim; p != NULL; p = p->urm)
            cout << p->info << " ";

    eliberare(prim, ultim);
    return 0;
}

Lista circulară

Lista nu are un nod terminal, deci din orice nod se poate ajunge la oricare altul urmând legăturile.

Legătura ultimului nod păstrează adresa primului nod, iar lista nu mai are o legătură egală cu NULL.

Crearea și inserarea după ultimul nod. Se inserează ca într-o listă simplu înlănțuită, apoi legătura ultimului nod primește adresa primului nod. Dacă lista are un singur nod, acesta este legat de el însuși.

void adaugaCirculara(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
    ultim->urm = prim;         // ultimul nod se leaga de primul
}

Parcurgerea. Nu există o legătură egală cu NULL la care să se oprească parcurgerea. Se pornește de la primul nod și se oprește la revenirea în primul nod. Fiindcă primul nod trebuie prelucrat înaintea testului, parcurgerea se scrie cu o structură repetitivă cu test final.

void afisareCirculara(nod *prim) {
    if (prim == NULL)
        return;
    nod *p = prim;
    do {
        cout << p->info << " ";
        p = p->urm;
    } while (p != prim);
    cout << endl;
}

Ștergerea nodului care urmează după nodul p. Legătura lui p primește adresa succesorului nodului șters. Dacă nodul șters era primul sau ultimul, se actualizează prim, respectiv ultim. Dacă nodul șters era singurul din listă, adică succesorul lui p este chiar p, lista devine vidă.

void eliminaDupaCirculara(nod *p, nod *&prim, nod *&ultim) {
    nod *q = p->urm;
    if (q == p)                // singurul nod din lista
        prim = ultim = NULL;
    else {
        p->urm = q->urm;
        if (q == prim)
            prim = q->urm;
        if (q == ultim)
            ultim = p;
    }
    delete q;
}

Problemă. Se citesc un număr natural nenul n și apoi n numere naturale. Se construiește o listă circulară cu numerele în ordinea citirii, se șterg din ea nodurile care conțin multipli de 3 și se afișează lista, pornind de la primul nod, sau mesajul lista vida.

Exemplu: pentru n = 6 și numerele 9 4 6 7 3 12 se afișează 4 7.

Descrierea soluției. Fiecare nod se verifică prin predecesorul lui. Predecesorul primului nod este ultimul nod, deci pointerul p pornește de la ultim. La fiecare pas se verifică nodul următor lui p: dacă este multiplu de 3, se șterge, iar p nu avansează; altfel p avansează. Lista nu are un nod terminal, deci numărul de pași se fixează dinainte: fiecare dintre cele n noduri inițiale se verifică o singură dată. Parcurgerea se oprește mai devreme dacă lista devine vidă.

#include <iostream>
using namespace std;

struct nod {
    int info;
    nod *urm;
};

void adaugaCirculara(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
    ultim->urm = prim;
}

void eliminaDupaCirculara(nod *p, nod *&prim, nod *&ultim) {
    nod *q = p->urm;
    if (q == p)
        prim = ultim = NULL;
    else {
        p->urm = q->urm;
        if (q == prim)
            prim = q->urm;
        if (q == ultim)
            ultim = p;
    }
    delete q;
}

int main() {
    nod *prim = NULL, *ultim = NULL;
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        adaugaCirculara(prim, ultim, x);
    }

    nod *p = ultim;                    // predecesorul primului nod
    for (int i = 1; i <= n && prim != NULL; i++)
        if (p->urm->info % 3 == 0)
            eliminaDupaCirculara(p, prim, ultim);
        else
            p = p->urm;

    if (prim == NULL)
        cout << "lista vida";
    else {
        p = prim;
        do {
            cout << p->info << " ";
            p = p->urm;
        } while (p != prim);
    }
    return 0;
}

Într-o listă circulară dublu înlănțuită, legătura spre succesor a ultimului nod păstrează adresa primului nod, iar legătura spre predecesor a primului nod păstrează adresa ultimului nod.

Lista dublu înlănțuită

Legătura ant a primului nod și legătura urm a ultimului nod au valoarea NULL. Lista se poate parcurge în ambele sensuri, iar predecesorul unui nod se află direct, fără parcurgere.

Săgețile de sus urmează legăturile urm, de la primul nod spre ultimul, iar cele de jos legăturile ant, de la ultimul nod spre primul.

Operațiile de la lista simplu înlănțuită se păstrează, dar la fiecare inserare și la fiecare ștergere se actualizează ambele legături ale nodurilor vecine.

struct nod {
    int info;
    nod *ant, *urm;   // adresele predecesorului si succesorului
};

Inserarea în lista dublu înlănțuită

La sfârșit. Nodul nou are ca predecesor ultimul nod și nu are succesor. Dacă lista este vidă, el devine primul nod; altfel, legătura urm a ultimului nod primește adresa lui.

La început. Nodul nou nu are predecesor și are ca succesor primul nod. Dacă lista este vidă, el devine ultimul nod; altfel, legătura ant a primului nod primește adresa lui.

void adaugaSfarsit(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = ultim;
    nou->urm = NULL;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
}

void adaugaInceput(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = NULL;
    nou->urm = prim;
    if (prim == NULL)
        ultim = nou;
    else
        prim->ant = nou;
    prim = nou;
}

După nodul q. Nodul nou se așază între q și succesorul lui. Dacă q are succesor, legătura ant a succesorului primește adresa nodului nou; altfel, nodul nou devine ultimul nod.

Înaintea nodului q. Nodul nou se așază între predecesorul lui q și q. Predecesorul se citește din q->ant, deci parcurgerea nu mai este necesară. Dacă q nu are predecesor, nodul nou devine primul nod.

void adaugaDupa(nod *q, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = q;
    nou->urm = q->urm;
    if (q->urm != NULL)
        q->urm->ant = nou;
    else
        ultim = nou;
    q->urm = nou;
}

void adaugaInainte(nod *&prim, nod *q, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->urm = q;
    nou->ant = q->ant;
    if (q->ant != NULL)
        q->ant->urm = nou;
    else
        prim = nou;
    q->ant = nou;
}

Parcurgerea în ambele sensuri

De la primul nod la ultimul, parcurgerea urmează legăturile urm. De la ultimul nod la primul, urmează legăturile ant și pornește de la ultim.

void afisareInainte(nod *prim) {
    for (nod *p = prim; p != NULL; p = p->urm)
        cout << p->info << " ";
    cout << endl;
}

void afisareInapoi(nod *ultim) {
    for (nod *p = ultim; p != NULL; p = p->ant)
        cout << p->info << " ";
    cout << endl;
}

Ștergerea unui nod oarecare

Nodul q se poate șterge direct, fiindcă ambii vecini ai lui sunt cunoscuți.

Pașii.

Dacă q are predecesor, legătura urm a predecesorului primește adresa succesorului lui q; altfel, q era primul nod, iar succesorul lui devine primul nod.
Dacă q are succesor, legătura ant a succesorului primește adresa predecesorului lui q; altfel, q era ultimul nod, iar predecesorul lui devine ultimul nod.
Se eliberează memoria de la adresa q.

Aceeași funcție tratează ștergerea primului nod, a ultimului nod și a unui nod din interior.

void elimina(nod *&prim, nod *&ultim, nod *q) {
    if (q->ant != NULL)
        q->ant->urm = q->urm;
    else
        prim = q->urm;         // se sterge primul nod
    if (q->urm != NULL)
        q->urm->ant = q->ant;
    else
        ultim = q->ant;        // se sterge ultimul nod
    delete q;
}

Programul complet

Problemă. Se citesc numere naturale nenule, până la citirea valorii 0. Se construiește o listă dublu înlănțuită, alocată dinamic, cu numerele în ordinea citirii. Se șterg din listă toate nodurile care conțin ultimul număr nenul citit și se afișează lista de la primul nod spre ultimul și de la ultimul spre primul sau, dacă lista este vidă, mesajul lista vida.

Exemplu: pentru 3 7 5 3 3 6 3 5 3 0 se afișează 7 5 6 5 și 5 6 5 7.

Descrierea soluției. Lista se creează prin inserări la sfârșit, iar ultimul număr nenul citit se reține într-o variabilă. La ștergere, lista se parcurge cu pointerul c. Adresa succesorului lui c se salvează înaintea ștergerii, fiindcă după eliberarea nodului câmpul c->urm nu mai poate fi citit.

#include <iostream>
using namespace std;

struct nod {
    int info;
    nod *ant, *urm;
};

void adaugaSfarsit(nod *&prim, nod *&ultim, int x) {
    nod *nou = new nod;
    nou->info = x;
    nou->ant = ultim;
    nou->urm = NULL;
    if (prim == NULL)
        prim = nou;
    else
        ultim->urm = nou;
    ultim = nou;
}

void elimina(nod *&prim, nod *&ultim, nod *q) {
    if (q->ant != NULL)
        q->ant->urm = q->urm;
    else
        prim = q->urm;
    if (q->urm != NULL)
        q->urm->ant = q->ant;
    else
        ultim = q->ant;
    delete q;
}

int main() {
    nod *prim = NULL, *ultim = NULL;
    int x, ultimulCitit = 0;
    cin >> x;
    while (x != 0) {
        adaugaSfarsit(prim, ultim, x);
        ultimulCitit = x;
        cin >> x;
    }

    nod *c = prim;
    while (c != NULL) {
        nod *urmator = c->urm;         // se salveaza inaintea stergerii
        if (c->info == ultimulCitit)
            elimina(prim, ultim, c);
        c = urmator;
    }

    if (prim == NULL)
        cout << "lista vida";
    else {
        for (c = prim; c != NULL; c = c->urm)
            cout << c->info << " ";
        cout << endl;
        for (c = ultim; c != NULL; c = c->ant)
            cout << c->info << " ";
    }
    return 0;
}

Stiva

Nodul extras este întotdeauna ultimul nod inserat, de aceea regula de funcționare a stivei se numește LIFO (last in, first out).

Stiva se implementează dinamic ca o listă simplu înlănțuită, păstrând numai adresa vârfului, în pointerul varf. Nodul din vârf se află la începutul listei, iar legătura fiecărui nod indică nodul de sub el.

Operația	Ce face	Corespondentul în lista simplu înlănțuită
inițializarea	creează stiva vidă, `varf = NULL`	inițializarea listei
adăugarea (push)	pune un nod nou în vârf	inserarea la începutul listei
extragerea (pop)	scoate nodul din vârf	ștergerea primului nod
consultarea vârfului	citește informația din vârf, `varf->info`	accesul la primul nod
testul de stivă vidă	verifică dacă `varf == NULL`	testul de listă vidă

Numai informația din vârf se poate consulta. Pentru a ajunge la un nod aflat mai jos, trebuie extrase toate nodurile de deasupra lui. Din stiva vidă nu se poate extrage niciun nod.

Materialul acesta se citește pe educamp.ro și nu se tipărește.

Ce cuprinde subcapitolul

Lista liniară
Lista simplu înlănțuită
Lista circulară
Lista dublu înlănțuită
Stiva
Coada
Arborele cu rădăcină
Arborele binar
Arborele binar de căutare
Apariții la examen

Continuă lectura ca și cursant

Cel puțin un subcapitol din fiecare capitol este disponibil gratuit și integral. Pentru a citi toate celelalte subcapitole ale disciplinei, te înscrii la cursul de pregătire.

Te înscrii, alegi în cont când începe cursul și plătești prima lună prin transfer bancar. Pentru a vedea mai întâi cum este prezentată materia, poți reveni la primul subcapitol al capitolului.

Acces la suportul de curs

25 RON / lună, fără ședințe

Ce cuprinde:

Acces la toate lecțiile disponibile
Suport de curs pentru tematica științifică și metodică
Exemple, explicații și exerciții
Acces la materialele noi adăugate pe platformă
Posibilitatea de a adresa întrebări

Poți alege și variante cu ședințe online, în grup sau individuale. Le vezi pe pagina cursului.

Ai întrebări sau o problemă? Scrie-mi pe WhatsApp, la 0745 874 576.

Înscrie-te Alte variante Cum plătești Login

Surse (4)

„Informatică. Manual pentru clasa a XI-a”, Editura Didactică și Pedagogică, București
Programa pentru concursul de ocupare a posturilor didactice, disciplina Informatică, cap. 4 „Alocarea dinamică a memoriei”
Programa pentru examenul de definitivare în învățământ, disciplina Informatică, cap. 4 „Alocarea dinamică a memoriei”
Subiecte și bareme publicate, Definitivat și Titularizare, informatică, 2003–2026

Lista liniară

Lista simplu înlănțuită

Inserarea la începutul listei

Inserarea la sfârșitul listei

Inserarea după un nod dat

Inserarea înaintea unui nod dat

Inserarea într-o listă ordonată

Parcurgerea listei

Căutarea unui nod

Ștergerea primului nod

Ștergerea ultimului nod

Ștergerea unui nod din interiorul listei

Eliberarea memoriei ocupate de listă

Programul complet

Lista circulară

Lista dublu înlănțuită

Inserarea în lista dublu înlănțuită

Parcurgerea în ambele sensuri

Ștergerea unui nod oarecare

Programul complet

Stiva

Ce cuprinde subcapitolul

🔒 Continuă lectura ca și cursant

Continuă lectura ca și cursant