Проблеми з пам'яттю та вказівниками у реалізації зв'язаних списків в C++

Проблеми з пам’яттю та вказівниками у реалізації зв’язаних списків в C++

7 Березня 2024 в 18:06 35

Розглянемо проблему, яка виникає при роботі зі зв’язаними списками у мові програмування C++. У багатьох початківців програмісти часто зіштовхуються з ситуацією, коли реалізація зв’язаного списку приводить до непередбачуваної поведінки через невірне використання вказівників та розподіл пам’яті.

#include &lt;iostream&gt;
using namespace std;
class Node {
    public:
        int data;
        Node* next;
        Node() {
            data = 0;
            next = NULL;
        }
        Node(int x) {
            data = x;
            next = NULL;
        }
};
class LinkedList {
    private:
        Node* head;
    public:
        LinkedList() {
            head = NULL;
        }
        // insert a node at the end of the linked list
        void insertAtEnd(int x) {
            Node newNode = Node(x);
            Node* current = head;
            // if LL is empty
            if (head == NULL) {
                head = &newNode;
            }
            // if LL is non-empty
            else {
                while (current->next != NULL) {
                    current = current->next;
                }
                current->next = &newNode;
            }
        }
        // print out the contents of the linked list
        void display() {
            Node* current = head;
            while (current != NULL) {
                cout &lt;&lt; current->data &lt;&lt; " ";
                current = current->next;
            }
            cout &lt;&lt; endl;
        }
};
int main() {
    LinkedList llist;
    llist.insertAtEnd(1);
    llist.insertAtEnd(2);
    llist.insertAtEnd(3);
    llist.display();
    return 0;
}

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node() {

data = 0;

next = NULL;

}

Node(int x) {

data = x;

next = NULL;

}

};

class LinkedList {

private:

Node* head;

public:

LinkedList() {

head = NULL;

}

// insert a node at the end of the linked list

void insertAtEnd(int x) {

Node newNode = Node(x);

Node* current = head;

// if LL is empty

if (head == NULL) {

head = &newNode;

}

// if LL is non-empty

else {

while (current->next != NULL) {

current = current->next;

}

current->next = &newNode;

}

// print out the contents of the linked list

void display() {

Node* current = head;

while (current != NULL) {

cout << current->data << " ";

current = current->next;

}

cout << endl;

}

};

int main() {

LinkedList llist;

llist.insertAtEnd(1);

llist.insertAtEnd(2);

llist.insertAtEnd(3);

llist.display();

return 0;

}

Основна проблема полягає у невірному використанні вказівників та розподілі пам’яті. У вказаній реалізації методу insertAtEnd новий вузол створюється на стеку за допомогою локальної змінної Node newNode. Коли ця змінна виходить із області видимості (після завершення виклику функції), пам’ять, яку вона використовувала, вивільняється. Однак вказівник current->next продовжує вказувати на цю вивільнену пам’ять, що може призводити до непередбачуваної поведінки при спробі звернутися до вузлів списку.

У випадку використання оператора new для створення нового вузла пам’ять розподіляється динамічно на кшталті динамічної пам’яті, і ця пам’ять залишається доступною до тих пір, поки вона не буде явно вивільнена. Таким чином, коректно працюють всі операції зв’язаного списку, включаючи вставку та відображення даних.

Отже, використання вказівників та правильний розподіл пам’яті є ключовими аспектами реалізації зв’язаних списків у мові програмування C++, що дозволяє уникнути непередбачуваної поведінки та забезпечити коректну роботу структури даних.