Упражнения: Списъци, Итератори и Управление на Паметта

Напредък

0%

✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

---

ℹ️Структура на Упражненията

Този набор съдържа 30 упражнения, разделени в три нива на трудност:

• Лесни (1-10): Фундаментални концепции и дефиниции
• Средни (11-20): Приложение на концепции и анализ
• Трудни (21-30): Напреднало приложение и синтез

---

🟢 Лесни Упражнения (1-10)

Упражнение

10 minЛЕСНО

Задача 1: Предимство на свързания списък

Въпрос: Кое е основното предимство на свързания списък пред масива?

A) По-бърз произволен достъп до елементи B) По-добра локалност на кеша C) Динамичен размер, който може да расте или намалява по време на изпълнение D) По-малко паметно натоварване на елемент

Отговор: C) Динамичен размер, който може да расте или намалява по време на изпълнение

Обяснение: Основното предимство на свързания списък е динамичността - можем да добавяме и премахваме елементи без предварително заделена памет. Масивите имат по-бърз произволен достъп (А е невярно), по-добра локалност (В е невярно) и по-малко паметно натоварване на елемент (D е невярно, защото всеки възел трябва да съхранява указатели).

---

Упражнение

10 minЛЕСНО

Задача 2: Указател next на последния възел

Въпрос: В едносвързан списък, указателят next на последния възел трябва да сочи към първия възел за завършване на списъка.

Отговор: False (Невярно)

Обяснение: В едносвързан списък, указателят next на последния възел трябва да е nullptr (или NULL), за да обозначи края на списъка. Списък, в който последният възел сочи към първия, се нарича кръгов (циркулярен) списък и е специален вид структура.

---

Упражнение

10 minЛЕСНО

Задача 3: Указатели в C++

Въпрос: В C++, указател съхранява __________ на друга променлива.

Отговор: адреса (или паметния адрес)

Обяснение: Указателят е променлива, която съхранява паметния адрес на друга променлива. Чрез този адрес можем да достъпим стойността на променливата индиректно.

---

Упражнение

10 minЛЕСНО

Задача 4: Аритметика на указатели

Въпрос: На какво се преобразува операцията за индексиране на масив arr[3] използвайки аритметика на указатели?

A) *(arr - 3) B) *(arr + 3) C) &(arr + 3) D) arr->3

Отговор: B) *(arr + 3)

Обяснение: Операцията arr[i] е синтактична захар за *(arr + i). Добавяме i към базовия адрес на масива и дереференцираме резултата. arr + 3 сочи към четвъртия елемент, а * взема стойността на този адрес.

---

Упражнение

10 minЛЕСНО

Задача 5: Struct vs Class

Въпрос: Каква е разликата между struct и class в C++ относно достъпа до членовете по подразбиране?

Отговор: В struct, членовете са public по подразбиране, докато в class, членовете са private по подразбиране. Това е единствената реална разлика между двете ключови думи в C++. Традицията е да се използва struct за прости структури от данни и class за по-сложни обекти с поведение.

---

Упражнение

10 minЛЕСНО

Задача 6: Грешка при създаване на възел

Въпрос: Идентифицирайте грешката в този код за създаване на възел:

struct Node {
    int data;
    Node* next;
};
Node* head = new Node();
head->data = 10;
// ... програмата продължава ...
// Програмата завършва без почистване

Отговор: Изтичане на памет (Memory Leak)

Обяснение: Кодът заделя динамична памет с new, но никога не я освобождава с delete. Указателят next също не е инициализиран и може да съдържа случайна стойност. Правилният код трябва да включва:

Node* head = new Node();
head->data = 10;
head->next = nullptr;  // Инициализация
// ... използване ...
delete head;  // Освобождаване на паметта

---

Упражнение

10 minЛЕСНО

Задача 7: Времева сложност на достъп

Въпрос: Каква е времевата сложност на достъпа до елемент по индекс в едносвързан списък?

A) O(1) B) O(log n) C) O(n) D) O(n²)

Отговор: C) O(n)

Обяснение: За да достъпим елемент по индекс в едносвързан списък, трябва да обходим списъка от началото до търсената позиция. В най-лошия случай (достъп до последния елемент) трябва да преминем през всички n възела, което дава линейна времева сложност O(n). За разлика от масивите, където достъпът по индекс е O(1), свързаните списъци не поддържат произволен достъп.

---

Упражнение

10 minЛЕСНО

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

