Java-программа для вставки узла в связанный список
Мы представили связанные списки в предыдущем посте. Мы также создали простой связанный список с 3 узлами и обсудили обход связанного списка.
Все программы, обсуждаемые в этом посте, учитывают следующие представления связанного списка.
В этом посте обсуждаются методы вставки нового узла в связанный список. Узел можно добавить тремя способами
1) В начале связанного списка
2) После данного узла.
3) В конце связанного списка.
Добавьте узел спереди: (процесс из 4 шагов)
Новый узел всегда добавляется перед заголовком данного связанного списка. И вновь добавленный узел становится новым главой связанного списка. Например, если данный связанный список имеет вид 10->15->20->25 и мы добавляем элемент 5 впереди, тогда связанный список становится 5->10->15->20->25. Назовем функцию, которая добавляет в начало списка, push(). Функция push() должна получить указатель на указатель заголовка, потому что push должен изменить указатель заголовка, чтобы он указывал на новый узел (см. это)
Ниже приведены 4 шага, чтобы добавить узел впереди.
Временная сложность push() составляет O(1), так как она выполняет постоянный объем работы.
Добавить узел после заданного узла: (процесс из 5 шагов)
Нам дается указатель на узел, и новый узел вставляется после данного узла.
Java
/* This function is in LinkedList class. Inserts a new node after the given prev_node. This method is defined inside LinkedList class shown above */public void insertAfter(Node prev_node, int new_data) { // 1. Check if the given Node is null if (prev_node == null) { System.out.println( "The given previous node cannot be null"); return; } /* 2. Allocate the Node & 3. Put in the data*/ Node new_node = new Node(new_data); // 4. Make next of new Node as next // of prev_node new_node.next = prev_node.next; // 5. make next of prev_node as new_node prev_node.next = new_node; } |
Временная сложность функции insertAfter() составляет O(1), так как она выполняет постоянный объем работы.
Добавьте узел в конце: (процесс из 6 шагов)
Новый узел всегда добавляется после последнего узла данного связанного списка. Например, если заданный связанный список 5->10->15->20->25 и мы добавим элемент 30 в конце, тогда связанный список станет 5->10->15->20->25- >30.
Поскольку связанный список обычно представлен его заголовком, мы должны пройти по списку до конца, а затем изменить предпоследний узел на новый узел.
Ниже приведены 6 шагов для добавления узла в конце.
Временная сложность добавления равна O(n), где n — количество узлов в связанном списке. Поскольку существует цикл от начала до конца, функция работает O (n).
Этот метод также можно оптимизировать для работы в O(1), сохраняя дополнительный указатель на конец связанного списка/
Ниже приведена полная программа, которая использует все вышеперечисленные методы для создания связанного списка.
Выход:
Created Linked list is: 1 7 8 6 4
Пожалуйста, обратитесь к полной статье в Linked List | Набор 2 (Вставка узла) для более подробной информации!