C++ Linear List example

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

using namespace std;

/*------------------------------------------------------------------- ЛИНЕЙНЫЙ СПИСОК ---------------------------------------------------------------*/

/*
Тип данных для однонаправленного списка целых чисел LinearList
@data - значение целого числа в элементе списка
@next - указатель на следующий элемент списка (nullptr, если это последний элемент)
*/
struct LinearList
{
    int data;                       // поле данных
    struct LinearList* next;        // указатель на следующий элемент
};



/*
Операции над однонаправленным линейным списком LinearList -----------------------
В качестве одного из аргументов передается LinearList**, т.е. указатель на указатель на наш тип данных - вроде как (LinearList*)*,
это необходимо для того, чтобы в наших функциях можно было менять исходный список.
Поскольку память под элементы списка выделяется динамически (new), мы оперируем указателями на эти области памяти (LinearList*).
Чтобы менять исходные данные, нам нужно передавать их в функцию по адресу (&), иначе будут меняться копии данных, создаваемые функцией
Чтобы получить адрес указателя нам нужно использовать в качестве типа данных указатель на этот указатель... отсюда страшный LinearList**
Далее в коде мы просто создадим наш список как указатель на первый элемент (LinearList* list) и будем передавать в функции адрес этого списка (func(&list)),
чтобы функции работали с исходным списком, а не с копиями.
В качестве альтернативного решения нам потребовалось бы возвращать в функциях значения ссылок на обновленный список и обновлять list результатами их выполнения (list = func(list))
*/

// Создание линейного списка root и инициализация его значениями на основе массива values длины length
void createLinearList(LinearList** root, int* values, const int length)
{
    if (length > 0)                             // есть смысл инициализировать список толькое если передаваемая длина массива length ненулевая
    {
        *root = new LinearList;                 // разыменованием получаем указатель на тип LinearList (т.е. LinearList*), который нужен для динамического выделения памяти (new)
        (*root)->data = values[0];              // инициализируем только что созданный элемент, указывая первый элемент массива в качестве параметра @data
        (*root)->next = nullptr;                //...и пустой указатель (nullptr aka NULL) в качестве параметра @next. Т.е. по факту у нас сейчас список из одного элемента.

        if (length > 1)                         // если длина передаваемого массива length всё же больше 1 элемента, можем дополнить список оставшимися в массиве значениями
        {
            LinearList* e = *root;              // создаем временную переменную e для движения по списку от положения root
            for (int i = 1; i < length; i++)    // в цикле по остатку массива values...
            {
                e->next = new LinearList;       // для каждого обрабатываемого элемента массива добавляем в конец списка новый элемент
                e = e->next;                    // сдвигаем указатель (временную переменную) на новый элемент
                e->data = values[i];            // инициализируем этот элемент по аналогии с первым, но по порядку членов массива
                e->next = nullptr;              // последний элемент всегда будет указывать на пустой указатель nullptr (aka NULL)
            }
        }
    }
}

// Последовательный вывод содержимого линейного списка root (здесь нам не надо менять исходный список, поэтому можно обойтись простым указателем на первый элемент списка LinearList*)
void printLinearList(LinearList* root)
{
    cout << endl << "Линейный однонаправленный список:" << endl;
    LinearList* e = root;                       // создаем временную переменную e для движения по списку от положения root
    while (e != nullptr)                        // пока не достигнут конец списка, т.е. пока временная переменная e не приняла значение равное пустому указателю nullptr
    {
        cout << "[" << e->data << "] -> ";      // выводим данные из узла списка @data
        e = e->next;                            // ...и переходим к следующему узлу, сдвигая временный указатель e дальше по списку.
    }
    cout << "NULL" << endl;                     // конец списка у нас всегда указывает на nullptr (NULL)
}

// Добавление нового элемента линейного списка со значением @data = value ПЕРЕД указанным element
void addLinearListElementBefore(LinearList** element, const int value)
{
    LinearList* e = new LinearList;             // Создаем новый узел
    e->data = value;                            // инициализируем его данные @data переданным в функцию значением value
    e->next = *element;                         // в качестве следующего элемента передаем исходный список (исходный список продолжает наш новый элемент)
    *element = e;                               // ...а сам новый элемент становится новым началом списка
}

