Программа для реализации односвязного списка на C++ с использованием класса

Опубликовано: 24 Сентября, 2022

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

В C++ связанный список может быть представлен отдельно классом и классом узла , который имеет два члена, а именно данные и указатель next , указывающий на следующий узел.

InsertNode : в этой статье вставка выполняется в конец списка. Следуйте инструкциям, чтобы вставить узел в связанный список.

  • Скажем, 4 нужно вставить в существующий связанный список, т. е. 1 -> 2 -> 3. Результирующий связанный список будет 1 -> 2 -> 3 -> 4.
  • Чтобы вставить новый узел, пройдите до конца списка, пока не будет найден узел NULL.
  • Создайте новый узел и свяжите новый узел с последним узлом связанного списка.

DeleteNode : в этой статье удаление выполняется с использованием индекса узла. Выполните шаги, чтобы удалить узел:

  • Если удаляемый узел является головным узлом, сохраните головку в переменной temp . Затем обновите head как head->next . Удалить темп .
  • Если индекс удаляемого узла больше длины списка, то возврат из функции.
  • Пройдите до узла, который нужно удалить. Удалите узел и свяжите предыдущий узел со следующим узлом удаленного узла.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)