Связные списки

Тема: Связные списки

Linked lists (связные списки)

Распишите код для следующих структур данных.

Можете выделять память динамически в heap используя new или malloc, отдельно для каждого нода. Можете пользоваться примерами.

Можете использовать template<typename T>.

1. Singly linked list (односвязный список):

   • Структура должна иметь поля под указатели на первый и последний нод списка;

   • Node* insertAfter(LinkedList* list, Node* node, int value) создает новый нод и добавляет его после данного нода. В случае если node == nullptr, нод добавляется в начало списка. Возвращает указатель на созданный нод;

   • FindNodeResult find(LinkedList* list, int value) ищет нод до нода с заданным значением в списке; Возвращает нод с этим значением, а также нод до него. FindNodeResult определите сами.

     Если используете template, можете добавить еще один параметр и передавать функтор поиска;

   • void removeAfter(LinkedList* list, Node* node) удаляет нод следующий данному ноду из списка. В случае если node == nullptr, удаляется первый нод списка;

   • void assertNoCycles(LinkedList* list), который проверяет, чтобы в списке не было циклов. Используйте эту функцию для проверки логики, можете делать assert в других функциях что это условие выполняется (называется contract). Этот метод довольно сложно реализовать без дополнительной информации в структуре, поэтому рекомендую также хранить текущее количество нодов в списке в LinkedList структуре. В этой функции просто пытайтесть посчитать длину заного, и если она становится больше реальной длины, у вас где-то цикл.

2. Doubly linked list (двусвязный список):

   • Структура должна иметь поля под указатели на первый и последний нод списка;

   • Node* insertAfter(LinkedList* list, Node* node, int value);

   • Node* insertBefore(LinkedList* list, Node* node, int value);

   • Node* find(LinkedList* list, int value) ищет нод с данным значением в списке (применяются заметки для find выше);

   • void remove(LinkedList* list, Node* node) удаляет нод из списка;

   • void assertNoCycles(LinkedList* list). Тут подойдет либо подход с длиной, либо можете сделать это путем проверки взаимосвязей во всех нодах, и проверки концов, поскольку из одного нода может отходить максимум 2 связи.

Распишите функции теста для каждой из функций, вызывайте их в main.