Как работает связанность в LinkedList?

Связанность в LinkedList: структура данных

LinkedList в Java реализует двусвязный список (doubly linked list), где каждый элемент содержит ссылки на соседние элементы. Это позволяет эффективно добавлять и удалять элементы с обоих концов.

Внутренняя структура

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

• Данные (item) — значение элемента
• next — ссылка на следующий узел
• prev — ссылка на предыдущий узел

// Внутренний класс Node в LinkedList
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;
    }
}

Как происходит связывание

При добавлении элемента в начало:

LinkedList<String> list = new LinkedList<>();
list.addFirst("A");
list.addFirst("B");
list.addFirst("C");

// Визуально:
// C <-> B <-> A
//
// Структура:
// Node(prev=null, item=C, next=Node(B)) <->
// Node(prev=Node(C), item=B, next=Node(A)) <->
// Node(prev=Node(B), item=A, next=null)

Внутренняя реализация 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<Integer> list = new LinkedList<>(Arrays.asList(10, 20, 30));
list.add(1, 15);  // Вставить 15 на позицию 1

// До: 10 <-> 20 <-> 30
// После: 10 <-> 15 <-> 20 <-> 30

Как это работает внутри:

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) {
    // 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<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));
list.remove(1);  // Удалить "B"

// До: A <-> B <-> C
// После: A <-> C

Реализация:

private E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;  // Следующий узел
    final Node<E> prev = x.prev;  // Предыдущий узел
    
    if (prev == null) {
        first = next;  // Если удаляем первый узел
    } else {
        prev.next = next;  // Перенаправляем ссылку
        x.prev = null;     // Разрываем связь с удалённым узлом
    }
    
    if (next == null) {
        last = prev;  // Если удаляем последний узел
    } else {
        next.prev = prev;  // Перенаправляем обратную ссылку
        x.next = null;     // Разрываем связь с удалённым узлом
    }
    
    x.item = null;
    size--;
    return element;
}

Особенности и преимущества

Преимущества двусвязного списка:

• ✅ O(1) добавление/удаление с обоих концов (addFirst, removeLast и т.д.)
• ✅ Двусторонний обход (Iterator в обе стороны)
• ✅ Нет необходимости копировать массив при расширении

Недостатки:

• ❌ O(n) доступ по индексу (нужно пройти от начала или конца)
• ❌ Больше памяти на ссылки (prev и next)
• ❌ Медленнее чем ArrayList для итерации по индексу

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

// Часто добавляют/удаляют из начала/конца
Queue<String> queue = new LinkedList<>();
queue.add("task1");
queue.poll();

// Двусторонняя очередь
Deque<String> deque = new LinkedList<>();
deque.addFirst("A");
deque.addLast("B");
deque.removeLast();

Главная идея: LinkedList — это цепь узлов, каждый узел знает соседей через prev/next ссылки. Это позволяет быстро добавлять/удалять элементы, но медленно искать по индексу.