Односвязные списки как замена массивам.

Madcape · 3 Ноя 2019

Старику Похабычу благодарность. Не так давно он меня натолкнул на одну уже совершенно известную и старую методу решения проблем с массивами. Собственно с массивами проблем то нет, только вот они сами просто ну сильно проблемные... а так у них проблем у самих нет )))

В общем, в С++ массивы - это то что нужно растоптать и выкинуть ))) ибо ну не возможно с ними работать - большой массив становится камнем в горле мелкого микроконтроллера, типа на тех что построены ардуинки. Да и не удобно с ними просто.

На тытрубе нашел одного автора, который пояснил что к чему и показал как.
Согласно его инфе сделал тоже себе библиотечку по работе с односвязными списками, немного дополнил - теперь есть возможность в массив заталкивать любые объекты, в том числе и экземпляры собственноручно созданных классов, не говоря уже о стандартных типах как "struct".

Из особенностей:
- умеет возвращать элементы по произвольному условию (функция getBy(<указатель_на_функцию_выборки( <ваш_тип> * data)) - где data - это объект, который вы ранее засунули в список )) / Пример: получить элемент, для которого его поле code == 1020304 / ;
- работа с курсором (внутри ведется курсор, и соответственно его можно двигать вверх/вниз и получать элемент по этому курсоры - удобно, если список используется для построения меню интерфейсов);
- для своих нужд внедрил еще поле parentList (вполне можно убрать, кому не нужно).

C++:

#pragma once
#include <Arduino.h>
// /*
//  * Односвязный список указателей на объекты пользовательских классов
//  */

template <typename T>
class List
{
public:
    List();
    ~List();

    List<T> * parentList;
    char * name;
    byte * level;
    int8_t cursor = 0; // значение курсора

    void init(char * name, byte level = 0, List<T> * parentList = nullptr){
        this->name = name;
        this->level = level;
        this->parentList = parentList;
    }
   
    bool dataAsObject=true; // флаг, что данными будут объекты

    T* push_back (T *data); // функция вставки нового элемента в конец списка
    void push_front(T *data); // вставка в начало списка
    void insert(T *data, int index);
    T * removeAt(int index, bool toOut = false);
    //void pop_front(  void(*func_t)(T)  );
    T * pop_front(bool toOut = false );
    T * pop_back(bool toOut = false);
    void clear();
   

    int length(){return Size;} // возвращает длину

    T* get(const int index);

    T* getBy(volatile bool (*pFunc)(T * data) ) { // возвращает элемент списка согласно функции выборки pFunc
        int counter = 0;
        int s = this->Size;
        Node<T> *current = this->head;
        while (counter < s)  {
            if (  pFunc(current->data)  ) {
                return current->data;
            } else {
                current = current->pNext; // pNext здесь УКАЗАТЕЛЬ
                counter++;
            }
        }
        return nullptr;
             
    };
    T& operator[](const int index);

    T * cursorChange(int8_t direct){
        if (cursor==0 && direct < 0){
            cursor = 0;
        } else {
            cursor = cursor + direct;
        }
       
        if (cursor > Size -1) cursor = Size - 1;
        if (cursor < 0) cursor = 0;
        return getCursorItem();
    }
    T* getNextItem(){
        cursorChange(1);
    }
     T* getPrevItem(){
        cursorChange(-1);
    }
   
    T* getCursorItem(){
        return this->get(this->cursor);
    }
    List<T> * parent(){
        return this->parentList;
    }
   
private:
    int Size;
   
    // внутренний класс. Узел
    template <typename U> ////// ??????????????? U а не Т - тогла компилится
    class Node
    {
    public:
        Node *pNext;
        T *data; // УКАЗАТЕЛЬ на объект

        Node (T *data = T(), Node *pNext = nullptr){ // принимает УКАЗАТЕЛЬ на сторонний объект другого класса!
            this->data = data;
            this->pNext = pNext;
        };
        ~Node(){
            //Serial << "Вызвался дестркутор объекта класса Node" << endl;
        }
    };
   
