InformaticăliceuClasa 11dificil
Liste Înlănțuite în C++ - Implementare Completă
Implementează liste simplu și dublu înlănțuite: inserare, ștergere, parcurgere și operații avansate.
2 luni în urmă
0 vizualizări
40 minute
Liste Înlănțuite în C++
Ce este o Listă Înlănțuită?
O structură de date liniară în care elementele nu sunt stocate contiguu în memorie, ci sunt legate prin pointeri.
Lista Simplu Înlănțuită
1#include <iostream> 2using namespace std; 3 4struct Nod { 5 int data; 6 Nod* next; 7 8 Nod(int val) : data(val), next(nullptr) {} 9}; 10 11class ListaSimpla { 12private: 13 Nod* head; 14 15public: 16 ListaSimpla() : head(nullptr) {} 17 18 // Inserare la început 19 void inserareInceput(int val) { 20 Nod* nou = new Nod(val); 21 nou->next = head; 22 head = nou; 23 } 24 25 // Inserare la final 26 void inserareFinal(int val) { 27 Nod* nou = new Nod(val); 28 if (!head) { 29 head = nou; 30 return; 31 } 32 Nod* temp = head; 33 while (temp->next) { 34 temp = temp->next; 35 } 36 temp->next = nou; 37 } 38 39 // Ștergere element 40 void sterge(int val) { 41 if (!head) return; 42 43 if (head->data == val) { 44 Nod* temp = head; 45 head = head->next; 46 delete temp; 47 return; 48 } 49 50 Nod* temp = head; 51 while (temp->next && temp->next->data != val) { 52 temp = temp->next; 53 } 54 55 if (temp->next) { 56 Nod* deSters = temp->next; 57 temp->next = temp->next->next; 58 delete deSters; 59 } 60 } 61 62 // Afișare 63 void afisare() { 64 Nod* temp = head; 65 while (temp) { 66 cout << temp->data << " -> "; 67 temp = temp->next; 68 } 69 cout << "NULL" << endl; 70 } 71 72 // Destructor 73 ~ListaSimpla() { 74 while (head) { 75 Nod* temp = head; 76 head = head->next; 77 delete temp; 78 } 79 } 80}; 81 82int main() { 83 ListaSimpla lista; 84 lista.inserareFinal(1); 85 lista.inserareFinal(2); 86 lista.inserareFinal(3); 87 lista.inserareInceput(0); 88 89 lista.afisare(); // 0 -> 1 -> 2 -> 3 -> NULL 90 91 lista.sterge(2); 92 lista.afisare(); // 0 -> 1 -> 3 -> NULL 93 94 return 0; 95}
Lista Dublu Înlănțuită
1struct NodDublu { 2 int data; 3 NodDublu* prev; 4 NodDublu* next; 5 6 NodDublu(int val) : data(val), prev(nullptr), next(nullptr) {} 7};
Complexitate
| Operație | Listă înlănțuită | Vector |
|---|---|---|
| Acces index | O(n) | O(1) |
| Inserare început | O(1) | O(n) |
| Inserare final | O(n) sau O(1)* | O(1) |
| Ștergere | O(n) | O(n) |
*O(1) dacă păstrăm pointer la tail
Tutorialul te-a ajutat?
Dacă ai nevoie de ajutor personalizat, găsește un profesor calificat pentru meditații