Въпрос: Възел на двусвързан списък съдържа указатели както към следващия, така и към предишния възел.

Отговор: True (Вярно)

Обяснение: Това е основната характеристика на двусвързания списък. Всеки възел съдържа два указателя: next (към следващия възел) и prev (към предишния възел). Това позволява обхождане на списъка и в двете посоки - напред и назад.

struct Node {
    int data;
    Node* next;  // Към следващия възел
    Node* prev;  // Към предишния възел
};

---

Упражнение

10 minЛЕСНО

Задача 9: Инициализация на указатели

Въпрос: Към каква стойност трябва да бъдат инициализирани указателите при създаване на нов възел?

Отговор: nullptr (или NULL)

Обяснение: При създаване на нов възел, всички указатели трябва да бъдат инициализирани към nullptr. Това гарантира, че указателят има валидна (макар и нулева) стойност и не сочи към случаен адрес в паметта. Неинициализираните указатели съдържат произволни стойности и могат да причинят сериозни грешки при дереференциране.

Node* newNode = new Node();
newNode->data = 42;
newNode->next = nullptr;  // Правилна инициализация
newNode->prev = nullptr;  // За двусвързан списък

---

Упражнение

10 minЛЕСНО

Задача 10: Операция O(1)

Въпрос: Коя операция е обикновено O(1) и за масиви, и за свързани списъци?

A) Търсене на елемент B) Достъп по индекс C) Вмъкване в началото D) Обхождане на всички елементи

Отговор: C) Вмъкване в началото

Обяснение: Вмъкването в началото е O(1) и за свързаните списъци (актуализиране на head указателя), и за динамични масиви като std::vector (макар че векторът технически е O(n) заради местенето на елементите, но std::deque го прави за O(1)). Търсенето е O(n), достъпът по индекс е O(1) само за масиви, а обхождането е O(n) и за двете структури.

---

🟡 Средни Упражнения (11-20)

Упражнение

15 minСРЕДНО

Задача 11: Обхождане и преброяване

Задача: Напишете функция за обхождане на едносвързан списък и преброяване на възлите:

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

int countNodes(Node* head) {
    // Вашата имплементация тук
}

Решение:

int countNodes(Node* head) {
    int count = 0;
    Node* current = head;
    while (current != nullptr) {
        count++;
        current = current->next;
    }
    return count;
}

Обяснение: Започваме от head и обхождаме списъка, следвайки next указателите. Увеличаваме брояча при всеки възел докато не достигнем nullptr, който означава края на списъка.

---

Упражнение

15 minСРЕДНО

Задача 12: Изтриване в края

Задача: Обяснете защо изтриването на възел в края на едносвързан списък (без tail указател) е O(n), докато същата операция в двусвързан списък (с tail указател) е O(1).

Отговор:

Едносвързан списък без tail: За да изтрием последния възел, трябва първо да намерим предпоследния възел, за да променим неговия next указател на nullptr. Това изисква обхождане на целия списък от начало до предпоследен възел - O(n) операции.

Двусвързан списък с tail: Имаме директен достъп до последния възел чрез tail указателя. Използваме неговия prev указател за да достъпим предпоследния възел и актуализираме връзките само с постоянен брой операции:

if (tail && tail->prev) {
    Node* oldTail = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete oldTail;
}

Това е O(1) операции.

---

Упражнение

15 minСРЕДНО

Задача 13: Отстраняване на бъгове

Задача: Намерете и поправете всички бъгове в тази функция за вмъкване в двусвързан списък:

void insertAtHead(Node** head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}

Подсказка: Това трябва да работи за двусвързан списък

Проблеми:

• Не се инициализира newNode->prev
• Не се актуализира prev указателят на старата глава

Коректна имплементация:

void insertAtHead(Node** head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = *head;
    newNode->prev = nullptr;  // Новият възел няма предишен

    if (*head != nullptr) {
        (*head)->prev = newNode;  // Старият head сега има предишен
    }

    *head = newNode;
}

---

Упражнение

15 minСРЕДНО

Задача 14: Iterator шаблон

Задача: Каква е целта на шаблона за дизайн Iterator и какъв проблем решава в контекста на структурите от данни?

Отговор: Шаблонът Iterator предоставя унифициран начин за обхождане на елементите в контейнер без да се излагат вътрешните му детайли за представяне (инкапсулация).

Проблем който решава: Различните структури от данни (масиви, списъци, дървета) имат различни начини за достъп до елементи. Без итератори клиентският код трябва да знае вътрешната структура за да обходи елементите.