    Node<T> *head; // головной элемент
};

// // конструктор
template <typename T>
List<T>::List()
{
    Size = 0;
    head = nullptr;
    parentList = nullptr;
}

// // деструктор
template <typename T>
List<T>::~List()
{
    //Serial << "Вызвался дестркутор объекта класса List" << endl;
    clear();
}

// перегрузка квадратных скобок - будем получать значение i-ого элемента
template <typename T>
T & List<T>::operator[](const int index)
{
    return this->get(index);
}

template <typename T>
T * List<T>::get(const int index) // получить указатель на элемент по его индексу
{  
    // проверка на допустимость величины индекса
    if (index > this->Size - 1 ) return nullptr;
    int counter = 0;
    Node<T> *current = this->head; // создаем временный указатель здесь сущесвующий head это объект класс Node

    int s = this->Size;
    while (counter < s){ // крутиться пока счетчик меньше размера списка

        if (counter == index){
            return (current->data);
        } else {
            current = current->pNext; // pNext здесь УКАЗАТЕЛЬ
            counter++;
        }      
    }
};



template <typename T>
T* List<T>::push_back(T *data){ // вставка в конец списка

    if(head == nullptr){
        head = new Node<T>(data);
    } else {
        Node<T> *current = this->head;
        while (current->pNext != nullptr)
        {
            current = current->pNext;
        }
        current->pNext = new Node<T>(data);
    }
    Size++;
    return data;
};


template <typename T>
void List<T>::push_front(T *data){ // добавить в начало списка
    head = new Node<T>(data, head);
    Size++;
}

template <typename T>
void List<T>::insert(T *data, int index){ // добавить в списка согласно индекса
    if(index == 0){
        push_front(data);
    } else {
        Node<T> *prev = this->head;
        for (int i = 0; i < index - 1; i++)
        {
            prev = prev->pNext;
        }
        Node<T> *newNode = new Node<T>(data, prev->pNext);
        prev->pNext = newNode;

    }
    Size++;  
}


template <typename T>
T * List<T>::pop_front(bool toOut){ // удаление первого элемента
   
    Node<T> *temp = head; // head тут у нас не объект (!), а УКАЗАТЕЛЬ на УЗЕЛ, у которого поле data - это тоже указатель на другой объект другого класса
    T *data = head->data; // указатель на объект data (ведь дата у нас не просто данные, а УКАЗАТЕЛЬ на объект, и этот объект тоже надо удолять из ОЗУ)
   
    head = head->pNext;

    Size--;
    if (toOut){
       
        return data;      
    }
    delete data;
    delete temp; // очистка ОЗУ от объекта data класса <T>  
    return nullptr;
};


template <typename T>
void List<T>::clear(){ // очистка всего списка
    int s = this->Size;
    while(s){
        pop_front(false); // удалить без возвращения удаляемого элемента
    }
}


template <typename T>
T * List<T>::removeAt(int index, bool toOut){ // // удалить по индексу. toOut - если True, то не удаляется из ОЗУ, а возвращается из запроса
    if(index == 0){
        pop_front(toOut);
    } else {
        Node<T> *prev = this->head;
        for (int i = 0; i < index - 1; i++)
        {
            prev = prev->pNext;
        }
        Node<T> *toDelete = prev->pNext;
        prev->pNext = toDelete->pNext;

        Size--;

        if (toOut){
            T * answer = toDelete->data; // указатель на данные
           
            if (dataAsObject) { // удалить просто узел
                delete toDelete;
            }
            return answer;  // вернуть указатель на данные
        } else {
            // удалить из ОЗУ объект data по его указателю в узле toDelete
            if (dataAsObject){  delete toDelete->data; }          
            delete toDelete;    // удалить из ОЗУ просто узел
            return nullptr;
        }
    }    
}
template <typename T>
T * List<T>::pop_back(bool toOut){ // удалить последний элемент
    return removeAt(Size-1, toOut);
}

Поиск

Поиск

Односвязные списки как замена массивам.

Madcape

✩✩✩✩✩✩✩