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ă

Copiază
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ă

Copiază
1struct NodDublu {
2    int data;
3    NodDublu* prev;
4    NodDublu* next;
5    
6    NodDublu(int val) : data(val), prev(nullptr), next(nullptr) {}
7};

Complexitate

*O(1) dacă păstrăm pointer la tail