Ключови предимства:

• Разделяне на обхождането от вътрешната структура
• Еднакъв интерфейс (++, *, !=) за различни контейнери
• Подкрепа за различни видове обхождане (forward, bidirectional, random access)
• Интеграция с C++ алгоритми и range-based for loops

---

Упражнение

15 minСРЕДНО

Задача 15: Оператори на итератор

Задача: Имплементирайте оператора за дереференциране (operator*) и оператора за неравенство (operator!=) за итератор на едносвързан списък:

template <typename T>
class SinglyLinkedListIterator {
private:
    Node<T>* current_;
public:
    SinglyLinkedListIterator(Node<T>* ptr) : current_(ptr) {}

    // Имплементирайте тези два оператора
    T& operator*() const {
        // Вашият код тук
    }

    bool operator!=(const SinglyLinkedListIterator<T>& other) const {
        // Вашият код тук
    }
};

Решение:

T& operator*() const {
    return current_->data;
}

bool operator!=(const SinglyLinkedListIterator<T>& other) const {
    return current_ != other.current_;
}

Обяснение:

• operator* - Връща референция към данните на текущия възел, позволявайки достъп и модификация чрез *iter
• operator!= - Сравнява указателите на двата итератора. Връща true ако сочат към различни възли (използва се в for loops)

---

Упражнение

15 minСРЕДНО

Задача 16: Изтичане на памет

Въпрос: Какво представлява изтичане на памет?

A) Когато програма използва твърде много памет B) Когато динамично заделена памет не се освободи след като вече не е необходима C) Когато указател сочи към невалидна памет D) Когато заделянето на памет се провали

Отговор: B) Когато динамично заделена памет не се освободи след като вече не е необходима

Обяснение: Изтичането на памет (memory leak) възниква когато програмата заделя динамична памет с new/malloc, но никога не я освобождава с delete/free. Паметта остава заделена, но програмата вече няма указател към нея, така че не може да бъде използвана или освободена. С течение на времето това води до изчерпване на наличната памет.

// Пример за memory leak:
void leak() {
    int* data = new int[100];
    // ... използване ...
    // Липсва delete[] data; ← LEAK!
}

---

Упражнение

15 minСРЕДНО

Задача 17: unique_ptr vs shared_ptr

Задача: Обяснете разликата между std::unique_ptr и std::shared_ptr относно семантиката на собственост.

Отговор:

std::unique_ptr - Уникална собственост. Само един unique_ptr може да притежава даден ресурс в даден момент. Не може да се копира, само да се премести (move). Когато unique_ptr бъде унищожен, автоматично изтрива ресурса.

std::unique_ptr<int> p1(new int(10));
// std::unique_ptr<int> p2 = p1; // ГРЕШКА! Не може да се копира
std::unique_ptr<int> p2 = std::move(p1); // OK - преместване

std::shared_ptr - Споделена собственост. Множество shared_ptr могат да споделят собствеността върху един ресурс чрез reference counting (брояч на референции). Ресурсът се изтрива само когато последният shared_ptr бъде унищожен.

std::shared_ptr<int> p1(new int(10));
std::shared_ptr<int> p2 = p1; // OK - споделяне
// Ресурсът ще бъде изтрит, когато и p1, и p2 излезат от scope

---

Упражнение

15 minСРЕДНО

Задача 18: Анализ на памет

Задача: Ще причини ли този код изтичане на памет? Обяснете защо или защо не:

void processData() {
    int* data = new int[100];
    // Обработка на данни...
    if (errorCondition) {
        return; // Ранно връщане при грешка
    }
    delete[] data;
}

Отговор: Да, ще причини изтичане на памет

Обяснение: Ако errorCondition е true, функцията ще върне рано (early return) преди да се изпълни delete[] data. Динамично заделената памет няма да бъде освободена.

Решения:

// Решение 1: Освободи паметта преди return
void processData() {
    int* data = new int[100];
    if (errorCondition) {
        delete[] data;
        return;
    }
    delete[] data;
}

// Решение 2 (по-добро): Използвай RAII
void processData() {
    std::unique_ptr<int[]> data(new int[100]);
    if (errorCondition) {
        return; // Паметта автоматично се освобождава
    }
}

---

Упражнение

15 minСРЕДНО

Задача 19: Сравнение на операции

Задача: Попълнете следващата таблица сравняваща операции:

