Когда использовать LinkedList вместо ArrayList в Java?

Ключевое различие: структура данных и сложность операций

Чтобы понять, когда использовать LinkedList вместо ArrayList, нужно разобраться, как они устроены внутри.

• ArrayList — это динамический массив. Элементы хранятся в непрерывном блоке памяти. Доступ по индексу — O(1), вставка/удаление в середине — O(n), так как нужно сдвигать элементы.
• LinkedList — это двусвязный список. Каждый элемент (узел) хранит ссылки на предыдущий и следующий элемент. Вставка/удаление в середине — O(1) (если у вас уже есть ссылка на нужный узел), но доступ по индексу — O(n), так как нужно пройти по списку от начала.

Когда использовать LinkedList (и когда НЕТ)

LinkedList оправдан только в двух сценариях:

1. Частые вставки/удаления в начале списка. Например, реализация очереди (FIFO) или стека (LIFO).
2. Частые вставки/удаления в середине списка, когда у вас есть ссылка на узел (например, при использовании итератора).

Вот пример, где LinkedList действительно быстрее:

import java.util.*;

public class CompareLists {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // Заполняем списки
        for (int i = 0; i < 100_000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // Тест: удаление из начала списка
        long start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            arrayList.remove(0); // O(n) — сдвиг всех элементов
        }
        long end = System.nanoTime();
        System.out.println("ArrayList remove from start: " + (end - start) / 1_000_000 + " ms");

        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            linkedList.remove(0); // O(1) — просто перекидываем ссылки
        }
        end = System.nanoTime();
        System.out.println("LinkedList remove from start: " + (end - start) / 1_000_000 + " ms");
    }
}

Результат (на моей машине): ArrayList — 450 ms, LinkedList — 8 ms. Разница колоссальная!

Почему в вашем случае лучше ArrayList

В вашем примере с задачами:

• Вы добавляете в конец — это O(1) для ArrayList (амортизированно) и O(1) для LinkedList.
• Удаляете из середины — для ArrayList O(n), для LinkedList тоже O(n), потому что сначала нужно найти элемент по индексу (а это O(n) для LinkedList!).
• Проходите циклом — для ArrayList это быстрее из-за кэш-локальности (элементы лежат рядом в памяти).

Итого: в вашем случае ArrayList выигрывает по всем статьям. LinkedList даёт преимущество только если вы удаляете/вставляете через итератор, а не по индексу.

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

• 90% случаев — используйте ArrayList. Он быстрее для итерации, занимает меньше памяти, лучше кэшируется.
• Используйте LinkedList, если:
  • Работаете с очередью (но лучше взять ArrayDeque — он быстрее).
  • Часто вставляете/удаляете в начале списка.
  • У вас есть итератор и вы часто вызываете iterator.remove().
• Для стека или очереди в современной Java используйте ArrayDeque — он быстрее LinkedList.

В вашем планировщике задач ArrayList — идеальный выбор. Не усложняйте себе жизнь!

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Итерация через for-each
long start = System.nanoTime();
for (int val : arrayList) { /* ничего не делаем */ }
System.out.println("ArrayList iteration: " + (System.nanoTime() - start));

start = System.nanoTime();
for (int val : linkedList) { /* ничего не делаем */ }
System.out.println("LinkedList iteration: " + (System.nanoTime() - start));