Suponha que as pilhas são implementadas por uma lista de ligação linear (Linear Linked List), com uma única variável, head, que é uma referência ao primeiro elemento da lista: Na figura, head aponta para a cabeça (topo) da pilha. Quais das seguintes ordens de complexidade, descrevem a complexidade temporal do método: push pop nessa implementação?

Alternativa A - (1) O(1) (2) O(1)

A questão aborda a análise de complexidade temporal de operações básicas em uma estrutura de dados de pilha implementada via lista encadeada simples.

Análise da Implementação

Para determinar a complexidade, é necessário entender onde as operações ocorrem em relação à variável head:

• Posição do Topo: O enunciado afirma explicitamente que head aponta para a cabeça (topo) da pilha. Isso significa que todas as inserções e remoções acontecem na primeira posição da lista.
• Operação Push (Inserção): Para adicionar um elemento, cria-se um novo nó, faz-se seu ponteiro apontar para o nó atual de head, e atualiza-se head para o novo nó. São apenas atribuições de ponteiros fixas.
• Operação Pop (Remoção): Para remover um elemento, salva-se o dado do nó atual de head, avança-se head para o próximo nó (head = head->next) e libera-se a memória. Também são operações fixas independentes do tamanho da lista.

Detalhamento das Complexidades

Ambas as operações são tempo constante, pois não exigem percorrer a lista para encontrar o topo ou a base. Se a implementação fosse diferente (ex: topo na cauda sem ponteiro para ela), o custo poderia ser O(n), mas neste caso específico, a referência direta ao topo garante eficiência máxima.

Portanto, ambas as operações possuem complexidade O(1).

Alternativa A.