Операция	Масив	Едносвързан списък	Двусвързан списък (с tail ptr)
Вмъкване в края	?	?	?
Изтриване в началото	?	?	?
Произволен достъп	?	?	?

Отговор:

Операция	Масив	Едносвързан списък	Двусвързан списък (с tail ptr)
Вмъкване в края	O(1)*	O(n) без tail, O(1) с tail	O(1)
Изтриване в началото	O(n)	O(1)	O(1)
Произволен достъп	O(1)	O(n)	O(n)

*За динамични масиви като std::vector (амортизирано). За статични масиви не можем да вмъкваме.

---

Упражнение

15 minСРЕДНО

Задача 20: Вмъкване след възел

Задача: Имплементирайте функция за вмъкване на възел след даден възел в двусвързан списък:

void insertAfter(Node* prevNode, int value) {
    // Вашата имплементация тук
    // Обработете крайни случаи
}

Решение:

void insertAfter(Node* prevNode, int value) {
    if (prevNode == nullptr) {
        return; // Грешка: невалиден възел
    }

    Node* newNode = new Node();
    newNode->data = value;

    // Настройка на указателите на новия възел
    newNode->next = prevNode->next;
    newNode->prev = prevNode;

    // Актуализация на next възела (ако съществува)
    if (prevNode->next != nullptr) {
        prevNode->next->prev = newNode;
    }

    // Актуализация на prevNode
    prevNode->next = newNode;
}

Важни крайни случаи:

• prevNode е nullptr - връщаме рано
• Вмъкване в края (prevNode->next е nullptr) - не актуализираме next->prev
• Вмъкване по средата - актуализираме всички 4 указателя

---

🔴 Трудни Упражнения (21-30)

Упражнение

20 minТРУДНО

Задача 21: Имплементация на push_back

Задача: Имплементирайте пълен метод push_back за клас двусвързан списък, който правилно обработва:

• Празен списък
• Непразен списък
• Заделяне на памет
• Актуализиране на head, tail и size

template <typename T>
class DoublyLinkedList {
private:
    Node<T>* head_;
    Node<T>* tail_;
    unsigned int size_;
public:
    void push_back(const T& value) {
        // Вашата пълна имплементация тук
    }
};

Решение:

void push_back(const T& value) {
    Node<T>* newNode = new Node<T>(value);

    if (tail_ == nullptr) {
        // Празен списък
        head_ = newNode;
        tail_ = newNode;
    } else {
        // Непразен списък
        tail_->next = newNode;
        newNode->prev = tail_;
        tail_ = newNode;
    }

    size_++;
}

Обяснение:

1. Заделяме нов възел с дадената стойност
2. Проверяваме дали списъкът е празен (tail_ == nullptr)
3. Ако е празен: head_ и tail_ сочат към новия възел
4. Ако не е празен: свързваме новия възел към текущия tail_ и актуализираме tail_
5. Увеличаваме size_

---

Упражнение

20 minТРУДНО

Задача 22: Коректен деструктор

Задача: Този деструктор причинява изтичане на памет. Идентифицирайте проблема и предоставете коректна имплементация:

template <typename T>
class DoublyLinkedList {
    ~DoublyLinkedList() {
        Node<T>* current = head_;
        while (current != nullptr) {
            current = current->next;
            delete current;
        }
    }
};

Проблеми:

1. Преместваме current към next преди да го изтрием
2. Когато изтриваме current, той вече сочи към next възела
3. Първият възел никога не се изтрива!

Коректна имплементация:

~DoublyLinkedList() {
    Node<T>* current = head_;
    while (current != nullptr) {
        Node<T>* temp = current->next; // Запазваме next ПРЕДИ delete
        delete current;                // Изтриваме текущия възел
        current = temp;                // Преминаваме към следващия
    }
    head_ = nullptr;
    tail_ = nullptr;
    size_ = 0;
}

Ключово: Трябва да запазим указателя към следващия възел преди да изтрием текущия!

---

Упражнение

20 minТРУДНО

Задача 23: Пълен iterator клас

Задача: Имплементирайте пълен клас iterator за двусвързан списък, който поддържа:

• Pre-increment (++iter)
• Post-increment (iter++)
• Pre-decrement (--iter)
• Дереференциране (operator*)
• Сравнение за равенство (operator==)
• Сравнение за неравенство (operator!=)

Включете методите begin() и end() в класа за списъка.

Решение:

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

    Node* head_;
    Node* tail_;
    unsigned int size_;

