Qual é a complexidade temporal de remover um elemento numa lista ligada?

A complexidade temporal de remover um elemento numa lista ligada depende de saber ou não qual o nó a remover:

• Se houver um ponteiro para o próprio nó, a remoção ocorre em O(1), pois basta reconfigurar os links dos nós vizinhos.
• Se for necessário primeiro encontrar o elemento por valor ou posição, a busca leva O(n), e a complexidade total da remoção será O(n).

Assim, sem acesso ao nó — O(n), com acesso — O(1).