Какая сложность вставки элемента в LinkedList

1️⃣ Как кратко ответить

Сложность вставки элемента в LinkedList составляет O(1), если у нас есть ссылка на узел, после которого нужно вставить элемент. В противном случае, если требуется сначала найти нужное место для вставки, сложность будет O(n).

2️⃣ Подробное объяснение темы

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

Зачем это нужно

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

Как работает вставка

1. Имея ссылку на узел: Если у нас уже есть ссылка на узел, после которого нужно вставить новый элемент, операция вставки выполняется за O(1). Это связано с тем, что мы просто перенастраиваем ссылки:

   • Создаем новый узел.
   • Устанавливаем ссылку нового узла на следующий узел текущего.
   • Перенастраиваем ссылку текущего узла на новый узел.

2. Без ссылки на узел: Если у нас нет ссылки на узел, и мы должны сначала найти нужное место для вставки, сложность возрастает до O(n), так как нам нужно пройти по списку, чтобы найти нужный узел.

Пример кода

Рассмотрим пример вставки элемента в односвязный LinkedList:

class Node {
    int data;
    Node next;
​
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
​
class LinkedList {
    Node head;
​
    // Вставка нового узла после заданного узла
    void insertAfter(Node prevNode, int newData) {
        if (prevNode == null) {
            System.out.println("Предыдущий узел не может быть null");
            return;
        }
​
        // Создаем новый узел
        Node newNode = new Node(newData);
​
        // Устанавливаем следующий узел нового узла как следующий узел предыдущего узла
        newNode.next = prevNode.next;
​
        // Устанавливаем следующий узел предыдущего узла как новый узел
        prevNode.next = newNode;
    }
}

• Node — класс, представляющий узел списка. Содержит данные и ссылку на следующий узел.
• LinkedList — класс, представляющий сам список. Содержит ссылку на первый узел (head).
• insertAfter — метод для вставки нового узла после заданного узла (prevNode).
  • Проверка, что prevNode не равен null, так как вставка невозможна без ссылки на предыдущий узел.
  • Создание нового узла с данными newData.
  • Установка ссылки next нового узла на следующий узел предыдущего узла.
  • Перенастройка ссылки next предыдущего узла на новый узел.

Этот метод демонстрирует вставку с временной сложностью O(1), так как мы уже имеем ссылку на узел, после которого нужно вставить новый элемент.