public:
    // Iterator клас
    class Iterator {
    private:
        Node* current_;

    public:
        Iterator(Node* ptr = nullptr) : current_(ptr) {}

        // Дереференциране
        T& operator*() const {
            return current_->data;
        }

        // Pre-increment
        Iterator& operator++() {
            if (current_) current_ = current_->next;
            return *this;
        }

        // Post-increment
        Iterator operator++(int) {
            Iterator temp(*this);
            ++(*this);
            return temp;
        }

        // Pre-decrement
        Iterator& operator--() {
            if (current_) current_ = current_->prev;
            return *this;
        }

        // Post-decrement
        Iterator operator--(int) {
            Iterator temp(*this);
            --(*this);
            return temp;
        }

        // Равенство
        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); }
};

---

Упражнение

20 minТРУДНО

Задача 24: Копиращ конструктор

Задача: Имплементирайте правилен копиращ конструктор за двусвързан списък, който извършва дълбоко копиране. Обяснете защо плиткото копиране би било проблематично.

Решение (Deep Copy):

DoublyLinkedList(const DoublyLinkedList<T>& other)
    : head_(nullptr), tail_(nullptr), size_(0) {

    Node<T>* current = other.head_;
    while (current != nullptr) {
        push_back(current->data); // Създаваме нови възли
        current = current->next;
    }
}

Защо плиткото копиране е проблематично:

// НЕПРАВИЛНО - Shallow Copy
DoublyLinkedList(const DoublyLinkedList<T>& other) {
    head_ = other.head_;  // Само копира указателя!
    tail_ = other.tail_;
    size_ = other.size_;
}

Проблеми със shallow copy:

1. Двете списъка споделят възли - промените в единия се отразяват в другия
2. Double deletion - когато единият списък бъде унищожен, той изтрива възлите, но другият все още има указатели към тях
3. Dangling pointers - след изтриване на единия, другият съдържа невалидни указатели

Пример за проблем:

DoublyLinkedList<int> list1;
list1.push_back(1);
list1.push_back(2);

DoublyLinkedList<int> list2 = list1; // Shallow copy

// Когато list2 излезе от scope и се унищожи:
// - Изтрива възлите
// - list1 все още има указатели към тези възли
// - Използването на list1 води до undefined behavior!

---

Упражнение

20 minТРУДНО

Задача 25: Откриване на цикъл

Задача: Напишете функция, която открива дали има цикъл в едносвързан списък без използване на допълнителна памет (O(1) пространствена сложност). Обяснете вашия алгоритъм.

Решение (Floyd's Cycle Detection - Tortoise and Hare):

bool hasCycle(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }

    Node* slow = head;      // Бавен указател (костенурка)
    Node* fast = head;      // Бърз указател (заек)

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;       // Движи се с 1 стъпка
        fast = fast->next->next; // Движи се с 2 стъпки

        if (slow == fast) {
            return true; // Има цикъл!
        }
    }

    return false; // Няма цикъл
}

Как работи алгоритъмът:

1. Два указателя: Използваме два указателя със различна скорост
2. Бавен (slow): Движи се с 1 възел на стъпка
3. Бърз (fast): Движи се с 2 възела на стъпка
4. Откриване: Ако има цикъл, бързият указател в крайна сметка ще "настигне" бавния
5. Без цикъл: Бързият указател ще достигне края (nullptr)

Интуиция: Представете си, че двама бегачи тичат по писта - единият тича два пъти по-бързо от другия. Ако пистата е циклична, по-бързият рано или късно ще измине един пълен кръг повече и ще настигне по-бавния.

Сложност:

• Време: O(n) - в най-лошия случай обхождаме списъка веднъж
• Памет: O(1) - използваме само два указателя

---

Упражнение

20 minТРУДНО

Задача 26: Valgrind анализ

Задача: Даден е този код с умишлено изтичане на памет, опишете точните команди, които бихте използвали с Valgrind за да го открият, и обяснете какво би показал изходът:

void leakyFunction() {
    int* arr = new int[50];
    arr[0] = 10;
    // Упс, забравихме да изтрием!
}

int main() {
    leakyFunction();
    return 0;
}

Стъпки за откриване с Valgrind:

1. Компилиране с debug символи:

g++ -g -o leak_program leak_program.cpp

2. Стартиране с Valgrind:

valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ./leak_program

Очакван изход:

==12345== Memcheck, a memory error detector
==12345== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12345== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==12345== Command: ./leak_program
==12345==
==12345==
==12345== HEAP SUMMARY:
==12345==     in use at exit: 200 bytes in 1 blocks
==12345==   total heap usage: 1 allocs, 0 frees, 200 bytes allocated
==12345==
==12345== 200 bytes in 1 blocks are definitely lost in loss record 1 of 1
==12345==    at 0x4C2E0EF: operator new[](unsigned long) (in /usr/lib/valgrind/...)
==12345==    by 0x108680: leakyFunction() (leak_program.cpp:2)
==12345==    by 0x1086A5: main (leak_program.cpp:8)
==12345==
==12345== LEAK SUMMARY:
==12345==    definitely lost: 200 bytes in 1 blocks
==12345==    indirectly lost: 0 bytes in 0 blocks
==12345==      possibly lost: 0 bytes in 0 blocks
==12345==    still reachable: 0 bytes in 0 blocks
==12345==         suppressed: 0 bytes in 0 blocks
==12345==
==12345== For lists of detected and suppressed errors, rerun with: -s
==12345== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Обяснение на изхода:

• 200 bytes in 1 blocks are definitely lost: Ясно изтичане - 50 int * 4 bytes = 200 bytes
• Stack trace: Показва точно къде е заделена паметта (ред 2 в leakyFunction)
• 1 allocs, 0 frees: Една заделена памет, нула освобождавания

Поправка:

void fixedFunction() {
    int* arr = new int[50];
    arr[0] = 10;
    delete[] arr; // Освобождаване на паметта!
}

---

Упражнение

20 minТРУДНО

Задача 27: Метод insert с итератор

Задача: Имплементирайте метод insert, който приема позиция итератор и стойност, вмъквайки нов възел преди позицията на итератора. Обработете всички крайни случаи:

template <typename T>
void DoublyLinkedList<T>::insert(iterator position, const T& value) {
    // Вашата имплементация
    // Обмислете: празен списък, вмъкване в началото,
    // вмъкване в края, вмъкване по средата
}

Решение:

template <typename T>
void DoublyLinkedList<T>::insert(iterator position, const T& value) {
    Node<T>* posNode = position.current_;

    // Случай 1: Вмъкване в края (или празен списък)
    if (posNode == nullptr) {
        push_back(value);
        return;
    }

    // Случай 2: Вмъкване в началото
    if (posNode == head_) {
        push_front(value);
        return;
    }

    // Случай 3: Вмъкване по средата
    Node<T>* newNode = new Node<T>(value);

    // Свързваме новия възел
    newNode->next = posNode;
    newNode->prev = posNode->prev;

    // Актуализираме съседните възли
    if (posNode->prev) {
        posNode->prev->next = newNode;
    }
    posNode->prev = newNode;

    size_++;
}

// Помощни методи (ако не са имплементирани)
template <typename T>
void DoublyLinkedList<T>::push_front(const T& value) {
    Node<T>* newNode = new Node<T>(value);

    if (head_ == nullptr) {
        head_ = newNode;
        tail_ = newNode;
    } else {
        newNode->next = head_;
        head_->prev = newNode;
        head_ = newNode;
    }
    size_++;
}

Крайни случаи:

1. Празен списък (position = end()): Използваме push_back
2. Вмъкване в началото (position = begin()): Използваме push_front
3. Вмъкване по средата: Актуализираме 4 указателя
4. Вмъкване в края (position = end()): Същото като празен списък

---

Упражнение

20 minТРУДНО

Задача 28: Рефакториране с RAII

Задача: Рефакторирайте този код да използва RAII принципи и интелигентни указатели за предотвратяване на изтичане на памет:

class FileProcessor {
    int* buffer;
    FILE* file;
public:
    FileProcessor(const char* filename) {
        buffer = new int[1000];
        file = fopen(filename, "r");
    }

    void process() {
        // Код за обработка, който може да хвърли изключения
        if (errorCondition) {
            throw std::runtime_error("Обработката се провали");
        }
    }

    ~FileProcessor() {
        delete[] buffer;
        fclose(file);
    }
};

Рефакториран код с RAII:

#include <memory>
#include <vector>
#include <fstream>
#include <stdexcept>

// Помощен клас за управление на FILE*
class FileHandle {
private:
    FILE* file_;

public:
    FileHandle(const char* filename, const char* mode) {
        file_ = fopen(filename, mode);
        if (!file_) {
            throw std::runtime_error("Неуспешно отваряне на файл");
        }
    }

    ~FileHandle() {
        if (file_) {
            fclose(file_);
        }
    }

