Вставка в связанный список

Опубликовано: 13 Января, 2023

Мы представили связанные списки в предыдущем посте. Мы также создали простой связанный список с 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 в связанном списке.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или если вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

РЕКОМЕНДУЕМЫЕ СТАТЬИ