Двусвързан Списък, Iterator и Управление на Паметта в C++

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

✓Обясните структурата и предимствата на двусвързан списък
✓Разберете и приложите шаблона Iterator за масиви и списъци в C++
✓Разпознавате и предотвратявате изтичане на памет в C++ код
✓Приложите добри практики при управление на паметта в C++

1. Въведение и Мотивация

💡Защо са важни списъците и итераторите в C++?

Списъците са фундаментална структура от данни, която позволява динамично добавяне и премахване на елементи по време на изпълнение на програмата. За разлика от масивите, които имат фиксиран размер, списъците могат да се разширяват и свиват по нужда, което ги прави изключително гъвкави за работа с променливи количества данни.

Итераторите в C++ предоставят универсален начин за достъп до елементите на различни контейнери, без да се налага да променяте кода си при смяна на типа на контейнера. Те скриват сложната логика за обхождане на дадена структура, предлагайки прост и познат интерфейс.

Въпросът за изтичането на памет

⚠️Сериозен Проблем

Изтичането на памет (memory leak) е сериозен и коварен проблем в C++, който възниква, когато динамично заделена памет не бъде освободена след използване. Това води до натрупване на неизползвана памет, което намалява производителността и може да доведе до срив на програмата.

Правилното управление на паметта е от решаващо значение за стабилността на C++ приложенията!

2. Преговор на Списъци и Динамична Памет

2.1. Основни типове свързани списъци

Свързан Списък (Singly Linked)

Всеки възел има указател next към следващия
Обхождане само в една посока (напред)
По-малка консумация на памет
Бързо добавяне/премахване в началото

Двусвързан Списък (Doubly Linked)

Всеки възел има prev и next указатели
Обхождане в двете посоки
По-голяма консумация на памет
По-ефективно премахване на произволни елементи

2.2. Управление на динамичната памет в C++

В C++ паметта може да се заделя динамично с оператора new и да се освобождава с delete.

Пример за заделяне и освобождаване:

int* ptr = new int(10); // Заделяне на памет за един int
std::cout << *ptr << std::endl; // Извежда 10
delete ptr;             // Освобождаване на паметта
ptr = nullptr;          // Добра практика: задаване на nullptr

За масиви използваме new[] и delete[]:

int* arr = new int[5];  // Заделяне на памет за масив
// ... работа с arr ...
delete[] arr;           // Освобождаване на паметта
arr = nullptr;

❌

❌ Изтичане на Памет

int* ptr = new int(10); // Заделяме памет 1
ptr = new int(20);      // Заделяме памет 2
                      // Памет 1 изтича!
delete ptr;             // Освобождаваме само памет 2

✅

✅ Правилно Управление

int* ptr = new int(10);
// ... използване ...
delete ptr;             // Освобождаване
ptr = nullptr;          // Сигурност

ptr = new int(20);      // Ново заделяне
delete ptr;
ptr = nullptr;

✅Добри Практики за Управление на Паметта

Винаги освобождавайте заделената памет с delete или delete[]
Използвайте умни указатели (std::unique_ptr, std::shared_ptr)
Избягвайте "голи" указатели, когато е възможно
Проверявайте за изтичания с инструменти като Valgrind или AddressSanitizer

3. Двусвързан Списък: Реализация и Анализ

3.1. Структура на елементите

ℹ️Структура на Възел

Всеки възел (node) в двусвързан списък съдържа:

Данни (стойността, която се съхранява)
Два указателя:
- prev - към предходния елемент
- next - към следващия елемент

Тази структура позволява:

Обхождане на списъка в двете посоки
По-ефективно премахване на произволни елементи

struct Node {
    int data;
    Node* prev;
    Node* next;

