Ce este o lista simpla inlantuita?
Listele simplu înlănțuite sunt structuri de date dinamice. Fiecare nod al listei conține, pe lângă
informația utilă, adresa următorului element. Această organizare permite doar acces secvențial
la elementele listei. Pentru a accesa lista, trebuie cunoscută adresa primului element (numită
capul listei); elementele următoare sunt accesate prin parcurgerea listei.
Lista simplu înlănțuită poate fi reprezentată 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 nr; // Memorarea efectivă a numărului
Nod* urm; // Legătura către următorul nod
};
Nod* cap = NULL; // Declararea listei vide
Parcurgerea si afisarea elementelor din lista
simplu inlantuita
void afisareLista(Nod* cap)
{
while (cap != NULL)
{
cout << cap->nr << "\n"; // Afisam numarul stocat
cap = cap->urm; // 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->nr = valoare;
elem->urm = 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->nr = valoare;
elem_final->urm = 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->urm != NULL)
nod_curent = nod_curent->urm;
//Mutam sageata ultimului element catre elementul creat
anterior
nod_curent->urm = 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->nr = valoare;
elem_creat->urm = NULL;
if (cap == NULL)
{
cap = elem_creat;
return;
}
if (cap == element_dat)
{
elem_creat->urm = cap;
cap = elem_creat;
return;
}
elem_creat->urm = element_dat->urmator;
element_dat->urm = 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->nr != valoare)
cap = cap->urm;
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->urm;
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* p)
{
Nod* x = p->urm;
p->urm = p->urm->urm;
delete x;
}
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* x = cap;
cap = cap->urm;
delete x;
}
else
{
Nod* p = cautarePozitie(cap, pozitie-1);
stergereElement(p);
}
}
Stergerea dupa o valoare
void stergereElementValoare(Nod* &cap, int valoare)
{
//In cazul in care elementul vizat este capul listei noastre
if(cap->nr == valoare)
{
Nod* x = cap;
cap = cap->urm;
delete x;
return;
}
//Parcurgem lista si cautam elementul cerut
Nod* elem = cap;
while (elem->urm != NULL && elem->urm->nr != valoare)
elem = elem->urm;
//Daca am gasit nodul, il stergem
if (elem->urm != NULL)
stergereElement(elem);