Как устроен LinkedList

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

Основные компоненты LinkedList

  1. Внутренний класс Node Внутри класса LinkedList есть внутренний статический класс Node, который представляет узел списка. Каждый узел содержит три ключевых поля:
    • E item — хранит значение элемента.
    • Node<E> next — ссылка на следующий узел.
    • Node<E> prev — ссылка на предыдущий узел.
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;
    }
}
  1. Поля класса LinkedList
    • Node<E> first — ссылка на первый узел списка.
    • Node<E> last — ссылка на последний узел списка.
    • int size — количество элементов в списке.

При получении элемента по индексу с помощью метода get производится обход по списку с начала или конца, смотря к чему этот индекс ближе - к началу или концу.

Производительность операций

  • Добавление/Удаление в начало или конец:
    Эти операции выполняются за O(1), так как требуется изменить всего несколько ссылок.
  • Доступ по индексу:
    Время доступа по индексу составляет O(n), поскольку нужно пройти от начала или конца списка до нужного узла.
  • Вставка/Удаление в середине:
    Эти операции также требуют O(n) времени из-за необходимости найти нужный узел.