Ce este o lista dublu inlantuita?

Listele dublu inlantuite sunt structuri de date dinamice. Ele au aceleasi
caracteristici de baza ca si listele simplu inlantuite. Diferenta fata de acestea consta in faptul ca, pentru fiecare nod, se retine si adresa elementului anterior, ceea ce permite traversarea listei in ambele directii.

Lista dublu inlantuita poate fi reprezentata grafic astfel:

Liste dublu inlantuite

Memorarea unei liste dublu inlantuite

Pentru memorarea listei se foloseste structura struct. Acesta structura va avea forma:

struct Nod
{
    int numar;      //Memorarea efectiva a numarului
    Nod* urmator;   //Memorarea legaturii catre urmatorul nod
    Nod* anterior;  //Memorarea legaturii catre nodul anterior
};

Nod* cap = NULL;    //Declararea listei vida

Parcurgerea si afisarea elementelor din lista dublu inlantuita

void afisareLista(Nod* cap)
{
    while (cap != NULL)
    {
        cout << cap->numar << "\n"; // Afisam numarul stocat 
        cap = cap->urmator;         // Mutam elementul curent la urmatorul element din lista
    }
}

Inserarea unui element intr-o lista dublu inlantuita

Inserare la inceput

Acesta este cazul cel mai simplu: trebuie doar alocat elementul, legat de primul element din lista si repozitionarea capului listei:

void inserareInceput(Nod* &cap, int valoare)
{
    //Creeam noul nod si ii atribuim valoarea din paramentru
    Nod *elem = new Nod;
    elem->numar = valoare;

    elem->urmator = cap; //Mutam sageata catre primul element din lista
    elem->anterior = NULL;

    if(cap != NULL)
        cap->anterior = elem; // Actualizam sageata primului element din lista
    
    cap = elem; //Inlocuim primul element din lista
}

Inserare la sfarsitul listei

void inserareFinal(Nod* &cap, int valoare)
{
    //Creeam noul nod si ii atribuim valoarea din paramentru
    Nod *elem_final = new Nod;
    elem_final->numar = valoare;
    elem_final->urmator = NULL;
    elem_final->anterior = NULL;
    
    if (cap == NULL) // In cazul in care lista noastra este vida, punem elementul in lista
        cap = elem_final;
    else
    {
        //Parcurgem lista pana la final
        Nod *nod_curent = cap;
        while (nod_curent->urmator != NULL)
            nod_curent = nod_curent->urmator;

        //Mutam sageata ultimului element catre elementul creat anterior
        nod_curent->urmator = elem_final;
        elem_final->anterior = nod_curent;
    }
}

Inserarea dupa un element dat

void inserareElement(Element* &cap, Element* element_dat, int valoare)
{
    //Creeam noul nod si ii atribuim valoarea din paramentru
    Nod *elem_creat = new Nod;
    elem_creat->numar = valoare;
    elem_creat->urmator = NULL;
    elem_creat->anterior = NULL;

    if (cap == NULL)
    {
        cap = elem_creat;
        return;
    }

    if (cap == element_dat)
    {
        elem_creat->urmator = cap;
        cap->anterior = elem_creat;
        cap = elem_creat;
        return;
    }

    elem_creat->urmator = element_dat->urmator;
    elem_creat->anterior = element_dat;
    element_dat->urmator->anterior = elem_creat;
    element_dat->urmator = elem_creat;
}

Cautarea unui element intr-o lista dublu inlantuita

Cautarea dupa valoare

Se parcurge lista pana la epuizarea acesteia sau identificarea elementului:

Nod* cautareValoare(Nod* cap, int valoare)
{
    while (cap != NULL && cap->numar != valoare)
        cap = cap->urmator;
    return cap;
}

Cautarea dupa pozitie

Nod* cautarePozitie(Nod* cap, int pozitie)
{
    int i = 0;  //Pozitia curenta

    //Parcurgem lista pana la pozitia curenta, sau
    //pana ajungem la ultimul element al listei
    while (cap != NULL && i < pozitie)
    {
        cap = cap->urmator;
        i++;
    }

    //In cazul in care am gasit pozitia ceruta, o returnam
    if (i == pozitie)
        return cap;
    else
        return NULL;
}

Stergerea unui element dintr-o lista dublu inlantuita

Stergerea unui element din interiorul listei

void stergereElement(Nod* elem)
{
    elem->anterior->urmator = elem->urmator;
    elem->urmator->anterior = elem->anterior;

    delete elem;
}

Stergerea unui element de pe o anumita pozitie

void stergereElementPozitie(Nod* &cap, int pozitie)
{
    if (pozitie == 0)
    {
        Nod* victima = cap;
        cap = cap->urmator;
        cap->anterior = NULL;
        delete victima;
    }
    else
    {
        Nod* predecesor = cautarePozitie(cap, pozitie);
        stergereElement(predecesor);
    }
}

Stergerea dupa o valoare

void stergereElementValoare(Nod* &cap, int valoare)
{
    //In cazul in care elementul vizat este capul listei noastre
    if(cap->numar == valoare)
    {
        Nod* victima = cap;
        cap = cap->urmator;
        cap->anterior = NULL;
        delete victima;
        return;
    }

    //Parcurgem lista si cautam elementul cerut
    Nod* elem = cap;
    while (elem->urmator != NULL && elem->urmator->numar != valoare)
        elem = elem->urmator;

    //Daca am gasit nodul, il stergem
    if (elem->urmator != NULL)
        stergereElement(elem);
}