В каком случае вставка элемента быстрее в ArrayList чем в LinkedList

Когда вставка в ArrayList может быть быстрее, чем в LinkedList

В подавляющем большинстве сценариев вставка (insertion) элементов в середину или начало списка быстрее в LinkedList, чем в ArrayList, из-за разницы в реализации структур данных. Однако есть специфические случаи, где ArrayList демонстрирует лучшую производительность при вставке.

Основные различия структур данных

// ArrayList - динамический массив
ArrayList<String> arrayList = new ArrayList<>();
// LinkedList - двусвязный список
LinkedList<String> linkedList = new LinkedList<>();

ArrayList: -- Хранит элементы в непрерывном массиве -- Вставка в середину требует сдвига всех последующих элементов (O(n) в худшем случае) -- Доступ по индексу за O(1) -- Высокая локальность данных (кеш-дружелюбность)

LinkedList: -- Хранит элементы в отдельных узлах с ссылками -- Вставка в середину требует только изменения ссылок (O(1) после нахождения позиции) -- Доступ по индексу за O(n) -- Низкая локальность данных

Случаи, когда ArrayList быстрее при вставке

1. Вставка в конец списка без необходимости расширения массива

Когда ArrayList имеет достаточную емкость (capacity) и вставка происходит в конец, операция выполняется за O(1):

// ArrayList с начальной емкостью 1000
ArrayList<Integer> list = new ArrayList<>(1000);
for (int i = 0; i <-minCapacity-; i++) {
    list.add(i); // Вставка в конец - O(1)
}

В этом случае:

• ArrayList: Просто присваивает значение в следующую ячейку массива
• LinkedList: Требует создания нового узла, выделения памяти, установки ссылок

Производительность: ArrayList быстрее благодаря: -- Отсутствию аллокации памяти для каждого элемента (память уже выделена) -- Отсутствию операций с указателями -- Лучшей кеш-локальности

2. Вставка в конец при предварительном обеспечении capacity

Если заранее известен размер коллекции и установлена достаточная емкость:

// Плохо: постоянные расширения массива
ArrayList<Integer> badList = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    badList.add(i); // Многократные copyOf() при расширении
}

// Хорошо: емкость задана заранее
ArrayList<Integer> goodList = new ArrayList<>(1000000);
for (int i = 0; i < 1000000; i++) {
    goodList.add(i); // Без реаллокаций - очень быстро
}

3. Мелкие списки или вставка близко к концу

Для небольших списков (менее 10-20 элементов) преимущества LinkedList нивелируются: -- Накладные расходы на создание узла -- Поиск позиции в LinkedList все равно требует O(n) -- Для ArrayList сдвиг небольшого количества элементов может быть быстрее

// Вставка на предпоследнюю позицию в ArrayList из 5 элементов
ArrayList<String> smallList = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
smallList.add(3, "E"); // Сдвигает только элемент "D" - очень быстро

4. Пакетная вставка с последующей сортировкой

Если нужно вставить много элементов и потом отсортировать:

// ArrayList
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    arrayList.add(random.nextInt()); // Быстрая вставка в конец
}
Collections.sort(arrayList); // Быстрая сортировка благодаря массиву

// LinkedList
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    linkedList.add(random.nextInt()); // Медленнее из-за создания узлов
}
Collections.sort(linkedList); // ОЧЕНЬ медленно - преобразование в массив и обратно

Бенчмарк-пример

@Benchmark
public void arrayListInsertion(Blackhole bh) {
    ArrayList<Integer> list = new ArrayList<>(SIZE);
    for (int i = 0; i < SIZE; i++) {
        list.add(i); // Вставка в конец
    }
    bh.consume(list);
}

@Benchmark
public void linkedListInsertion(Blackhole bh) {
    LinkedList<Integer> list = new LinkedList<>();
    for (int i = 0; i < SIZE; i++) {
        list.add(i); // Вставка в конец
    }
    bh.consume(list);
}

Результаты (условные): . Вставка 1 млн элементов в конец: -- ArrayList с заданной capacity: ~50 мс -- LinkedList: ~120 мс

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

1. Используйте ArrayList, когда: -- Чаще требуется доступ по индексу, чем вставка -- Известен примерный размер коллекции -- Вставки преимущественно в конец -- Важна производительность итерации

2. Используйте LinkedList, когда: -- Частые вставки/удаления в начале/середине -- Не требуется частый доступ по индексу -- Работаете как с очередью (addFirst/removeLast)

Вывод

ArrayList быстрее LinkedList при вставке только в специфических условиях: -- Вставка в конец списка -- При достаточной емкости (не требуется расширение массива) -- Для мелких списков -- При пакетной обработке с последующими операциями над всем списком

В остальных случаях (вставка в начало/середину) LinkedList сохраняет преимущество благодаря константной сложности изменения ссылок против линейной сложности сдвига элементов в массиве.