int arr[5] = {10, 20, 30, 40, 50};
int value = arr[2];  // O(1): пряме обчислення адреси

struct Node
{
    int data;
    Node* next;  // Покажчик на наступний вузол
};

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = new Node{30, nullptr};

struct Node
{
    int data;      // Корисне навантаження (payload)
    Node* next;    // Адреса наступного вузла (або nullptr)
};

// Створення окремого вузла
Node* firstNode = new Node;
firstNode->data = 10;
firstNode->next = nullptr;

// Або через uniform initialization (C++11)
Node* secondNode = new Node{20, nullptr};

// Або через designated initializers (C++20)
Node* thirdNode = new Node{.data = 30, .next = nullptr};

// LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>

// Структура вузла (вкладена в клас для інкапсуляції)
struct Node
{
    int data;
    Node* next;
    
    // Конструктор для зручності
    Node(int value, Node* nextNode = nullptr)
        : data(value), next(nextNode)
    {
    }
};

class LinkedList
{
private:
    Node* head;  // Покажчик на перший вузол (nullptr для порожнього списку)

public:
    // Конструктор: створює порожній список
    LinkedList();
    
    // Деструктор: видаляє всі вузли (RAII)
    ~LinkedList();
    
    // Заборона копіювання (для простоти)
    LinkedList(const LinkedList&) = delete;
    LinkedList& operator=(const LinkedList&) = delete;
    
    // Перевірити, чи список порожній
    bool isEmpty() const;
    
    // Отримати кількість елементів (O(n) — потребує обходу)
    int size() const;
    
    // Вставити елемент на початок (O(1))
    void insertFront(int value);
    
    // Вставити елемент в кінець (O(n) без tail-покажчика)
    void insertBack(int value);
    
    // Видалити перший вузол (O(1))
    void deleteFront();
    
    // Видалити перше входження значення (O(n))
    void deleteValue(int value);
    
    // Пошук елемента (O(n))
    bool search(int value) const;
    
    // Вивести всі елементи
    void display() const;
    
    // Обернути список (змінити напрямок покажчиків)
    void reverse();
    
    // Очистити список (видалити всі вузли)
    void clear();
};

#endif

// LinkedList.cpp
#include "LinkedList.h"

// Конструктор: ініціалізує порожній список
LinkedList::LinkedList()
    : head(nullptr)  // Голова вказує на nullptr — список порожній
{
}

// Деструктор: видаляє всі вузли (ідіома RAII)
LinkedList::~LinkedList()
{
    clear();  // Делегуємо логіку очищення методу clear()
}

// Перевірити, чи список порожній
bool LinkedList::isEmpty() const
{
    return head == nullptr;
}

// Отримати кількість елементів
int LinkedList::size() const
{
    int count = 0;
    Node* current = head;
    
    // Обходимо список, рахуючи вузли
    while (current != nullptr)
    {
        ++count;
        current = current->next;
    }
    
    return count;
}

// Очистити список (видалити всі вузли)
void LinkedList::clear()
{
    Node* current = head;
    
    while (current != nullptr)
    {
        Node* nextNode = current->next;  // Зберігаємо адресу наступного
        delete current;                  // Видаляємо поточний
        current = nextNode;              // Переходимо до наступного
    }
    
    head = nullptr;  // Список тепер порожній
}

void LinkedList::insertFront(int value)
{
    // Створюємо новий вузол, його next вказує на поточну голову
    Node* newNode = new Node(value, head);
    
    // Оновлюємо голову — тепер це новий вузол
    head = newNode;
    
    // Складність: O(1) — три операції, незалежно від розміру списку
}

void LinkedList::insertBack(int value)
{
    Node* newNode = new Node(value, nullptr);
    
    // Якщо список порожній — новий вузол стає головою
    if (head == nullptr)
    {
        head = newNode;
        return;
    }
    
    // Інакше — знаходимо останній вузол (той, чий next == nullptr)
    Node* current = head;
    while (current->next != nullptr)
    {
        current = current->next;
    }
    
    // current тепер вказує на останній вузол
    current->next = newNode;
    
    // Складність: O(n) — обхід від голови до кінця
}

void LinkedList::deleteFront()
{
    // Передумова: список не повинен бути порожнім
    if (isEmpty())
    {
        std::cerr << "Помилка: спроба видалення з порожнього списку\n";
        return;  // Або throw std::out_of_range
    }
    
    // Зберігаємо адресу другого вузла
    Node* temp = head->next;
    
    // Видаляємо перший вузол
    delete head;
    
    // Оновлюємо голову
    head = temp;
    
    // Складність: O(1)
}

