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

# Время вставки элемента в LinkedList

Время вставки элемента в LinkedList зависит от позиции, в которую вставляется элемент, и составляет O(n) в худшем случае и O(1) в лучшем.

Анализ сложности

O(1) — лучший случай

Вставка в начало или конец списка:

• В начало: addFirst() — просто создаём новый узел и обновляем ссылку head. Это постоянное время.
• В конец: addLast() — если у нас есть ссылка на tail, то также O(1). Если её нет, нужно пройти весь список.

O(n) — худший и средний случай

Вставка в произвольную позицию требует:

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

Так как основное время занимает поиск позиции, итоговая сложность O(n).

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

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

// O(1) — вставка в начало
list.addFirst(10);           // head -> Node(10) -> null

// O(1) — вставка в конец (если есть tail)
list.addLast(20);            // head -> Node(10) -> Node(20) -> null

// O(n) — вставка в середину
list.add(1, 15);             // Нужно пройти до индекса 1
// head -> Node(10) -> Node(15) -> Node(20) -> null

// O(n) — вставка по итератору
ListIterator<Integer> iter = list.listIterator(1);
iter.add(12);

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

ArrayList vs LinkedList:

• ArrayList: вставка в конец O(1), в начало/середину O(n) из-за сдвига элементов
• LinkedList: вставка в начало O(1), в конец O(1) (если есть tail), в середину O(n) из-за поиска

Оптимизация

Для частых вставок в конец используйте:

LinkedList<Integer> list = new LinkedList<>();
list.addLast(value);  // O(1)

А не:

list.add(list.size(), value);  // O(n) — сначала поиск позиции

Выводы

• Вставка в начало/конец LinkedList: O(1)
• Вставка в произвольную позицию: O(n)
• LinkedList хорош для частых вставок/удалений в начало/конец
• Для частых обращений по индексу лучше использовать ArrayList