Программа для реализации односвязного списка на C++ с использованием класса
Связанный список хранит данные в последовательном хранилище, подобно массивам. Хотя данные хранятся последовательно, ячейки памяти не являются смежными.
В отличие от массива, связанный список может хранить данные разных типов.
На приведенной ниже диаграмме представлена структура связанного списка.
В C++ связанный список может быть представлен отдельно классом и классом узла , который имеет два члена, а именно данные и указатель next , указывающий на следующий узел.
InsertNode : в этой статье вставка выполняется в конец списка. Следуйте инструкциям, чтобы вставить узел в связанный список.
- Скажем, 4 нужно вставить в существующий связанный список, т. е. 1 -> 2 -> 3. Результирующий связанный список будет 1 -> 2 -> 3 -> 4.
- Чтобы вставить новый узел, пройдите до конца списка, пока не будет найден узел NULL.
- Создайте новый узел и свяжите новый узел с последним узлом связанного списка.
DeleteNode : в этой статье удаление выполняется с использованием индекса узла. Выполните шаги, чтобы удалить узел:
- Если удаляемый узел является головным узлом, сохраните головку в переменной temp . Затем обновите head как head->next . Удалить темп .
- Если индекс удаляемого узла больше длины списка, то возврат из функции.
- Пройдите до узла, который нужно удалить. Удалите узел и свяжите предыдущий узел со следующим узлом удаленного узла.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)