Какую коллекцию выберешь для задач частой вставки элементов в середину?

Выбор коллекции для частой вставки элементов в середину

Это классический вопрос, который требует понимания внутреннего устройства коллекций и анализа сложности операций. Выбор зависит от конкретных требований и нагрузки.

LinkedList — оптимальный выбор

LinkedList — это двусвязный список, который обеспечивает константную временную сложность O(1) для вставки элемента, если у вас уже есть ссылка на узел. Основное преимущество:

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

// Вставка в начало
list.addFirst(0);  // O(1)

// Вставка в конец
list.addLast(4);   // O(1)

// Вставка в позицию
list.add(2, 100);  // O(n)

Ключевой момент: если вставлять через позицию add(index, element), сложность все ещё O(n) из-за необходимости найти нужный узел.

ArrayList — НЕ подходит

ArrayList использует динамический массив и имеет O(n) сложность для вставки в середину:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Вставка в позицию требует сдвига всех элементов
list.add(1, 100);  // O(n) — очень дорого при большом размере

При каждой вставке нужно:

1. Найти позицию
2. Сдвинуть все элементы справа на одну позицию
3. Вставить новый элемент

При частых операциях это приводит к деградации производительности.

Практические рекомендации

Используй LinkedList когда:

• Часто вставляешь/удаляешь элементы в начало или конец
• Используешь итератор и вставляешь через ListIterator
• Нужны операции removeFirst(), removeLast(), pollFirst()

LinkedList<String> queue = new LinkedList<>();
ListIterator<String> iter = queue.listIterator();

while (iter.hasNext()) {
    String current = iter.next();
    if (current.startsWith("remove_")) {
        iter.remove();  // O(1) удаление через итератор
    }
}

Избегай LinkedList когда:

• Часто обращаешься к элементам по индексу (get(i)) — O(n) операция
• Нужна кэш-локальность (массивы лучше для CPU кэша)
• Память критична (LinkedList требует больше памяти из-за указателей)

Альтернативные варианты

ArrayDeque — двусторонняя очередь на базе массива:

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(0);   // O(1)
deque.addLast(1);    // O(1)
deque.removeFirst(); // O(1)

Отличный выбор если вставляешь только в начало/конец.

CopyOnWriteArrayList — если нужна потокобезопасность при частом чтении:

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("item");  // Копирует весь массив (дорого)

НО это O(n) для записи, поэтому не подходит для частых вставок.

Итоговый совет

Для задач частой вставки в середину правильный ответ — LinkedList с использованием ListIterator для навигации и вставки:

LinkedList<Integer> list = new LinkedList<>();
ListIterator<Integer> iter = list.listIterator();

// Вставки через итератор имеют O(1) сложность
while (iter.hasNext()) {
    if (someCondition(iter.next())) {
        iter.add(newElement);  // O(1)
    }
}

Это обеспечит лучшую производительность по сравнению с ArrayList при сценариях с частыми модификациями в середине списка.