Вставка в связанный список
Мы представили связанные списки в предыдущем посте. Мы также создали простой связанный список с 3 узлами и обсудили обход связанного списка.
Все программы, обсуждаемые в этом посте, учитывают следующие представления связанного списка.
В этом посте обсуждаются методы вставки нового узла в связанный список. Узел можно добавить тремя способами
- В начале связанного списка
- После заданного узла.
- В конце связанного списка.
Добавьте узел спереди: (процесс из 4 шагов)
Подход: новый узел всегда добавляется перед заголовком данного связанного списка. И вновь добавленный узел становится новым главой связанного списка. Например, если данный связанный список имеет вид 10->15->20->25 и мы добавляем элемент 5 впереди, тогда связанный список становится 5->10->15->20->25. Назовем функцию, которая добавляет в начало списка, push(). Push() должен получить указатель на указатель заголовка, потому что push должен изменить указатель заголовка, чтобы он указывал на новый узел (см. это)
Ниже приведены 4 шага, чтобы добавить узел впереди.
Анализ сложности:
- Временная сложность: O(1). У нас есть указатель на голову, и мы можем напрямую прикрепить узел и изменить указатель. Таким образом, временная сложность вставки узла в положение головы составляет O (1), поскольку он выполняет постоянный объем работы.
- Вспомогательное пространство: O(1)
Добавить узел после заданного узла: (процесс из 5 шагов)
Подход: нам дается указатель на узел, и новый узел вставляется после данного узла.
Выполните шаги, чтобы добавить узел после заданного узла:
- Во-первых, проверьте, является ли данный предыдущий узел NULL или нет.
- Затем выделите новый узел и
- Назначьте данные новому узлу
- А затем сделайте следующий новый узел следующим из предыдущего узла.
- Наконец, переместите следующий из предыдущих узлов в качестве нового узла.
Анализ сложности:
Временная сложность: O(1), так как prev_node уже задан в качестве аргумента в методе, нет необходимости перебирать список, чтобы найти prev_node
Вспомогательное пространство: O (1), поскольку для изменения указателей используется постоянное пространство.
Добавьте узел в конце: (процесс из 6 шагов)
- Новый узел всегда добавляется после последнего узла данного связанного списка. Например, если заданный связанный список 5->10->15->20->25 и мы добавляем элемент 30 в конце, тогда связанный список становится 5->10->15->20->25- >30.
- Поскольку связанный список обычно представлен его заголовком, мы должны пройти по списку до конца, а затем изменить предпоследний узел на новый узел.
Ниже приведены 6 шагов для добавления узла в конце.
Анализ сложности:
- Временная сложность: O(N), где N — количество узлов в связанном списке. Поскольку существует цикл от начала до конца, функция работает O (n).
- Этот метод также можно оптимизировать для работы в O(1), сохраняя дополнительный указатель на конец связанного списка/
- Вспомогательное пространство: O(1)
Ниже приведена полная программа, которая использует все вышеперечисленные методы для создания связанного списка.
Временная сложность: O(N)
Вспомогательное пространство: O(1)
Альтернативный метод с использованием вызова конструктора:
- Однако другой метод использует вызов конструктора внутри класса узла, чтобы свести к минимуму работу по выделению памяти.
- Это также уменьшает количество строк кода.
Ниже приведена реализация вышеуказанного метода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)
Вы можете попробовать отработать вопросы MCQ в связанном списке.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или если вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.