Чем отличаются ArrayList и LinkedList, и в каких случаях лучше использовать первое, а в каких второй вариант?

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

У ArrayList добавление в конец амортизированно O(1), вставка в середину требует сдвига элементов. У LinkedList поиск позиции стоит O(n), поэтому утверждение «любая вставка O(1)» неверно. Связный список расходует больше памяти на узлы и обычно хуже использует кеш процессора. Для большинства операций со списком выбирают ArrayList; для очереди часто подходит ArrayDeque. Решение уточняют по реальным операциям и измерениям.