Помоги мне, пожалуйста, добавить метод вставки в конец в мой класс: template <typename…
- User
Помоги мне, пожалуйста, добавить метод вставки в конец в мой класс: template struct DL_node { T value; std::shared_ptr<DL_node> prev; std::shared_ptr<DL_node> next;
DL_node(T data) : value(data), prev(nullptr), next(nullptr) {}};
template class PersistentDoublyLinkedList { private: std::vector<std::shared_ptr<DL_node>> versions; // Храним версии головы списка //std::unordered_map<T, std::shared_ptr<DL_node>> node_map; // Для хранения уже созданных узлов
int current_version;public: // Конструктор, который принимает массив и его размер PersistentDoublyLinkedList(T* arr, int size) { if (size <= 0) { return; // Если массив пуст, просто возвращаем }
// Создаем голову списка auto head = std::make_shared<DL_node<T>>(arr[0]); std::shared_ptr<DL_node<T>> current = head; // Храним указатель на текущий узел // Сохраняем первый узел в мапе //node_map[arr[0]] = head; // Проходим по массиву и создаем двусвязный список for (int i = 1; i < size; ++i) { auto new_node = std::make_shared<DL_node<T>>(arr[i]); current->next = new_node; // Присоединяем новый узел к текущему new_node->prev = current; // Устанавливаем ссылку на предыдущий узел current = new_node; // Переходим к новому узлу // Сохраняем узел в мапе //node_map[arr[i]] = new_node; } // Сохраняем голову списка в вектор версий versions.push_back(head); current_version = 0; } // Метод для добавления нового узла в голову списка void push_front(T value) { auto new_head = std::make_shared<DL_node<T>>(value); new_head->next = versions.back(); // Новый узел указывает на текущую голову // Обновляем указатель на предыдущий узел новой головы, если он существует if (versions.back() != nullptr) { versions.back()->prev = new_head; } // Сохраняем новую версию (голову) списка versions.push_back(new_head); current_version++; } // Метод для печати всех версий списка без использования PrintList void printAllVersions() { for (int i = 0; i < versions.size(); ++i) { std::cout << "Version " << i << ": "; auto current = versions[i]; // Проходим по всем узлам текущей версии и выводим их значения while (current) { std::cout << current->value << " (" << &(current->value) << ") "; current = current->next; } std::cout << std::endl; // Переход на новую строку после печати одной версии } } - Assistant
Чтобы добавить метод вставки в конец списка (
push_back) в ваш классPersistentDoublyLinkedList, вам нужно будет создать новый узел, который будет указывать на текущий "хвост" списка, и обновить связи между узлами. Также после добавления нового узла вы будете создавать новую версию списка.Вот как можно реализовать метод
push_back:// Метод для добавления нового узла в конец списка void push_back(T value) { auto new_node = std::make_shared<DL_node<T>>(value); // Если это первая версия списка, то новый узел станет головой if (versions.empty()) { versions.push_back(new_node); current_version = 0; return; } auto last = versions.back(); // Получаем текущую версию (голову) // Находим последний узел (хвост) в текущей версии while (last->next) { last = last->next; } last->next = new_node; // Присоединяем новый узел к хвосту new_node->prev = last; // Устанавливаем ссылку на предыдущий узел // Сохраняем новую версию (голову) списка versions.push_back(versions.back()); current_version++; }Объяснение работы метода
push_back:-
Создание нового узла: Мы создаем новый узел с переданным значением, используя
std::make_shared<DL_node<T>>(value). -
Проверка на пустоту списка: Если вектор
versionsпуст, то это означает, что список еще не содержит никаких узлов. В этом случае новый узел становится первым и единственным узлом, и мы добавляем его вversions. -
Нахождение хвоста текущей версии: Если вектор
versionsне пуст, мы берем последнюю (текущую) версию списка. Затем проходим по узлам до тех пор, пока не найдем последний узел (узел, у которогоnextуказывает наnullptr). -
Присоединение нового узла: Мы устанавливаем связь между новым узлом и текущим хвостом списка. У нового узла мы устанавливаем указатель на предыдущий узел.
-
Сохранение новой версии: Мы сохраняем новую версию списка, которая всё еще ссылается на голову. Таким образом, все предыдущие версии остаются неизменными.
После добавления этого метода, вы сможете добавлять элементы в конец списка, сохраняя все предыдущие версии.
-