Почему ArrayList эффективен для удаления последнего элемента?

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

Почему это быстрее, чем LinkedList?

• Локальность данных: Элементы ArrayList хранятся в непрерывном блоке памяти, что дружественно к кэшу процессора.
• Отсутствие накладных расходов: Не требуется обход списка или обновление ссылок между узлами, как в LinkedList.

Пример:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
// Удаление последнего элемента — операция O(1)
list.remove(list.size() - 1);

Сравнение:

• ArrayList.remove(last): O(1).
• LinkedList.remove(last): Теоретически O(1), но на практике медленнее из-за непрямого доступа к памяти и обновления ссылок.
• ArrayList.remove(first/middle): O(n), так как требует сдвига всех последующих элементов.