linked_list_issue.cpp

#include <initializer_list>
#include <iostream>
#include <memory>

// -fsanitize=address -stdlib=libc++ -g -O0 -pedantic -fstack-protector -D_GLIBCXX_DEBUG_PEDANTIC -D_GLIBCXX_DEBUG -fsanitize=undefined -Wall -Werror -std=c++20

template<class T>
struct Node {
    T data {};
    std::shared_ptr<Node> prev = {nullptr};
    std::shared_ptr<Node> next = {nullptr};

    Node(const T& data) : data{data} {
    }
};

template<class T>
struct List {
    using Item = Node<T>;
    using ItemPtr = std::shared_ptr<Item>;

    ItemPtr head {nullptr};
    ItemPtr tail {nullptr};

     List() {
         head = std::make_shared<Item>(T());
         tail = std::make_shared<Item>(T());
         head->next = tail;
         tail->prev = head;
    }

    List(const std::initializer_list<T>& items) : List() {
        for (const auto& item : items) {
            PushBack(item);
        }
    }

    void PushFront(const T& data) {
        auto node = std::make_shared<Item>(data);
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void PushBack(const T& data) {
        auto node = std::make_shared<Item>(data);
        node->prev = tail->prev;
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }

    void Remove(ItemPtr node) {
        if (!node) return;
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void MoveToFront(ItemPtr node) {
        if (!node) return;
        Remove(node);
        PushFront(node->data);
    }

    void MoveToBack(ItemPtr node) {
        if (!node) return;
        Remove(node);
        PushBack(node->data);
    }

    ItemPtr Back() {
        if (head->next == tail) return {};
        return tail->prev;
    }

    ItemPtr Front() {
        if (head->next == tail) return {};
        return head->next;
    }

    ItemPtr Search(const T& target) {
        auto current = head->next;
        while (current != tail) {
            if (current->data == target) {
                return current;
            }
            current = current->next;
        }
        return {};
    }

    void Reverse() {
        auto i = head->next;
        auto j = tail->prev;
        while (i != tail && j != head && i != j && i->prev != j) {
            std::swap(i->data, j->data);
            i = i->next;
            j = j->prev;
        }
    }

    bool IsEmpty() {
        return head->next == tail;
    }

    void Print() {
        std::cout << "List(";
        ItemPtr current = head->next;
        while (current != tail) {
            if (current != head->next) {
                std::cout << " ";
            }
            std::cout << current->data;
            current = current->next;
        }
        std::cout << ")" << std::endl;
    }
};

int main() {
    auto list = List({1,2,3});
    list.Print();

    list.PushBack(4);
    list.Print();

    list.PushFront(0);
    list.Print();

    list.MoveToBack(list.Front());
    list.Print();

    std::cout << list.Back()->data << std::endl;

    list.MoveToFront(list.Back());
    list.Print();

    auto node = list.Search(2);
    if (node) {
        std::cout << "Node data: " << node->data << std::endl;
        list.Remove(node);
        list.Print();
    }

    list.Reverse();
    list.Print();

    while (!list.IsEmpty()) {
        list.Remove(list.Front());
    }
    list.Print();

    list.PushFront(0);
    list.Print();

    std::cout << "OK" << std::endl;
}