Как реализован LinkedList?

Внутренняя структура LinkedList в Java

LinkedList — это реализация двусвязного списка в Java Collections Framework. Это важная структура данных с O(1) операциями вставки/удаления в начало/конец, но O(n) доступом по индексу.

Основная структура данных

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;
    }
}

Каждый узел хранит:

• item — значение
• next — указатель на следующий узел
• prev — указатель на предыдущий узел

Поля класса LinkedList

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    
    transient int size = 0;      // Количество элементов
    transient Node<E> first;     // Ссылка на первый узел
    transient Node<E> last;      // Ссылка на последний узел
    
    // ... методы
}

Ключевые поля:

• size — текущее количество элементов в списке
• first — указатель на первый узел (для операций в начале)
• last — указатель на последний узел (для операций в конце)

Основные операции

1. Добавление элемента в конец (O(1))

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

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++;
}

2. Добавление элемента в начало (O(1))

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;     // Связываем новый с первым
    size++;
}

3. Получение элемента по индексу (O(n))

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

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

Оптимизация (size >> 1) — это деление на 2. LinkedList умно начинает поиск с ближайшего конца!

4. Удаление элемента (O(n) в худшем случае)

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

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;    // Перезвязываем: prev -> next
        x.prev = null;
    }
    
    if (next == null) {
        last = prev;         // Удаляем последний элемент
    } else {
        next.prev = prev;    // Перезвязываем: prev <- next
        x.next = null;
    }
    
    x.item = null;
    size--;
    return element;
}

Как LinkedList используется как очередь (Deque)

// Операции очереди — все O(1)
public void addLast(E e)     // add() в конец
public void addFirst(E e)    // add() в начало
public E removeLast()        // remove() с конца
public E removeFirst()       // remove() с начала
public E getLast()           // get() с конца
public E getFirst()          // get() с начала

// Использование как Stack
public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

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

*амортизированная, может быть O(n) при расширении массива

Пример реальной работы

LinkedList<String> list = new LinkedList<>();
list.add("A");        // first: A, last: A
list.add("B");        // first: A <-> B, last: B
list.addFirst("X");   // first: X <-> A <-> B, last: B

System.out.println(list.get(1));      // O(n) — ходим от X к A
list.remove(0);                       // Удаляем X, перезвязываем

Итератор и кэширование

LinkedList хранит текущую позицию при итерации для оптимизации последовательного доступа:

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // Кэширует последний возвращённый узел для быстрого remove()
}

Это позволяет быстро удалять элементы при итерации через iterator.remove().

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

✅ Используй LinkedList если:

• Много операций добавления/удаления в начало/конец (реализуешь Deque, Queue, Stack)
• Часто удаляешь элементы через iterator
• Размер часто меняется

❌ Не используй LinkedList если:

• Нужен частый доступ по индексу (используй ArrayList)
• Нужна производительность в realtime системах (LinkedList требует выделение памяти для каждого узла)
• Работаешь с большими данными (ArrayList более кэш-дружелюбен)