В чём разница между ArrayList и LinkedList? Какие операции эффективны для каждой из них?

Question

ArrayList — массив с динамическим размером. Эффективен для доступа по индексу (O(1)), но вставка/удаление в середину медленные (O(n)).LinkedList — двусвязный список. Быстрая вставка/удаление (O(1)), но доступ по индексу медленный (O(n)).

YeaHub · Accepted Answer

СтруктураArrayList: динамический массив.LinkedList: узлы с ссылками на предыдущий/следующий элемент.ArrayListдоступ по индексы - O(1)вставка в конец - O(1) (амортиз.)вставка в середину - O(n)удаление - O(n)LinkedListдоступ по индексы - O(n)вставка в конец - O(1)вставка в середину - O(n) (если есть итератор)удаление - O(1) (если есть итератор)List arrayList = new ArrayList<>(); // Лучше для частого чтения List linkedList = new LinkedList<>(); // Лучше для частой вставки/удаленияКогда использовать:ArrayList: если нужен быстрый доступ по индексу (например, кэширование).LinkedList: если часто изменяется структура (например, очередь).