Как происходит вставка элемента в LinkedList

Вставка элемента в LinkedList

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

Структура узла LinkedList

Каждый элемент (узел) в LinkedList содержит три поля:

class Node<E> {
    E item;         // Данные элемента
    Node<E> next;   // Ссылка на следующий узел
    Node<E> prev;   // Ссылка на предыдущий узел (для двусвязного списка)
}

Основные сценарии вставки

1. Вставка в начало списка (addFirst)

Создается новый узел, который становится головой списка:

• Новый узел next указывает на старую голову
• Если список не пуст, prev старой головы указывает на новый узел
• Голова списка обновляется

// Пример реализации addFirst
public void addFirst(E element) {
    Node<E> newNode = new Node<>(element);
    newNode.next = first;  // Связываем с текущей головой
    if (first != null) {
        first.prev = newNode;  // Обновляем ссылку у старой головы
    } else {
        last = newNode;  // Если список был пуст, новый узел и голова и хвост
    }
    first = newNode;  // Обновляем голову списка
    size++;
}

2. Вставка в конец списка (addLast)

Аналогична вставке в начало, но работаем с хвостом:

• Новый узел prev указывает на старый хвост
• Если список не пуст, next старого хвоста указывает на новый узел
• Хвост списка обновляется

3. Вставка в произвольную позицию

При вставке по индексу требуется:

1. Найти узел в позиции index (занимает O(n))
2. Перестроить ссылки вокруг новой позиции

// Вставка перед существующим узлом
public void insertBefore(Node<E> existingNode, E element) {
    Node<E> newNode = new Node<>(element);
    newNode.prev = existingNode.prev;
    newNode.next = existingNode;
    
    if (existingNode.prev != null) {
        existingNode.prev.next = newNode;
    } else {
        first = newNode;  // Если вставляем перед головой
    }
    
    existingNode.prev = newNode;
    size++;
}

Сравнение временной сложности

Практический пример использования

LinkedList<String> list = new LinkedList<>();
list.add("A");           // Вставка в конец
list.addFirst("B");      // Вставка в начало → ["B", "A"]
list.add(1, "C");        // Вставка по индексу → ["B", "C", "A"]

// Внутреннее представление после вставки "C":
// Узел "B": prev=null, next="C"
// Узел "C": prev="B", next="A"
// Узел "A": prev="C", next=null

Ключевые особенности

1. Отсутствие перемещения данных — вставка требует только изменения ссылок, что особенно эффективно для больших объектов
2. Двусвязность — наличие ссылок prev и next упрощает вставку как перед, так и после существующего узла
3. Итераторная вставка — при работе через ListIterator вставка выполняется за O(1), так как итератор хранит текущую позицию

Оптимизации в реализации Java

• Кэширование последней позиции — при последовательном доступе по индексу сохраняется последний доступный узел
• Проверка границ — при вставке по индексу проверяется, ближе ли к началу или концу, чтобы минимизировать обход

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