Какая структура данных оптимальна для частой вставки элементов в середину коллекции?

Какая структура данных оптимальна для частой вставки элементов в середину коллекции?

Отличный вопрос, который напрямую связан с практической разработкой. Ответ зависит от того, как часто ты обращаешься к элементам.

Однозначный ответ

LinkedList — оптимален для частых вставок в середину, когда ты знаешь позицию. ArrayList проигрывает, так как требует сдвига элементов.

Почему LinkedList лучше?

ArrayList при вставке в середину:
[A][B][C][D][E] -> вставляем X в позицию 2
Нужно сдвинуть C, D, E: O(n)
[A][B][X][C][D][E]

LinkedList при вставке в середину:
A <-> B <-> C <-> D <-> E
Нужно переставить ссылки: O(1)
A <-> B <-> X <-> C <-> D <-> E

Но есть БОЛЬШОЙ нюанс

// ЕСЛИ у тебя есть Iterator:
LinkedList<String> list = new LinkedList<>();
Iterator<String> it = list.iterator();
it.next();
it.next();
it.add("X");  // O(1) — эффективно!

// ЕСЛИ нет Iterator и нужно найти позицию:
LinkedList<String> list = new LinkedList<>();
list.add(500, "X");  // O(500) — найти 500-й элемент O(500) + вставка O(1)
// Итого O(n) — медленнее чем ArrayList!

Сравнение для вставки в середину

Сценарий                    ArrayList   LinkedList
──────────────────────────────────────────────────
Знаешь позицию, есть Index  O(n)        O(n) + O(1)
Есть Iterator               O(n)        O(1)
Вставка в конец            O(1)*       O(1)
Вставка в начало           O(n)        O(1)
Случайный доступ           O(1)        O(n)

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

// ПЛОХО: ArrayList для частых вставок в середину без итератора
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

for (int i = 0; i < 1000; i++) {
    list.add(500, "X" + i);  // O(n) — медленно!
}

// ХОРОШО: LinkedList с Iterator
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

// Если нужно вставлять в начало
for (int i = 0; i < 1000; i++) {
    list.addFirst("X" + i);  // O(1)
}

// Если нужно вставлять по курсору
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.add("X");  // O(1) — вставка через Iterator
        break;
    }
}

// ЛУЧШЕ: ArrayList если часто нужен доступ
ArrayList<String> list = new ArrayList<>();
// Или используй более специализированные структуры

На практике: когда что использовать

Используй LinkedList для:

• Частых вставок/удалений через Iterator
• Реализации очередей (Deque)
• Когда не нужен random access

Используй ArrayList для:

• Частых чтений/случайного доступа
• Одноразовых вставок
• Когда нужна компактность памяти

Реальный пример

// Сценарий: фильтруем список, удаляя нечётные числа

// ПЛОХО: ArrayList с индексом
ArrayList<Integer> list = new ArrayList<>(
    Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
);

for (int i = 0; i < list.size(); i++) {
    if (list.get(i) % 2 != 0) {
        list.remove(i);  // O(n) — сдвиг элементов
        i--;  // Нужно уменьшить индекс
    }
}

// ХОРОШО: LinkedList с Iterator
LinkedList<Integer> list = new LinkedList<>(
    Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
);

Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() % 2 != 0) {
        it.remove();  // O(1) — просто переставить ссылки
    }
}

Вывод

Для частой вставки в середину оптимален LinkedList, НО только если:

1. Используешь Iterator или методы addFirst()/addLast()
2. Не нужен frequent random access

Если нужны оба — frequent вставки и random access — рассмотри альтернативы или оптимизируй алгоритм.