Structuri de Date Liniare Implementate Dinamic – Liste Liniare Dublu Înlanțuite 7
1. Obiectivele lecției:
- Să înțeleagă conceptul de listă liniară dublu înlănțuită.
- Să învețe cum să implementeze o listă dublu înlănțuită dinamic.
- Să implementeze operații comune: adăugare, ștergere, parcurgere în ambele sensuri.
2. Ce este o listă liniară dublu înlănțuită?
- Definiție:
O listă dublu înlănțuită este o structură de date compusă din noduri, unde fiecare nod conține:- O valoare (informație utilă).
- Un pointer către următorul nod.
- Un pointer către nodul anterior.
- Caracteristici:
- Permite parcurgerea în ambele direcții.
- Primul nod al listei (denumit head) are pointerul către nodul anterior setat la nullptr.
- Ultimul nod al listei (denumit tail) are pointerul către următorul nod setat la nullptr.
- Structura nodului:
struct Nod {
int valoare;
Nod* urmator;
Nod* anterior;
};
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Permite parcurgerea bidirecțională. | Necesită mai multă memorie pentru pointere suplimentare. |
| Operații de inserare și ștergere eficiente. | Mai complicat de implementat decât listele simplu înlănțuite. |
| Utilă pentru structuri precum deque sau liste circulare. | Mai greu de gestionat pentru noduri multiple. |
4. Structura nodului
struct Nod {
int valoare; // Informația stocată în nod
Nod* urmator; // Pointer către următorul nod
Nod* anterior; // Pointer către nodul anterior
};
5. Operații comune pe liste dublu înlănțuite
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
nod->anterior = nullptr;
return nod;
}
2. Adăugarea unui element
- Adăugare la început:
void adaugaInceput(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = tail = nod;
} else {
nod->urmator = head;
head->anterior = nod;
head = nod;
}
}
- Adăugare la sfârșit:
void adaugaSfarsit(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (tail == nullptr) {
head = tail = nod;
} else {
nod->anterior = tail;
tail->urmator = nod;
tail = nod;
}
}
3. Ștergerea unui element
- Ștergere de la început:
void stergeInceput(Nod*& head, Nod*& tail) {
if (head == nullptr) return;
Nod* temp = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->urmator;
head->anterior = nullptr;
}
delete temp;
}
- Ștergere de la sfârșit:
void stergeSfarsit(Nod*& head, Nod*& tail) {
if (tail == nullptr) return;
Nod* temp = tail;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->anterior;
tail->urmator = nullptr;
}
delete temp;
}
- Ștergerea unui nod cu o valoare specificată:
void stergeValoare(Nod*& head, Nod*& tail, int valoare) {
if (head == nullptr) return;
Nod* temp = head;
while (temp != nullptr && temp->valoare != valoare) {
temp = temp->urmator;
}
if (temp == nullptr) return;
if (temp == head) {
stergeInceput(head, tail);
} else if (temp == tail) {
stergeSfarsit(head, tail);
} else {
temp->anterior->urmator = temp->urmator;
temp->urmator->anterior = temp->anterior;
delete temp;
}
}
4. Parcurgerea listei
- Parcurgere de la început la sfârșit:
void parcurgeInainte(Nod* head) {
Nod* temp = head;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
- Parcurgere de la sfârșit la început:
void parcurgeInapoi(Nod* tail) {
Nod* temp = tail;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->anterior;
}
cout << endl;
}
6. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* urmator;
Nod* anterior;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
nod->anterior = nullptr;
return nod;
}
void adaugaInceput(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (head == nullptr) {
head = tail = nod;
} else {
nod->urmator = head;
head->anterior = nod;
head = nod;
}
}
void adaugaSfarsit(Nod*& head, Nod*& tail, int valoare) {
Nod* nod = creeazaNod(valoare);
if (tail == nullptr) {
head = tail = nod;
} else {
nod->anterior = tail;
tail->urmator = nod;
tail = nod;
}
}
void parcurgeInainte(Nod* head) {
Nod* temp = head;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
void parcurgeInapoi(Nod* tail) {
Nod* temp = tail;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->anterior;
}
cout << endl;
}
void stergeInceput(Nod*& head, Nod*& tail) {
if (head == nullptr) return;
Nod* temp = head;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->urmator;
head->anterior = nullptr;
}
delete temp;
}
void stergeSfarsit(Nod*& head, Nod*& tail) {
if (tail == nullptr) return;
Nod* temp = tail;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->anterior;
tail->urmator = nullptr;
}
delete temp;
}
int main() {
Nod* head = nullptr;
Nod* tail = nullptr;
adaugaInceput(head, tail, 10);
adaugaInceput(head, tail, 20);
adaugaSfarsit(head, tail, 30);
cout << „Parcurgere înainte: „;
parcurgeInainte(head);
cout << „Parcurgere înapoi: „;
parcurgeInapoi(tail);
stergeInceput(head, tail);
cout << „După ștergerea primului nod: „;
parcurgeInainte(head);
stergeSfarsit(head, tail);
cout << „După ștergerea ultimului nod: „;
parcurgeInainte(head);
return 0;
}
7. Activități practice pentru elevi
- Implementați o funcție care determină lungimea unei liste dublu înlănțuite.
- Scrieți o funcție care inserează un nod înainte de un nod specificat.
- Realizați o funcție care inversează o listă dublu înlănțuită.
8. Scheme logice
- Adăugare:
- Creează nod -> Actualizează legăturile -> Actualizează head sau tail.
- Ștergere:
- Verifică dacă lista este goală -> Actualizează legăturile -> Eliberează memoria.
9. Concluzie
- Listele dublu înlănțuite oferă flexibilitate și eficiență pentru operații bidirecționale.
- Sunt utile în aplicații care necesită acces rapid în ambele sensuri.
- Practica este esențială pentru a înțelege și a implementa corect această structură de date.