Qual é a estimativa da complexidade temporal da operação de remoção de um elemento numa lista ligada simples?

A complexidade temporal de remover um elemento numa lista ligada simples depende de termos um ponteiro para o elemento a remover ou apenas para a cabeça da lista.

• Se precisar remover um elemento, sabendo apenas a cabeça da lista, primeiro é necessário percorrer a lista para encontrar o elemento e o seu nó anterior. Isto leva O(n) tempo, onde n é o número de elementos na lista.
• Se tivermos um ponteiro para o elemento anterior (ou para o próprio elemento a remover, se for o primeiro), a remoção ocorre em O(1), pois basta reconfigurar os links.

Assim, em geral, remover um elemento numa lista ligada simples é uma operação com complexidade temporal de O(n).