// Добавление нового элемента линейного списка со значением @data = value ПОСЛЕ указанного element
void addLinearListElementAfter(LinearList** element, const int value)
{
    LinearList* tmp = new LinearList;           // Создаем новый узел
    tmp->data = value;                          // инициализируем его данные @data переданным в функцию значением value

    LinearList* e = (*element)->next;           // создаем временный узел для обмена ссылками и записываем в него указатель на элемент, следующий за переданным в функцию узлом element
    (*element)->next = tmp;                     // вместо сохраненного следующего подставляем только что созданный узел tmp
    tmp->next = e;                              // а сам tmp будет ссылаться на сохраненный ранее узел, который теперь смещается дальше по списку (element -> tmp -> e -> ...)
}

// Добавление нового элемента со значением @data = value в начало списка root
void addLinearListElementHead(LinearList** root, const int value)
{
    addLinearListElementBefore(&(*root), value); // по сути это функция обертка - мы добавляем новый элемент перед элементом root (ссылкой на первый элемент списка)
}

// Добавление нового элемента со значением @data = value в конец списка root
void addLinearListElementEnd(LinearList** root, int value)
{
    LinearList* e = *root;                      // создаем временную переменную e для движения по списку от положения root

    while (e->next != nullptr)                  // движемся по списку от узла к узлу пока на достигнем последнего узла (у которого ссылка на следующий элемент будет NULL)
    {
        e = e->next;                            // переход к следующему узлу...
    }
    addLinearListElementAfter(&e, value);       // добавляем новый элемент ПОСЛЕ последнего найденного узла e (последний узел списка) через описанную ранее функцию
}

// Удаление из списка root элемента element (при совпадении адреса ссылки на element с одним из элементов списка root)
void removeLinearListElement(LinearList** root, LinearList* element)
{
    if (*root == nullptr) return;               // если список и так пуст, удалять особо нечего, поэтому просто уходим отсюда

    LinearList* a = *root;                      // создаем временную переменную a для движения по списку от положения root
    if (a == element)                           // если совпадение пришлось на первый же элемент списка - это особый случай...
    {
        *root = a->next;                        // смещаем указатель на начало массива дальше (там вполне может оказаться NULL - ничего страшного)
        delete a;                               // чистим память по указанному адресу a
        return;                                 // и прекращаем дальнейший обход
    }

    a = *root;                                  // Если с первым элементом не прокатило, то начинаем обход списка с начала, запоминаем a, после которого возможно будет удален элемент b
    LinearList* b = (*root)->next;              // создаем указатель b на следующий элемент - удалять найденный элемент будем по этому же указателю
    while (b != nullptr)                        // пока мы не достигли конца списка (a - последний элемент, следующий за ним b - пустой)
    {
        if (b == element)                       // проверяем, нужно ли удалять следующий элемент (по совпадению адресов памяти)
        {
            a->next = b->next;                  // если да - записываем в следующий за a узел значение узла, следующего за b (как бы исключем b из нашего списка)
            delete b;                           // и очищаем выделенную под удаленный узел память с последующим выходом...
            return;
        }
        a = b;                                  // ...если совпадения нет - смещаем наши указатели a и b дальше по списку
        b = b->next;
    }
}

// Удаление первого элемента списка root (смещение корневой ссылки дальше по списку)
void removeLinearListHead(LinearList** root)
{
    removeLinearListElement(&(*root), *root);   // передаем в описанную ранее функцию список root (по адресу) и адрес указателя на первый элемент (т.е. то, что будем удалять)
}