    // Конструктор за улеснение
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

3.2. Основни операции

Добавяне на елемент (add / insert):

Ако е известен указател към елемента → O(1) константно време
Просто актуализираме указателите на новия елемент и съседните му

Премахване на елемент (remove / erase):

Ако е известен указател към елемента → O(1) константно време
Актуализираме указателите на предходния и следващия елемент

Обхождане на списъка (traverse):

Може да се извършва от началото към края или обратно
Обхождането на целия списък отнема O(n) линейно време

3.3. Предимства и недостатъци

✅ Предимства

Бързо добавяне и премахване на елементи
Възможност за обхождане в двете посоки
Ефективно премахване при известен указател
Динамичен размер

❌ Недостатъци

По-голяма паметова сложност (допълнителен указател)
По-бавно търсене на елемент по индекс
По-сложна имплементация
Не се кешира добре (несвързана памет)

3.4. Примерна реализация

#include <iostream>

// Структура на възел в двусвързан списък
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// Клас за двусвързан списък
class DoublyLinkedList {
private:
    Node* head; // Указател към първия възел
    Node* tail; // Указател към последния възел

public:
    // Конструктор
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // Деструктор за освобождаване на паметта
    ~DoublyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next_node = current->next;
            delete current;
            current = next_node;
        }
        head = nullptr;
        tail = nullptr;
    }

    // Добавяне на елемент в края на списъка
    void add(int value) {
        Node* newNode = new Node(value);

        if (tail) { // Ако списъкът не е празен
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        } else { // Ако списъкът е празен
            head = newNode;
            tail = newNode;
        }
    }

    // Премахване на конкретен възел
    void remove(Node* node_to_remove) {
        if (!node_to_remove) return;

        if (node_to_remove->prev) {
            node_to_remove->prev->next = node_to_remove->next;
        } else { // Ако премахваме head
            head = node_to_remove->next;
        }

        if (node_to_remove->next) {
            node_to_remove->next->prev = node_to_remove->prev;
        } else { // Ако премахваме tail
            tail = node_to_remove->prev;
        }

        delete node_to_remove; // Освобождаване на паметта
    }

    // Обхождане и извеждане на елементите
    void display() const {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    Node* getHead() const { return head; }
};

⚠️Важно за Деструктора!

Обърнете внимание на деструктора ~DoublyLinkedList(). Той е от ключово значение за правилното освобождаване на цялата памет, заета от възлите на списъка. Без него бихме имали мащабно изтичане на памет!

Как можем да подобрим тази имплементация?

Добавяне на Copy Constructor и Assignment Operator - за правилно копиране
Move Semantics - за ефективно преместване на ресурси
Sentinel Nodes - фиктивни head/tail за опростяване на граничните случаи
Template реализация - за работа с различни типове данни
Проверка за грешки - валидация на входните параметри

4. Iterator Дизайн Патърн

4.1. Същност и роля на итераторите

ℹ️Какво е Iterator?

Итераторът е дизайн патърн, който предоставя унифициран начин за обхождане на елементите на колекция, независимо от вътрешната ѝ структура.

Ролята на итератора:

Абстракция - скрива детайлите на вътрешната структура
Унифициран интерфейс - един и същ API за различни контейнери
Безопасност - може да следи границите на колекцията

4.2. Имплементация на итератори

За масивите:

template<typename T>
class ArrayIterator {
private:
    T* current; // Указател към текущия елемент
    T* end_ptr; // Указател към края

public:
    ArrayIterator(T* start, T* end) : current(start), end_ptr(end) {}

    // Достъп до стойността
    T& operator*() const {
        return *current;
    }

    // Преместване към следващия (префикс)
    ArrayIterator& operator++() {
        ++current;
        return *this;
    }

    // Проверка за равенство
    bool operator==(const ArrayIterator& other) const {
        return current == other.current;
    }

    bool operator!=(const ArrayIterator& other) const {
        return current != other.current;
    }
};

За двусвързан списък:

template<typename T>
class DoublyLinkedListWithIterator {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(T val) : data(val), prev(nullptr), next(nullptr) {}
    };

    Node* head;
    Node* tail;

public:
    // Клас Iterator
    class Iterator {
    private:
        Node* current;

    public:
        Iterator(Node* node) : current(node) {}

        // Достъп до стойността
        T& operator*() const {
            return current->data;
        }

        // Преместване напред
        Iterator& operator++() {
            if (current) current = current->next;
            return *this;
        }

        // Преместване назад (за двусвързан списък)
        Iterator& operator--() {
            if (current) current = current->prev;
            return *this;
        }

        // Проверка за равенство
        bool operator==(const Iterator& other) const {
            return current == other.current;
        }

        bool operator!=(const Iterator& other) const {
            return current != other.current;
        }
    };

    // Методи за получаване на итератори
    Iterator begin() { return Iterator(head); }
    Iterator end() { return Iterator(nullptr); }
};

