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

Ответ

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

Структура LinkedList

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

Java LinkedList — это двусвязный список, каждый узел имеет ссылки на соседей.

Пример вставки

Представим список: A → B → C → D

Хотим вставить X между B и C.

ДО вставки:

A ← → B ← → C ← → D

ПОСЛЕ вставки X:

A ← → B ← → X ← → C ← → D
       |    ↓ ↑    |
       +----X----+

Алгоритм вставки

Шаг 1: Найди позицию (traverse)

Нужно найти узел перед позицией вставки. Если список большой, это требует прохода по всем узлам.

// Поиск узла в позиции index
Node<E> node = getNode(index);
// Внутри getNode — цикл по узлам:
Node<E> x = first;
for (int i = 0; i < index; i++) {
    x = x.next;
}
return x;

Шаг 2: Создай новый узел

Node<E> newNode = new Node<>(element);

Шаг 3: Переставь связи

// Текущие связи:
// prevNode ← → nextNode

// Новые связи:
// prevNode ← → newNode ← → nextNode

newNode.next = nextNode;     // newNode указывает на nextNode
newNode.prev = prevNode;     // newNode указывает на prevNode
prevNode.next = newNode;     // prevNode указывает на newNode
if (nextNode != null) {
    nextNode.prev = newNode; // nextNode указывает на newNode
}

Полный пример из Java исходников

public boolean add(E e) {
    linkLast(e);
    return true;
}

private void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
}

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

private void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
}

private Node<E> node(int index) {
    if (index < (size >> 1)) {
        // Если индекс в первой половине — начинаем с first
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // Если во второй половине — начинаем с last (оптимизация!)
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Практический пример

import java.util.LinkedList;
import java.util.List;

public class LinkedListInsertionExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // Добавляем элементы: A, B, D
        list.add("A");
        list.add("B");
        list.add("D");
        
        System.out.println("До вставки: " + list);
        // Вывод: [A, B, D]
        
        // Вставляем C между B и D (индекс 2)
        list.add(2, "C");
        
        System.out.println("После вставки: " + list);
        // Вывод: [A, B, C, D]
        
        // Вставляем X между B и C (индекс 2)
        list.add(2, "X");
        
        System.out.println("После второй вставки: " + list);
        // Вывод: [A, B, X, C, D]
    }
}

Сложность операций

Примечание: LinkedList медленнее для вставки в середину, чем ArrayList!

Почему вставка медленная

1. Поиск позиции — нужно пройтись по всем узлам (O(n))
2. Переставка связей — только O(1)

Общая сложность: O(n), потому что поиск доминирует.

Оптимизация LinkedList

Java LinkedList имеет оптимизацию: если индекс близко к концу, начинает с конца:

if (index < (size >> 1)) {  // Половина
    // Начать с начала
    for (int i = 0; i < index; i++)
        x = x.next;
} else {
    // Начать с конца
    for (int i = size - 1; i > index; i--)
        x = x.prev;
}

Это снижает сложность в лучшем случае до O(n/2).

Визуальная демонстрация

// Исходный список: [1, 2, 3, 4, 5]
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1,2,3,4,5));

// Вставляем 99 на позицию 2 (между 2 и 3)
list.add(2, 99);

// Шаг 1: Поиск узла на позиции 2
//   1 → 2 → 3 → 4 → 5
//       ↓    ↑
//    Нашли 3

// Шаг 2: Создание нового узла
//   newNode = Node(99)

// Шаг 3: Переставка связей
//   1 → 2 → 99 → 3 → 4 → 5
//       ↑        ↓   ↑
//   prevNode   newNode nextNode

System.out.println(list);
// [1, 2, 99, 3, 4, 5]

Когда использовать LinkedList

✅ Используй LinkedList когда:

• Частые операции в начале/конце списка
• Нужна эффективная вставка/удаление из начала
• Часто удаляешь элементы при итерации

❌ НЕ используй LinkedList когда:

• Частый доступ по индексу (list.get(i))
• Вставка в произвольное место (все равно O(n))
• Мало памяти (каждый узел занимает больше место: item + 2 ссылки)

Best Practice

// Плохо — много вставок в середину
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add(500, "element" + i); // Медленно! O(n) каждый раз
}

// Хорошо — добавляй в конец, потом sort если нужно
List<String> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add("element" + i);
}
Collections.sort(list);

Заключение

Вставка в середину LinkedList работает путём:

1. Поиска узла на позиции (O(n))
2. Создания нового узла (O(1))
3. Переставки четырёх ссылок (O(1))

Общая сложность: O(n), где n — расстояние до позиции вставки.