Что делает LinkedList при добавлении значения?

LinkedList при добавлении значения

LinkedList в Java — это реализация связного списка, где каждый элемент связан с предыдущим и следующим элементом через ссылки (указатели). При добавлении значения LinkedList выполняет специфичные операции, отличные от ArrayList.

Структура элемента LinkedList

Каждый элемент в LinkedList представлен внутренним классом Node:

private static class Node<E> {
    E item;                  // Данные
    Node<E> next;           // Ссылка на следующий элемент
    Node<E> prev;           // Ссылка на предыдущий элемент
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Что происходит при add()

Когда вы вызываете add(E e), элемент добавляется в конец списка:

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;  // Подключаем предыдущий элемент к новому
}

Пример выполнения

LinkedList<String> list = new LinkedList<>();

list.add("A");
// Состояние: first = [A|null←→null]

list.add("B");
// Состояние: first = [A|null←→B] → last = [B|A←→null]

list.add("C");
// Состояние: first = [A|null←→B] ↔ [B|A←→C] → last = [C|B←→null]

Добавление в конкретную позицию

При add(int index, E element) операция более сложная:

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);  // Если в конец, используем linkLast
    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;  // Подключаем предыдущий узел
}

Пример вставки в середину

LinkedList<Integer> list = new LinkedList<>();
list.add(1);  // [1]
list.add(3);  // [1 ← → 3]
list.add(1, 2);  // Вставляем 2 между 1 и 3
// [1 ← → 2 ← → 3]

Операции push() и addFirst()

Добавление в начало списка:

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;  // Текущий первый элемент
    final Node<E> newNode = new Node<>(null, e, f);  // Новый узел указывает на старый первый
    first = newNode;  // Новый узел становится первым
    
    if (f == null)
        last = newNode;  // Если список пуст
    else
        f.prev = newNode;  // Подключаем старый первый к новому
}

Временная сложность

LinkedList<String> list = new LinkedList<>();

list.add("A");           // O(1) - добавление в конец
list.addFirst("Z");      // O(1) - добавление в начало
list.add(5, "X");        // O(n) - требует поиска элемента по индексу

Сравнение с ArrayList

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

LinkedList<Integer> queue = new LinkedList<>();

// Добавляем элементы
queue.add(10);      // O(1)
queue.add(20);      // O(1)
queue.addFirst(5);  // O(1)

// Результат: [5, 10, 20]

System.out.println(queue);  // [5, 10, 20]

Вывод: LinkedList при добавлении создаёт новый узел и обновляет связи (указатели) соседних узлов. Добавление в конец и начало работает за O(1), а вставка в середину требует поиска позиции (O(n)). LinkedList идеален для очередей и стеков, но неэффективен для частых обращений по индексу.