ℹ️Ключова Разлика

При масивите итераторът работи с обикновени указатели и аритметика, докато при списъците трябва да обхожда чрез полетата next и prev на възлите.

4.3. Итератори в STL

STL (Standard Template Library) предоставя унифициран интерфейс за обхождане на различни контейнери:

#include <vector>
#include <list>
#include <iostream>

int main() {
    // Итератор за вектор (масив)
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Итератор за свързан списък
    std::list<int> lst = {10, 20, 30};
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Предимството: Един и същ цикъл работи с различни контейнери!

5. Изтичане на Памет

5.1. Какво е изтичане на памет?

⚠️Определение

Изтичане на памет (memory leak) е ситуация, при която програма заделя динамична памет (чрез new), но не я освобождава (с delete), след като вече не я използва.

Последици: Натрупване на неизползвана памет → изчерпване на ресурси → срив

5.2. Причини за изтичане на памет

Забравяне на delete след new
Изключения (exception) преди delete
Грешки в логиката на програмата
Презаписване на указател преди освобождаване

// Пример за изтичане
int* ptr = new int(10); // Заделяме памет 1
ptr = new int(20);      // Презаписваме указателя - памет 1 изтича!
delete ptr;             // Освобождаваме само памет 2

5.4. Инструменти за откриване

✅Мощни Инструменти

Valgrind (Linux) - най-често използван, показва къде точно е заделена паметта
AddressSanitizer (ASan) - вграден в GCC/Clang, бърз и ефективен
Visual Studio Diagnostic Tools - за Windows с графичен интерфейс
Dr. Memory - за Windows и Linux

5.5. Демонстрация

#include <iostream>

void leakyFunction() {
    int* ptr = new int[100]; // Заделяме памет
    // ... използваме ptr ...
    // Забравя се delete[] ptr;  <-- Изтичане!
}

int main() {
    for (int i = 0; i < 1000; ++i) {
        leakyFunction(); // Всяко извикване "изтича" 400 байта
    }
    return 0;
}

Анализ с Valgrind:

valgrind --leak-check=full ./a.out

Valgrind ще покаже точно къде е заделена паметта, която не е освободена!

void fixedFunction() {
    int* ptr = new int[100];
    // ... използваме ptr ...
    delete[] ptr; // Паметта се освобождава!
}

6. Добри Практики и Превенция

6.1. Използване на Smart Pointers и RAII

ℹ️RAII - Resource Acquisition Is Initialization

Основната идея: Когато създавате обект, той придобива ресурсите в конструктора и ги освобождава автоматично в деструктора. Това гарантира надеждно освобождаване дори при изключения!

#include <memory>

void safeFunction() {
    std::unique_ptr<int> data = std::make_unique<int>(12345);
    // Паметта се освобождава автоматично!
}

Три основни типа smart pointers:

std::unique_ptr

Ексклузивна собственост

Само един притежател
Не може да се копира
Може да се премести
Нулев overhead

std::shared_ptr

Споделена собственост

Множество притежатели
Reference counting
Автоматично освобождаване
Малък overhead

std::weak_ptr

Слаба референция

Не увеличава броя
Предотвратява цикли
Трябва да се "заключи"
За наблюдение

6.2. Ръчно управление

⚠️Кога е необходимо?

Наследен код, който не може да се промени
Взаимодействие с C API-та
Високопроизводителни системи
Вградени системи с ограничени ресурси
Нискоуровневи структури от данни

✅Най-добри практики при ръчно управление

Преминавайте към smart pointer веднага след създаване
Определете ясна собственост над всеки ресурс
Използвайте RAII принципите
Избягвайте "голи" указатели
Редовно тествайте с инструменти

7. Обобщение и Заключение

✅Какво научихме днес