Ответ
Временная сложность O(1) для удаления последнего элемента в обеих структурах данных достигается за счет разных механизмов, но это верно для стандартной реализации java.util.LinkedList.
ArrayList:
- Доступ к последнему элементу по индексу (
list.size() - 1) — O(1). - Удаление элемента с конца не требует сдвига остальных элементов в массиве, только уменьшение счетчика размера, что также выполняется за O(1).
LinkedList (двусвязный список в Java):
- Список хранит ссылки на голову (
first) и хвост (last). - Удаление последнего элемента (
removeLast()) — это операция с хвостовым узлом, выполняемая за O(1), так как не требует обхода списка.
Пример кода:
// ArrayList
ArrayList<String> arrayList = new ArrayList<>(Arrays.asList("A", "B", "C"));
arrayList.remove(arrayList.size() - 1); // O(1)
// LinkedList
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C"));
linkedList.removeLast(); // O(1)Важное уточнение: Это справедливо именно для двусвязного списка. В односвязном списке (без ссылки на хвост) удаление последнего элемента потребовало бы обхода до предпоследнего узла, что дало бы сложность O(n).