Como avaliar a complexidade temporal das operações de inserção, remoção e busca de elementos numa lista ligada?

A complexidade temporal das operações numa lista ligada depende do que exatamente estamos a fazer e se temos acesso ao elemento necessário:

• Inserção:

  • No início da lista — O(1), pois basta alterar os links.
  • No final de uma lista ligada simples sem ponteiro para o final — O(n), é necessário percorrer toda a lista.
  • No final com ponteiro para o final — O(1).
  • Em um lugar arbitrário (por índice ou valor) — O(n), pois é preciso encontrar a posição.

• Remoção:

  • Remover o primeiro elemento — O(1).
  • Remover por valor ou índice — O(n), pois é preciso encontrar o elemento e o seu anterior.

• Busca:

  • Procurar um elemento por valor — O(n), pois é preciso percorrer a lista.

Assim, as operações principais requerem tempo linear se não houver acesso direto ao nó necessário. Isto deve-se à natureza sequencial das listas ligadas.