Ce este o lista simpla inlantuita?

Listele simplu inlantuite sunt structuri de date dinamice. Fiecare nod al listei contine, in afara de informatia utila, adresa urmatorului element. Aceasta organizare permite numai acces secvential la elementele listei. Pentru accesarea listei trebuie cunoscuta adresa primului element (numita capul listei); elementele urmatoare sunt accesate parcurgand lista.

Lista simplu inlantuita poate fi reprezentata grafic astfel:

Liste simplu inlantuite

Memorarea unei liste simplu 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* cap = NULL;    //Declararea listei vida

Parcurgerea si afisarea elementelor din lista simplu 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 simplu 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

    cap = elem; //Inlocuim primul element din lista
}

Inserare la sfarsitul listei

In acest caz trebuie intai parcursa lista si dupa aceea adaugat elementul si legat de
restul listei. De asemenea, trebuie avut in vedere cazul in care lista este vida.

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;

    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;
    }
}

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;

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

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

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

Cautarea unui element intr-o lista simplu 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 simplu inlantuita

Stergerea unui element din interiorul listei

Pentru a sterge un element dintr-o lista simplu inlantuita, trebuie sa transmitem prin parametrul elementul dinaintea lui. Vom modifica sageata predecesorului, sa sara peste elementul nostru curent, direct la vecinul victimei noastre.

void stergereElement(Nod* predecesor)
{
    Nod* victima = predecesor->urmator;
   
    predecesor->urmator = predecesor->urmator->urmator;
    
    delete victima;
}

Stergerea unui element de pe o anumita pozitie

void stergereElementPozitie(Nod* &cap, int pozitie)
{
    //In cazul in care primul element este cel ce trebuie sters
    if (pozitie == 0)
    {
        Nod* victima = cap;
        cap = cap->urmator;
        delete victima;
    }
    else
    {
        Nod* predecesor = cautarePozitie(cap, pozitie-1);
        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;
        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);
}