Чем отличается время удаления последнего элемента в ArrayList и LinkedList, и почему оно может быть одинаковым?

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

• ArrayList — это динамический массив. Удаление последнего элемента обычно происходит за O(1), так как достаточно просто уменьшить размер массива (например, уменьшить счетчик элементов). Однако, если нужно освободить память или сдвинуть элементы, время может увеличиться, но для последнего элемента сдвиг не нужен.

• LinkedList — это двусвязный список. Удаление последнего элемента требует доступа к последнему узлу и его предыдущему. Если у списка есть ссылка на хвост (tail), удаление последнего элемента также происходит за O(1), так как можно быстро обновить указатели.

Почему время может быть одинаковым:

Если LinkedList реализован с хранением ссылки на последний элемент, удаление последнего элемента — это просто обновление указателей, что занимает O(1), как и в ArrayList. Если же ссылки на хвост нет, придется проходить весь список, что займет O(n).

Таким образом, при правильной реализации обе структуры могут обеспечивать удаление последнего элемента за константное время.