Qual é a diferença no tempo de remoção do último elemento em ArrayList e LinkedList, e por que pode ser o mesmo?

O tempo de remoção do último elemento em ArrayList e LinkedList difere devido à sua estrutura interna, mas em alguns casos pode ser o mesmo.

• ArrayList é um array dinâmico. A remoção do último elemento geralmente ocorre em O(1), pois basta diminuir o tamanho do array (por exemplo, diminuir o contador de elementos). No entanto, se for necessário liberar memória ou deslocar elementos, o tempo pode aumentar, mas para o último elemento não é necessário deslocamento.

• LinkedList é uma lista duplamente ligada. A remoção do último elemento requer acesso ao último nó e ao seu anterior. Se a lista tiver uma referência ao final (tail), a remoção do último elemento também ocorre em O(1), pois é possível atualizar rapidamente os ponteiros.

Por que o tempo pode ser o mesmo:

Se a LinkedList for implementada com uma referência ao último elemento, remover o último elemento é simplesmente atualizar os ponteiros, o que leva O(1), assim como no ArrayList. Se não houver referência ao final, será necessário percorrer toda a lista, o que leva O(n).

Assim, com uma implementação correta, ambas as estruturas podem garantir a remoção do último elemento em tempo constante.