Como determinar a complexidade temporal da operação de inserção de um elemento no meio de uma lista ligada simples?

Inserir um elemento no meio de uma lista ligada simples requer primeiro percorrer a lista desde o início até à posição desejada, pois numa lista ligada simples não há ligações inversas nem acesso direto aos elementos por índice.

A complexidade temporal da operação de inserção no meio de uma lista ligada simples é O(n), onde n é o número de elementos até à posição de inserção. Isto deve-se à necessidade de percorrer a lista até ao nó desejado.

O processo de inserção em si (alteração de ponteiros) leva O(1), mas a procura da posição leva O(n), pelo que a complexidade final é O(n).