Ответ
Ответ зависит от того, известен ли индекс последнего элемента.
- Если индекс известен, удаление из конца
ArrayListпроисходит за O(1), так же как и вLinkedList. ВArrayListэто просто уменьшение счетчика размера. - Если индекс неизвестен,
LinkedListимеет преимущество, так как хранит прямые ссылки на голову (first) и хвост (last).
Детальное сравнение:
| Операция | ArrayList |
LinkedList |
|---|---|---|
remove(list.size() - 1) |
O(1). Не требует сдвига элементов. | O(1) для получения последнего узла, но требует обхода до предпоследнего для обновления ссылок (O(n)). В Java LinkedList является двусвязным, поэтому removeLast() — O(1). |
remove(Object) для последнего элемента |
O(n) для поиска элемента + O(1) для удаления (если это действительно последний). | O(n) для поиска + O(1) для удаления узла. |
Практический пример:
// Эффективное удаление последнего элемента
ArrayList<Integer> arrayList = new ArrayList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(1, 2, 3));
// O(1) в обоих случаях, если использовать правильные методы
arrayList.remove(arrayList.size() - 1); // Быстро
linkedList.removeLast(); // Быстро (использует ссылку на 'last')Вывод: Для частых операций удаления/добавления именно в конец обе структуры эффективны (O(1)). LinkedList выигрывает, когда нужно часто удалять из начала (O(1) vs O(n) у ArrayList).