    // Забраняваме копиране
    FileHandle(const FileHandle&) = delete;
    FileHandle& operator=(const FileHandle&) = delete;

    FILE* get() { return file_; }
};

// Рефакториран FileProcessor с RAII
class FileProcessor {
private:
    std::vector<int> buffer;  // Автоматично управление на памет
    FileHandle file;          // RAII обвивка за FILE*

public:
    FileProcessor(const char* filename)
        : buffer(1000),       // std::vector управлява паметта
          file(filename, "r") // FileHandle управлява файла
    {
        // Конструкторът е изключение-безопасен!
    }

    void process() {
        // Код за обработка
        if (errorCondition) {
            throw std::runtime_error("Обработката се провали");
            // Паметта и файлът автоматично се освобождават!
        }
    }

    // Деструкторът е автоматичен - не е нужен!
    // ~FileProcessor() = default;
};

// Алтернатива с std::unique_ptr
class FileProcessor2 {
private:
    std::unique_ptr<int[]> buffer;
    std::unique_ptr<FILE, decltype(&fclose)> file;

public:
    FileProcessor2(const char* filename)
        : buffer(std::make_unique<int[]>(1000)),
          file(fopen(filename, "r"), &fclose)
    {
        if (!file) {
            throw std::runtime_error("Неуспешно отваряне на файл");
        }
    }

    void process() {
        if (errorCondition) {
            throw std::runtime_error("Обработката се провали");
        }
    }
};

// Най-добър подход - използвайте C++ iostream
class FileProcessor3 {
private:
    std::vector<int> buffer;
    std::ifstream file;

public:
    FileProcessor3(const char* filename)
        : buffer(1000),
          file(filename)
    {
        if (!file.is_open()) {
            throw std::runtime_error("Неуспешно отваряне на файл");
        }
    }

    void process() {
        if (errorCondition) {
            throw std::runtime_error("Обработката се провали");
        }
    }
};

Предимства на RAII подхода:

1. Автоматично освобождаване: Паметта и файловете се освобождават автоматично
2. Изключение-безопасност: Ресурсите се освобождават дори при изключения
3. По-чист код: Няма нужда от explicit cleanup код
4. Предотвратяване на грешки: Не може да забравите да освободите ресурси

---

Упражнение

20 minТРУДНО

Задача 29: Избор на структура

Задача: Имате приложение, което трябва да:

1. Често вмъква елементи и на двата края
2. Понякога достъпва средния елемент
3. Обхожда напред и назад
4. Минимизира използването на памет

Трябва ли да използвате масив, едносвързан списък или двусвързан списък? Обосновете избора си с анализ на сложността и компромиси.

Анализ на изискванията:

Сравнение на Структури

Изискване	Масив (std::vector)	Едносвързан	Двусвързан
1. Вмъкване и в двата края	❌ O(n) за начало ✅ O(1) за край*	✅ O(1) за начало ❌ O(n) за край без tail	✅ O(1) и за двата
2. Достъп до среден елемент	✅ O(1)	❌ O(n)	❌ O(n)
3. Двупосочно обхождане	✅ O(n)	❌ Само напред	✅ O(n) и двете посоки
4. Минимизиране на памет	✅ Най-ефективен	⚠️ Средно (1 указател)	❌ Най-много (2 указателя)

*амортизирано

Препоръка: Двусвързан Списък

Обосновка:

1. Изискване 1 (Критично): Двусвързаният списък е единствената структура, която предлага O(1) вмъкване и в двата края без компромиси

2. Изискване 2 (Понякога): Макар достъпът до средния елемент да е O(n), това е периодична операция и не е критична

3. Изискване 3 (Важно): Двусвързаният списък естествено поддържа двупосочно обхождане

4. Изискване 4 (Компромис): Макар двусвързаният списък да използва най-много памет на възел, той не води до прекомерна консумация като цяло

Алтернативни решения:

Вариант A: std::deque (Двупосочна опашка)

std::deque<int> data;
// Предимства:
// - O(1) вмъкване и в двата края
// - По-бърз достъп до среден елемент от списък
// - По-добра кеш локалност
// Препоръчително, ако достъпът до средата е по-чест

Вариант B: Хибриден подход

// Използвайте двусвързан списък + кеш за последен достъпен елемент
class OptimizedList {
    DoublyLinkedList<int> list;
    struct {
        Node* node;
        size_t index;
    } cache;

