Como se determina a complexidade temporal da remoção de um elemento localizado no meio de uma lista ligada?

A complexidade temporal de remover um elemento do meio de uma lista ligada depende de ter acesso direto a esse elemento e ao seu nó anterior.

• Se tiver um ponteiro para o próprio elemento e para o nó anterior (por exemplo, numa lista duplamente ligada), a remoção ocorre em O(1), pois basta reconfigurar os links.
• Se tiver apenas o valor ou um ponteiro para o elemento sem acesso ao anterior, primeiro é necessário percorrer a lista desde o início até esse elemento, o que leva O(n), onde n é o número de elementos antes do elemento a remover.

Assim, geralmente, remover do meio de uma lista ligada é considerado uma operação com complexidade de tempo O(n), se não houver acesso direto ao nó anterior.