// Удаление последнего элемента списка root
void removeLinearListEnd(LinearList** root)
{
    LinearList* a = *root;
    LinearList* b = (*root)->next;

    if (b == nullptr)                           // если в списке только один элемент, сносим его нашей функцией (через указатель на первый элемент)
    {
        removeLinearListElement(&(*root), *root);
        return;
    }

    while (b->next != nullptr)                  // иначе движемся по списку по аналогии с предыдущей функцией до самого конца (a - предпоследний элемент, b - последний)
    {
        a = b;
        b = b->next;
    }

    delete b;                                   // удаляем последний элемент b
    a->next = nullptr;                          // перезаписываем у предпоследнего узла a ссылку на следующий элемент, чтобы она указывала не на удаленный b, а на пустой указатель NULL
}

// Очищаем список от элементов
void clearLinearList(LinearList** root)
{
    while (*root != nullptr)                    // пока список не опустеет
    {
        removeLinearListHead(&(*root));         // удаляем элемент из начала и смещаем список дальше.
    }
}



//-------------------------------------------------------------------------------//
// Задача 1 лабораторной (по варианту 1)
//-------------------------------------------------------------------------------//
void operateLinearList(LinearList* root)
{
    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Определение среднего арифметического значения элементов списка, кратных 4: " << endl;
    cout << "------------------------------------------------------" << endl;

    int num = 0;                                // количество найденных элементов кратных 4
    int sum = 0;                                // сумма найденных элементов кратных 4
    LinearList* e = root;                       // создаем временную переменную e для движения по списку от положения root

    cout << "Числа кратные 4:" << endl;
    while (e != nullptr)                        // пока не дошли до конца списка
    {
        if (e->data % 4 == 0)                   // проверяем кратность значения, хранящегося в @data текущего узла е
        {
            cout << e->data << endl;
            sum += e->data;                     // если значение кратно 4, плюсуем его к сумме sum
            num++;                              // и увеличиваем число найденных элементов num на 1
        }
        e = e->next;                            // переходим к следующему доступному элементу по указателю @next
    }

    if (num > 0)                                // если в результате обхода списка что-то нашлось, значит можно посчитать среднее арифметическое всех найденных элементов
    {
        cout << "Среднее арифметическое = " << (float)sum / num << endl;
    }
    else                                        // иначе считать особо нечего, не делить же 0 на 0...
    {
        cout << "Чисел удовлетворяющим условиям задачи в списке не найдено" << endl;
    }
}



int main()
{
    setlocale(LC_ALL, "Russian");

    const int default_length = 5;                               // длина инициализационного массива
    int default_data[default_length] = { 4, 7, 13, 17, 44 };    // инициализационный массив значений для инициализации структур

    LinearList* list = nullptr;                 // переменная для хранения указателя на линейный однонаправленный список

    cout << "------------------------------------------------------" << endl;
    cout << " Создание линейного однонаправленного списка: " << endl;
    cout << "------------------------------------------------------" << endl;
    createLinearList(&list, default_data, default_length);
    printLinearList(list);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Добавление элемента в конец списка: " << endl;
    cout << "------------------------------------------------------" << endl;

    int ListData = 0;
    cout << "Введите целое число: ";
    cin >> ListData;                            // записываем введенное число в переменную
    addLinearListElementEnd(&list, ListData);
    printLinearList(list);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Добавление элемента в начало списка: " << endl;
    cout << "------------------------------------------------------" << endl;

    cout << "Введите целое число: ";
    cin >> ListData;                            // записываем введенное число в переменную
    addLinearListElementHead(&list, ListData);
    printLinearList(list);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Удаление первого элемента списка: " << endl;
    cout << "------------------------------------------------------" << endl;
    removeLinearListHead(&list);
    printLinearList(list);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " Удаление последнего элемента списка: " << endl;
    cout << "------------------------------------------------------" << endl;
    removeLinearListEnd(&list);
    printLinearList(list);

    // задание лабораторной по варианту 1
    operateLinearList(list);

    cout << endl;
    cout << "------------------------------------------------------" << endl;
    cout << " УДАЛЕНИЕ всего списка: " << endl;
    cout << "------------------------------------------------------" << endl;

    clearLinearList(&list);
    printLinearList(list);

    return 0;
}