void LinkedList::deleteValue(int value)
{
    // Особливий випадок: видаляється голова
    if (head != nullptr && head->data == value)
    {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    
    // Загальний випадок: шукаємо вузол з value, зберігаючи попередній
    Node* current = head;
    Node* previous = nullptr;
    
    while (current != nullptr && current->data != value)
    {
        previous = current;
        current = current->next;
    }
    
    // Якщо current == nullptr — значення не знайдено
    if (current == nullptr)
    {
        std::cerr << "Значення " << value << " не знайдено у списку\n";
        return;
    }
    
    // Знайдено: previous -> current -> current->next
    // Перемикаємо: previous -> current->next
    previous->next = current->next;
    delete current;
    
    // Складність: O(n) — у гіршому випадку обходимо весь список
}

bool LinkedList::search(int value) const
{
    Node* current = head;
    
    // Обходимо список до знаходження value або кінця
    while (current != nullptr)
    {
        if (current->data == value)
        {
            return true;  // Знайдено
        }
        current = current->next;
    }
    
    return false;  // Не знайдено
}

void LinkedList::display() const
{
    if (isEmpty())
    {
        std::cout << "Список порожній\n";
        return;
    }
    
    Node* current = head;
    std::cout << "Список: ";
    
    while (current != nullptr)
    {
        std::cout << current->data;
        if (current->next != nullptr)
        {
            std::cout << " → ";  // Стрілка для візуалізації зв'язків
        }
        current = current->next;
    }
    
    std::cout << " → nullptr\n";
}

void LinkedList::reverse()
{
    Node* previous = nullptr;
    Node* current = head;
    Node* next = nullptr;
    
    while (current != nullptr)
    {
        // Зберігаємо наступний вузол
        next = current->next;
        
        // Обертаємо зв'язок поточного вузла
        current->next = previous;
        
        // Зміщуємо покажчики на наступну ітерацію
        previous = current;
        current = next;
    }
    
    // previous тепер вказує на новий перший вузол (колишній останній)
    head = previous;
    
    // Складність: O(n) — один прохід по списку
}

#include "LinkedList.h"
#include <iostream>

int main()
{
    LinkedList list;
    
    std::cout << "=== Демонстрація однозв'язаного списку ===\n\n";
    
    // Вставка елементів
    std::cout << "Вставка елементів: 10, 20, 30 на початок\n";
    list.insertFront(30);
    list.insertFront(20);
    list.insertFront(10);
    list.display();  // Виведе: 10 → 20 → 30 → nullptr
    
    std::cout << "\nВставка 40 в кінець\n";
    list.insertBack(40);
    list.display();  // Виведе: 10 → 20 → 30 → 40 → nullptr
    
    // Пошук
    std::cout << "\nПошук елемента 20: " 
              << (list.search(20) ? "знайдено" : "не знайдено") << '\n';
    std::cout << "Пошук елемента 99: " 
              << (list.search(99) ? "знайдено" : "не знайдено") << '\n';
    
    // Розмір
    std::cout << "\nРозмір списку: " << list.size() << '\n';
    
    // Видалення
    std::cout << "\nВидалення першого елемента\n";
    list.deleteFront();
    list.display();  // Виведе: 20 → 30 → 40 → nullptr
    
    std::cout << "\nВидалення елемента зі значенням 30\n";
    list.deleteValue(30);
    list.display();  // Виведе: 20 → 40 → nullptr
    
    // Обернення
    std::cout << "\nОбернення списку\n";
    list.reverse();
    list.display();  // Виведе: 40 → 20 → nullptr
    
    // Очищення
    std::cout << "\nОчищення списку\n";
    list.clear();
    list.display();  // Виведе: Список порожній
    
    return 0;
}

template<typename T>
struct Node
{
    T data;          // Замість int data
    Node<T>* next;
};

for (auto it = list.begin(); it != list.end(); ++it)
{
    std::cout << *it << '\n';
}

// Або range-based for (стаття 23)
for (int value : list)
{
    std::cout << value << '\n';
}

struct DoublyNode
{
    int data;
    DoublyNode* next;
    DoublyNode* prev;  // Покажчик на попередній вузол
};

void deleteFront()
{
    delete head;         // Видалили перший вузол
    head = head->next;   // ❌ UB: доступ до звільненої пам'яті!
}

void deleteFront()
{
    Node* temp = head->next;  // Спершу зберігаємо next
    delete head;
    head = temp;              // Тепер безпечно оновлюємо head
}

Node* newNode = new Node{42};  // next не ініціалізовано!
lastNode->next = newNode;       // Висячий покажчик у newNode->next

Node* newNode = new Node{42, nullptr};  // Явно встановлюємо nullptr

~LinkedList()
{
    delete head;  // Видаляє лише перший вузол, решта — витік!
}

~LinkedList()
{
    Node* current = head;
    while (current != nullptr)
    {
        Node* next = current->next;
        delete current;
        current = next;
    }
}

void display()
{
    while (head != nullptr)
    {
        std::cout << head->data << " ";
        head = head->next;  // ❌ Втрачаємо голову назавжди!
    }
}

void display()
{
    Node* current = head;  // Тимчасова змінна для обходу
    while (current != nullptr)
    {
        std::cout << current->data << " ";
        current = current->next;
    }
}