    Node* getMiddle() {
        // Използвайте кеша за оптимизация
    }
};

Заключение: За дадените изисквания двусвързан списък е най-добрият избор, тъй като покрива всички критични случаи ефективно, въпреки по-голямата консумация на памет.

---

Упражнение

20 minТРУДНО

Задача 30: Метод reverse()

Задача: Проектирайте и имплементирайте генеричен метод reverse() за двусвързан списък, който обръща списъка на място (без заделяне на нови възли). Вашата имплементация трябва да:

• Обработва празни списъци
• Обработва списъци с един възел
• Правилно актуализира всички указатели (head, tail, next, prev)
• Поддържа O(n) времева сложност и O(1) пространствена сложност

template <typename T>
void DoublyLinkedList<T>::reverse() {
    // Вашата имплементация тук
}

Решение:

template <typename T>
void DoublyLinkedList<T>::reverse() {
    // Случай 1: Празен списък или един елемент
    if (head_ == nullptr || head_ == tail_) {
        return; // Нищо за правене
    }

    // Случай 2: Обръщане на списъка
    Node<T>* current = head_;
    Node<T>* temp = nullptr;

    // Обхождаме списъка и разменяме next и prev на всеки възел
    while (current != nullptr) {
        // Запазваме next преди да го презапишем
        temp = current->prev;

        // Разменяме next и prev
        current->prev = current->next;
        current->next = temp;

        // Преминаваме към следващия възел (който сега е в prev!)
        current = current->prev;
    }

    // Разменяме head и tail
    // temp сочи към prev на старата глава, т.е. nullptr
    // Новата глава е prev на старата глава (защото разменихме указателите)
    temp = head_;
    head_ = tail_;
    tail_ = temp;
}

Алтернативна имплементация (по-ясна):

template <typename T>
void DoublyLinkedList<T>::reverse() {
    // Празен списък или един елемент
    if (head_ == nullptr || head_->next == nullptr) {
        return;
    }

    Node<T>* current = head_;

    // Обхождаме и разменяме указателите
    while (current != nullptr) {
        // Swap next and prev
        Node<T>* nextNode = current->next;
        current->next = current->prev;
        current->prev = nextNode;

        // Преминаваме към следващия (сега в prev)
        current = nextNode;
    }

    // Swap head and tail
    Node<T>* temp = head_;
    head_ = tail_;
    tail_ = temp;
}

Обяснение стъпка по стъпка:

Представете си списък: 1 ↔ 2 ↔ 3 ↔ 4

Преди обръщане:

head_ → [1] ↔ [2] ↔ [3] ↔ [4] ← tail_

Стъпка 1: Обхождаме и разменяме next/prev за всеки възел:

[1]: next=2, prev=null  →  next=null, prev=2
[2]: next=3, prev=1     →  next=1, prev=3
[3]: next=4, prev=2     →  next=2, prev=4
[4]: next=null, prev=3  →  next=3, prev=null

Стъпка 2: Разменяме head_ и tail_:

head_ → [4] ↔ [3] ↔ [2] ↔ [1] ← tail_

След обръщане: 4 ↔ 3 ↔ 2 ↔ 1

Тестване:

// Тест
DoublyLinkedList<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);

std::cout << "Преди: ";
list.display(); // 1 2 3 4

list.reverse();

std::cout << "След: ";
list.display(); // 4 3 2 1

Анализ на сложността:

• Време: O(n) - обхождаме списъка веднъж
• Памет: O(1) - използваме само временни променливи

---

Насоки за Решаване

🟢 Лесни (1-10)

Фокусирайте се върху:

• Дефиниции и терминология
• Основни концепции
• Разпознаване на структури
• Прости операции

🟡 Средни (11-20)

Изискват:

• Приложение на концепции
• Прости имплементации
• Анализ на код
• Разбиране на сложност

🔴 Трудни (21-30)

Изискват:

• Синтез на концепции
• Пълни имплементации
• Обработка на крайни случаи
• Оптимизация и дизайн

✅Съвети за Успех

• Начертайте диаграми: Винаги визуализирайте указателите преди имплементация
• Тествайте крайни случаи: Празен списък, един елемент, много елементи
• Използвайте инструменти: Valgrind/ASan за проверка на памет
• Коментирайте: Обяснете логиката и обработката на специални случаи
• Прочетете внимателно: Разберете всички изисквания преди да започнете
• Преглеждайте примерите: Референцирайте лекцията за помощ

---

Успех с упражненията! 🎓